徐文強(qiáng)，周揚(yáng)名，王 喆

1.華東理工大學(xué) 信息科學(xué)與工程學(xué)院，上海 200237

2.上海交通大學(xué) 中美物流研究院，上海 200030

Li 等人[1]提出的著色旅行商問題（colored traveling salesman problem，CTSP）是一種考慮到工件工作區(qū)域部分重合的多旅行商問題（multiple traveling salesman problem，MTSP）。近年來(lái)，著色旅行商問題作為一種適于多機(jī)差別化訪問的問題模型被廣泛地拓展和研究。著色旅行商問題是多旅行商問題的擴(kuò)展，也是具有挑戰(zhàn)性的NP難[1]的組合優(yōu)化問題，當(dāng)前流行的求解算法多為啟發(fā)式算法。針對(duì)著色旅行商問題模型難以適應(yīng)現(xiàn)實(shí)中存在的沖突條件，本文提出了帶沖突圖的著色旅行商問題。

作為著名的組合優(yōu)化問題，TSP 無(wú)論是在運(yùn)籌學(xué)、數(shù)學(xué)還是計(jì)算機(jī)科學(xué)領(lǐng)域均受到持久的關(guān)注。TSP 理論已被廣泛地應(yīng)用到各種規(guī)劃、調(diào)度等優(yōu)化問題，包括計(jì)算機(jī)電路板布線、印制電路板鉆孔、汽配件噴涂等具體案例。而多旅行商問題是對(duì)旅行商問題的泛化和發(fā)展。在該問題中，一組城市集被多個(gè)旅行商訪問，且每個(gè)城市只允許被旅行商訪問一次，最終目標(biāo)是最小化所有旅行商的總旅行成本。多旅行商問題也已經(jīng)被廣泛應(yīng)用到各種優(yōu)化中，例如，人力資源規(guī)劃、計(jì)算機(jī)網(wǎng)絡(luò)的拓?fù)湓O(shè)計(jì)和郵遞路線規(guī)劃等。

在現(xiàn)實(shí)生活中，要求城市、配送點(diǎn)或者工作位置在任何條件下均保持開放權(quán)限是困難的，也是不現(xiàn)實(shí)的。在多旅行商問題的應(yīng)用中，一些配送點(diǎn)往往只能接受特定的物流供應(yīng)商供應(yīng)，一些工件的加工區(qū)域往往存在部分重合，事實(shí)上雙橫梁水切割系統(tǒng)問題[1]正是存在上述情況而啟發(fā)了著色旅行商問題的提出。著色旅行商問題不同于多旅行商問題的顯著特點(diǎn)在于著色旅行商問題存在多組城市集，包括各旅行商專屬城市集及共享城市集。

而現(xiàn)實(shí)中的沖突情況如危險(xiǎn)貨品運(yùn)輸，對(duì)抗條件下的跨境物流，沖突工作位置的多工件協(xié)作等具體案例，則進(jìn)一步推動(dòng)帶沖突圖的著色旅行商問題（colored traveling salesman problem with conflicts graph，CTSPCG）的提出。帶沖突圖的著色旅行商問題需要考慮城市之間的沖突關(guān)系。

自Li等人[1]提出著色旅行商問題以來(lái)，眾多學(xué)者不斷發(fā)展和開拓了相關(guān)鄰域的研究。孟祥虎[2]對(duì)著色旅行商問題進(jìn)行了泛化研究，提出了包含通用CTSP[2]、串行/連環(huán)CTSP[3]和邊權(quán)重動(dòng)態(tài)CTSP[4]三種問題和相應(yīng)求解算法。徐向平[5]則在孟祥虎的工作基礎(chǔ)上做了進(jìn)一步拓展，用超圖重新描述了孟祥虎提出的三種問題，并提出了雙目標(biāo)CTSP[6]和帶有先約束的CTSP[7]以及相應(yīng)的求解算法。董學(xué)士等人則先后提出了著色瓶頸旅行商問題[8-9]、著色平衡旅行商問題[10]和平衡多旅行商問題[11]，以及相應(yīng)的求解算法。代星[12]和王東明等人[13]則提出了最大值最小化的著色旅行商問題和最大值最小化的連環(huán)著色旅行商問題。

著色旅行商問題是多旅行商問題的擴(kuò)展，也是具有挑戰(zhàn)性的NP難[1]的組合優(yōu)化問題，當(dāng)前流行的求解算法多為啟發(fā)式算法。Li 等人[1]提出了遺傳算法（genetic algorithm，GA）、貪婪初始化的遺傳算法（GA with greedy initialization）、爬坡遺傳算法（hill-climbing GA）以及模擬退火遺傳算法（simulated annealing GA，SAGA）等算法。Meng 等人[14]提出了變鄰域局部搜索算法（variable neighborhood search）。Xu 等人[15]提出了基于德勞內(nèi)三角的變鄰域局部搜索算法（Delaunay-triangulation-based VNS）。He 等人先后提出了迭代兩階段局部搜索算法（iterated two-phase local search，ITPLS）[16]和分組模因搜索算法（grouping memetic search）[17]。韓舒寧等人[18]設(shè)計(jì)了一種基于均勻設(shè)計(jì)（uniform design，UD）融合伊藤算法IT?和蟻群算法（ant colony optimization，ACO）的混合伊藤算法（hybrid IT? algorithm with uniform design，UDHIT?）。Pandiri 等人[19]提出了蜂群智能方法，Dong 等人[20]則提出了人工蜂群算法（artificial bee colony，ABC）。Zhou等人，即本團(tuán)隊(duì)，則先后提出了多鄰域模擬退火搜索（multi-neighborhood simulated annealing search）[21]和基于多鄰域模擬退火的迭代局部搜索算法（multi-neighborhood simulated annealing-based iterated local search）[22]。

為拓展著色旅行商問題在沖突條件下的適應(yīng)性，本文參考帶沖突圖的背包問題[23-24]等沖突條件下的組合優(yōu)化問題，提出了帶沖突的著色旅行商問題。為找到對(duì)該問題更好的求解方法，文中所提出的模因算法參考了其他經(jīng)典的模因算法[25-26]。模因算法能夠更好地平衡算法的搜索能力和逃脫局部最優(yōu)能力。

本文所作的工作如下：

（1）提出了帶沖突圖的著色旅行商問題（CTSP-CG），建立了相應(yīng)數(shù)學(xué)模型，并使用精確算法求解器求解。

（2）提出了基于大領(lǐng)域模擬退火局部搜索的模因算法并求解。比較分析了模因算法和CPLEX精確求解器的實(shí)驗(yàn)結(jié)果，發(fā)現(xiàn)模因算法在20個(gè)小規(guī)模實(shí)例中的9個(gè)結(jié)果更好，在18 個(gè)實(shí)例上展現(xiàn)了其遠(yuǎn)超精確算法的求解速度。比較分析模因算法和其他本文實(shí)現(xiàn)的啟發(fā)式算法，發(fā)現(xiàn)模因算法在全部14 個(gè)中等規(guī)模實(shí)例上均取得了更好結(jié)果。結(jié)果顯示模因算法在求解CTSP-CG問題上具有統(tǒng)計(jì)學(xué)意義的顯著性。

（3）通過替換模因算法中的搜索算子進(jìn)行了消融實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果驗(yàn)證了模因算法中局部搜索算子的有效性。而通過替換模因算法中的種群更新算子進(jìn)行的消融實(shí)驗(yàn)，則驗(yàn)證了種群更新算子的有效性。

1 帶沖突圖的著色旅行商問題

圖1 是帶沖突圖的著色旅行商問題的示意圖。城市0表示倉(cāng)庫(kù)（depot）城市。所有旅行商從城市0出發(fā)，最終回到城市0。城市1，2，3 各自分別為旅行商1，2，3的專屬城市。專屬城市只允許對(duì)應(yīng)旅行商訪問。城市4，5，6，7為共享城市。共享城市允許任意旅行商訪問，這也意味著城市0即倉(cāng)庫(kù)城市也為共享城市。除城市0外，其余城市只能被旅行商訪問且僅訪問一次。4號(hào)城市和5號(hào)城市相互存在沖突，因此不允許同一旅行商訪問這兩個(gè)城市。圖1 中旅行商1 從0 號(hào)城市出發(fā)，依次訪問了1號(hào)專屬城市，4號(hào)共享城市后回到0號(hào)城市；旅行商2 從0 號(hào)城市出發(fā)，依次訪問了3 號(hào)專屬城市，7 號(hào)共享城市，6 號(hào)共享城市后回到0 號(hào)城市；旅行商3 從0號(hào)城市出發(fā)，依次訪問了2 號(hào)專屬城市，5 號(hào)共享城市，最終回到0號(hào)城市。

圖1 帶沖突圖的著色旅行商問題示意圖Fig.1 Example of colored traveling salesman problems with conflict graph

1.1 問題描述

帶沖突圖的著色旅行商問題是著色旅行商問題的擴(kuò)展模型。同著色旅行商問題相似，有m個(gè)旅行商和n個(gè)城市，其中m，n∈N+，且m＜n。為更好表述該問題，本文引入了一個(gè)完全圖概念G(V,E)。其中，V表示所有城市的集合，集合大小為n，其中各個(gè)城市各自編號(hào)為0 到n-1。每條邊用(i,j)∈E，i≠j,i,j∈V表示。并且用權(quán)重wij表示城市i與城市j之間的距離。V能夠被劃分為m+1 個(gè)非空不相交集合：包含一個(gè)共享城市集S和m個(gè)旅行商對(duì)應(yīng)的專屬城市集C1,C2,…,Ck,…,Cm，其中k表示k號(hào)旅行商。數(shù)學(xué)化表達(dá)可以為,Ci∩Cj=φ,?i≠j∈{0,1,…,m} 。每個(gè)專屬城市集Ck中的城市只有對(duì)應(yīng)的旅行商k才允許訪問，而共享城市集S中的城市可以被任意旅行商訪問。除倉(cāng)庫(kù)城市外所有城市都必須被訪問一次且只能訪問一次。訪問時(shí)，旅行商從倉(cāng)庫(kù)城市出發(fā)，根據(jù)選定的邊到下一個(gè)城市，訪問其對(duì)應(yīng)全部專屬城市及選定的共享城市后，最終返回倉(cāng)庫(kù)城市，同時(shí)規(guī)劃時(shí)也需要確保所有旅行商也訪問完了所有共享城市。其中，倉(cāng)庫(kù)城市設(shè)定為0號(hào)城市。

為了適配現(xiàn)實(shí)中存在的運(yùn)輸條件沖突情況，帶沖突圖的著色旅行商問題相對(duì)于普通的著色旅行商問題引入了沖突與沖突圖H的概念。H為一個(gè)n×n的0-1矩陣，當(dāng)Hij=1 時(shí)表示城市i和城市j存在沖突，也即城市i和城市j不允許被同一個(gè)旅行商訪問。Hij=0則表示沒有這樣的沖突。該問題的目標(biāo)與著色旅行商問題的目標(biāo)相同，即最小化總成本。沖突關(guān)系是相互的，因此沖突圖矩陣為對(duì)稱矩陣。

1.2 整數(shù)規(guī)劃模型

不同于3-index整數(shù)規(guī)劃模型[1，16]表示著色旅行商問題。本文采取了2-index的整數(shù)規(guī)劃模型描述帶沖突圖的著色旅行商問題。其中，決策變量x和y如下：

決策變量xij=1 表示邊(i，j)有旅行商通過，若沒有旅行商通過，則xij=0。yik也是決策變量，當(dāng)yik=1時(shí)表示旅行商k訪問了城市1，若旅行商k未訪問，則yik=0。

目標(biāo)函數(shù)為：

問題模型服從下列限制條件：

所有的旅行商只能由0號(hào)城市即倉(cāng)庫(kù)城市出發(fā)，最終也必須返回0號(hào)城市，

旅行商k被禁止訪問其他旅行商的專屬城市，同時(shí)其他旅行商也被禁止訪問旅行商k的專屬城市。也就是說(shuō)不存在一條這樣的邊，它由一個(gè)專屬城市到另一個(gè)不同旅行商專屬城市構(gòu)成，

0號(hào)城市需由m個(gè)旅行商各自訪問且僅訪問一次：

但這里目前只能表示0 號(hào)城市被旅行商總共訪問了m次，并不能限制其精確訪問一次。要達(dá)成上述意圖，還需結(jié)合以下3個(gè)約束。

所有非0 號(hào)城市都只由一個(gè)城市連入且只連出一個(gè)城市：

一個(gè)非0號(hào)城市只能被一個(gè)旅行商城市所訪問：

城市與旅行商的一致性約束。不存在相鄰兩條邊被不同旅行商訪問，保證決策變量x和y的一致性，進(jìn)而確保一條路線只有一個(gè)旅行商訪問，

下式為著名的mtz約束，該約束意在判斷圖中無(wú)子環(huán)路，判斷方式為除去0 號(hào)城市外，剩余規(guī)劃路線不構(gòu)成環(huán)路。對(duì)于CTSP等類MTSP問題而言即便有多個(gè)環(huán)路，但都必須訪問0 號(hào)城市，因此該約束仍然生效。此外，mtz約束僅在有向圖問題上有效：

當(dāng)兩個(gè)共享城市存在沖突時(shí)，這兩個(gè)城市不能由同一個(gè)旅行商訪問：

2 模因算法

模因算法受文化擴(kuò)散現(xiàn)象啟發(fā)，且有機(jī)地融合了遺傳算法的框架。模因算法并不是內(nèi)容固定的優(yōu)化算法，而是作為一種廣泛的算法類別和解決特定問題的一般指導(dǎo)方針。模因算法是基于種群的元啟發(fā)式算法，由一個(gè)演化框架和一組局部搜索算法組成，局部搜索算法在演化框架的生成階段內(nèi)被使用。模因算法已被廣泛地應(yīng)用于組合優(yōu)化問題的求解，例如文獻(xiàn)[17，25-26]。對(duì)于帶沖突圖的著色旅行商問題，求解算法既要考慮不同城市的可訪問性，又要考慮城市之間可能存在的沖突。也就是說(shuō)相對(duì)于著色旅行商問題，帶沖突圖的著色旅行商問題在原本相對(duì)平滑的鄰域空間中添加了若干隔斷，會(huì)導(dǎo)致求解算法在運(yùn)行時(shí)更容易地陷入局部最優(yōu)解。

本文為降低算法運(yùn)行時(shí)陷入局部最優(yōu)的概率和提高算法掙脫局部最優(yōu)的可能，采用了模因算法及自適應(yīng)大規(guī)模鄰域搜索算子。同時(shí)，更好更快的搜索能力有助于限定時(shí)間內(nèi)找到更好的解，這也是采用自適應(yīng)大規(guī)模領(lǐng)域搜索的另一目的，此外，文中為此采用了貪婪初始化策略。

2.1 解的表示與評(píng)估

本文采用的解的表示法為鄰接矩陣表示法[16]。其他的表示法包括雙基因編碼表示法[1]、直接編碼表示法[3]。鄰接矩陣表示法與直接編碼表示法均可以唯二表示一個(gè)解，而雙基因編碼表示法不能。相比于直接編碼表示法，鄰接矩陣表示法占用的存儲(chǔ)空間更大，但插入與刪除操作更快更便捷[22]。

以圖2 為例，如圖所示，左起第一列第二至四行代表旅行商，第一行左起第二至八列代表城市編號(hào)。0號(hào)城市默認(rèn)為原點(diǎn)城市。第二行第二列的數(shù)字1，代表該位置的列所對(duì)應(yīng)的城市（即0 號(hào)城市）在該位置的行所對(duì)應(yīng)的旅行商（即1號(hào)旅行商）的下一個(gè)城市編號(hào)，在這里則為1 號(hào)城市。依此類推，可得旅行商1 號(hào)的序列為r1：{0，1，4，0}，旅行商2 號(hào)的訪問序列為r2：{0，2，5，0}，分組3的訪問序列為r3：{0，3，7，6，0}。該編碼方式克服了雙染色體編碼方式重復(fù)編碼多，操作時(shí)間復(fù)雜度高的問題。是一種相當(dāng)迅速有效的編碼方式。

圖2 解的表示Fig.2 Presentation of solution

2.2 算法框架

在流程圖3中，種群初始化采取了一種貪婪隨機(jī)方式，以期在算法前期取得較好的結(jié)果。選擇父本則是完全的隨機(jī)化的，以提供隨機(jī)性。交叉算子采用了m-tour方式對(duì)解進(jìn)行重組，以保存父本解的優(yōu)秀特性。自適應(yīng)的大規(guī)模鄰域搜索是該模因算法的核心，作為局部搜索算子獲得更好解是有效的。種群更新采取的是簡(jiǎn)單更新的方式，若新解的結(jié)果好于種群中的最壞解，則將新解替換掉種群中的最壞解。

圖3 模因算法流程圖Fig.3 Flow chart of memetic algorithm

2.3 種群初始化

本文采取了與文獻(xiàn)[16-17，19，22]中相似的解初始化方法。帶沖突圖的著色旅行商問題中包含了共享城市和專屬城市兩類城市集，因此，為充分利用問題本身的特性，解的初始化方法有兩個(gè)構(gòu)造階段。不同于著色旅行商問題，帶沖突圖的著色旅行商問題在構(gòu)造解的過程中需要適應(yīng)沖突。

種群初始化方法如下：

解的初始化的偽代碼

初始化第一階段為第4～19 行，該階段將所有專屬城市放入了解S中。其中第4行表示遍歷所有旅行商，第5 行表示隨機(jī)選擇并遍歷旅行商k的專屬城市集。第6 行表示初始化Δ，Δ記錄了最佳插入位置的代價(jià)。第7、8 行表示初始化Index，Index表示找到的最好位置。第9行出現(xiàn)的e(i,j)表示邊，該邊由i城市出發(fā)到j(luò)城市，rk表示旅行商k的訪問序列。此處需要注意的是，當(dāng)解S中僅用城市0時(shí)，其訪問序列為rk：{0，0}，遍歷rk所得的邊也為e(0,0)。第10～14 行則表示記錄最好插入位置和代價(jià)。第17行表示將隨機(jī)遍歷的專屬城市c插入解中的最好插入位置，根據(jù)解的表示其實(shí)現(xiàn)可能有所不同。

初始化第二階段為第21～38行，該階段將所有的共享城市放入了解S中。其中第21 行表示隨機(jī)選擇并遍歷共享城市集U。第22～25 行初始化Δ、Index和BestRoute，BestRoute表示最好位置的旅行商路線。第22 行表示遍歷旅行商。第27～29 行判斷隨機(jī)選擇的共享城市c是否能插入到旅行商路線rk中而不引起沖突，其具體實(shí)現(xiàn)形式與沖突圖的實(shí)現(xiàn)形式和解的實(shí)現(xiàn)形式有關(guān)。第30～37行與第9～15行相似，表示找到最好的插入位置，唯一不同的是第35 行額外記錄了最好位置對(duì)應(yīng)的旅行商。第39行表示插入共享城市c到解S的最好插入位置。

種群初始化方法則是在解的初始化的基礎(chǔ)上初始化多個(gè)解。同時(shí)，種群初始化在確保種群多樣性上也有實(shí)際需求，因此需要檢測(cè)是否有重復(fù)解。本文采用判斷初始解的值是否完全相同的方式，即，來(lái)判斷解是否重復(fù)。

2.4 自適應(yīng)的大規(guī)模鄰域搜索

本文提出的自適應(yīng)大規(guī)模鄰域搜索算子包含四個(gè)搜索模塊，兩個(gè)更新模塊。四個(gè)搜索模塊分別為：鏈接重構(gòu)搜索，路線間鄰域搜索，路線內(nèi)鄰域搜索，路線內(nèi)與路線間聯(lián)合鄰域搜索。兩個(gè)更新模塊分別為：直接更新與模擬退火更新。自適應(yīng)大規(guī)模鄰域搜索有多輪迭代。每輪迭代都隨機(jī)指定一個(gè)搜索模塊和更新模塊，該方式提高了搜索在不同情況的泛用性。四個(gè)搜索模塊如下：

（1）鏈接重構(gòu)搜索受到限制性交叉交換（constrained cross-exchange）[17]啟發(fā)。該搜索分為兩個(gè)階段，鏈接斷開階段和鏈接重構(gòu)階段。在鏈接斷開階段需遍歷解，然后按概率切出單純由共享城市組成的鏈路片段pc。在鏈接重構(gòu)階段，則將隨機(jī)選定的鏈路片段pc與各可插入位置e(i,j)進(jìn)行比較，找出最好的可插入位置及插入方向。這與解的初始化的偽代碼中的第22～39 行極為相似，不同處在于需要同k-opt一般額外考慮pc插入到解中的方向是正或逆。若該鏈路片段pc與所有路線中的共享城市均沖突，則將該鏈路pc打散成一個(gè)個(gè)共享城市逐個(gè)插入。插入位置的尋找方式和插入方式與第22～39行相同。

（2）路線內(nèi)鄰域搜索與[19，22]中的對(duì)應(yīng)搜索相同。其分為移除階段和重插入階段，移除階段即簡(jiǎn)單地隨機(jī)移除解中的專屬城市。重插入階段的工作則與解的初始化第一階段，即解的初始化的偽代碼中的第4～19行相同。

（3）路線間鄰域搜索與文獻(xiàn)[19，22]中的對(duì)應(yīng)搜索相似。其同樣分為移除階段和重插入階段，移除階段隨機(jī)移除解中的共享城市。重插入階段的工作則與解的初始化第二階段，即解的初始化的偽代碼中的第21～40行相同。

（4）路線內(nèi)與路線間聯(lián)合鄰域搜索則是先執(zhí)行路線間鄰域搜索再執(zhí)行路線內(nèi)鄰域搜索。選擇該順序是受Zhou等人[21-22]在CTSP實(shí)例上進(jìn)行相似實(shí)驗(yàn)的啟發(fā)。

需要注意的是，不同于所參考的求解著色旅行商問題的搜索算子，文中自適應(yīng)大規(guī)模鄰域搜索算子的模塊必須適應(yīng)沖突條件。諸模塊的適應(yīng)沖突條件的策略均為規(guī)避策略。即比較城市i和路線r1中的城市j∈r1是否滿足Hij=1，若滿足則認(rèn)為城市i與路線r1有沖突。為規(guī)避沖突，不能把城市i放入路線r1。同理，在模塊（1）中若滿足Hij=1，其中城市i∈p1屬于片段p1，城市j∈r1屬于路線r1，則認(rèn)為片段p1與路線r1沖突。兩個(gè)更新模塊：直接更新即是新結(jié)果較好即更新，結(jié)果較差則放棄。模擬退火更新則確保接受新的更好解的同時(shí)，根據(jù)當(dāng)前溫度，按metropolis概率公式判斷是否接受新的更差解。當(dāng)前溫度可由當(dāng)前迭代次數(shù)與設(shè)定的初始溫度換算得出。

2.5 解的重組

解的重組是將選定的多個(gè)父本解進(jìn)行重組，得到一個(gè)新的子代解，在遺傳算法中通常也可稱為交叉（crossover）。圖4 是解的重組的示意圖。該重組方式為m-tour方式。

圖4 解的重組Fig.4 Reorganization of solution

該重組方案分為兩個(gè)階段，在圖4所示實(shí)例中階段1有3個(gè)步驟，階段2有1個(gè)步驟。圖4所示實(shí)例所選兩個(gè)本解于步驟1 左側(cè)表示。左父本解的結(jié)構(gòu)為lr1={0,1,4,0},lr2={0,2,5,0},lr3={0,3,7,6,0} 。右父本解的結(jié)構(gòu)為rr1={0,4,1,0},rr2={0,2,6,0},rr3={0,7,3,5,0} 。其中，1，2，3號(hào)城市均為專屬城市，5，6，7號(hào)城市及0號(hào)倉(cāng)庫(kù)（depot）城市均為共享城市。

具體如圖4中所示。在第一個(gè)階段，找到兩個(gè)解中每城市代價(jià)最小的路線并將其加入新解中，其中每城市代價(jià)是通過計(jì)算該路線總代價(jià)比上該路線城市數(shù)得來(lái)的。若存在多條每城市代價(jià)最小的路線，如步驟1 中l(wèi)r1={0,1,4,0},rr1={0,4,1,0}，兩路線的每城市代價(jià)均為最小，則隨機(jī)一條路線加入到新解中，實(shí)例中步驟1選擇的是虛線表示的lr1={0,1,4,0} 。加入子代解后，需刪去兩個(gè)父本解中的對(duì)應(yīng)的路線和共享城市，如步驟2 中左右父本解均不存在關(guān)于1，4 號(hào)的城市的路線，步驟3中右父本解不存在關(guān)于2，5，6號(hào)城市的路線。重復(fù)以上操作，直到所有路線都被構(gòu)建，也即專屬城市全部加入解中。

在第二階段，需要重新插入第一階段完成后剩余的未加入到解中的共享城市，圖4 中所示實(shí)例僅有6 號(hào)城市未插入到解中，因此僅需一個(gè)步驟，步驟流程與解的初始化第二階段相同。具體到圖4 實(shí)例而言，6 號(hào)城市先對(duì)步驟4中左側(cè)原解中的每條路線所屬的旅行商進(jìn)行考察，判斷是否存在沖突；之后，對(duì)不存在沖突的旅行商的邊進(jìn)行考察，找到增加的成本最小的邊，如e(0,2)后，將城市插入該邊，即刪除e(0,2)，增加e(0,6)，e(6,2) 。

2.6 種群更新

當(dāng)前對(duì)種群進(jìn)行更新的策略有多種，從替換的解可分為：替換最壞解[1，17]，替換當(dāng)前位置解[10-11,18-20]。從更新的評(píng)估公式可分為：考慮多樣性[1，17]，不考慮多樣性[10-11，18-20]。從接受的策略可分為：無(wú)論新解優(yōu)劣直接接受[10-11，18]，新解更優(yōu)才接受[1，17]，按概率接受更新[19-20]。這些種群更新的策略應(yīng)用在不同的基于種群的算法上。

本文采取的更新策略為，替換最壞解且考慮多樣性的新解更優(yōu)才接受的方式。其對(duì)多樣性的評(píng)估方式是觀察原種群中是否有與新解相同的解。當(dāng)一個(gè)新解生成后，判斷其是否已在種群中，若存在則說(shuō)明多樣性不足，將其放棄。否則繼續(xù)判斷其是否比當(dāng)前最壞解更壞，若更壞則放棄。否則，將其替換掉最壞解。

2.7 算法時(shí)間復(fù)雜度分析

在循環(huán)開始后，需要執(zhí)行選擇父本組件，由于本文中該組件是完全隨機(jī)化的，因此，可認(rèn)為其復(fù)雜度為O(1)。之后需要執(zhí)行解的重組組件，其第一階段時(shí)間復(fù)雜度為O(n)，第二階段的時(shí)間復(fù)雜度為O(pres·n2)，其中pres表示第一階段剩下的城市的概率，解的重組整體的時(shí)間復(fù)雜度為O(pres·n2)。自適應(yīng)大規(guī)模鄰域搜索算子包含四個(gè)搜索模塊和兩個(gè)更新模塊，四個(gè)搜索模塊在具體運(yùn)行中的花費(fèi)或有不同，但時(shí)間復(fù)雜度均可用O(pc·n2)表示。其中pc為城市被選中而重新插入到解種的概率。因此，單次循環(huán)的時(shí)間復(fù)雜度可以表示為O((pres+pc)·n2)，或者將pres和pc視為常數(shù)，用O(n2)表示。

3 實(shí)驗(yàn)與結(jié)果分析

3.1 基準(zhǔn)實(shí)例

本文采取的實(shí)驗(yàn)實(shí)例如表1所示。其中，eil來(lái)自于文獻(xiàn)[1]，gr來(lái)自于文獻(xiàn)[19-20]。這些數(shù)據(jù)由原始的TSP數(shù)據(jù)轉(zhuǎn)換而成，原始名為TSPLIB，可從以下網(wǎng)址下載：http：//people.sc.fsu.edu/～jburkardt/datasets/tsp/tsp.html。此外，沖突圖由限制聯(lián)通子圖的算法隨機(jī)生成，以確保其必定有解。

表1 實(shí)驗(yàn)中使用的CTSP-CG實(shí)例Table 1 Instances of CTSP-CG used in experiments

3.2 實(shí)驗(yàn)設(shè)置

本文所采取的實(shí)驗(yàn)環(huán)境為：AMD Ryzen 7 5800H with Radeon Graphics，3.20 GHz處理器和16 GB RAM。本文提供了一個(gè)精確算法和兩個(gè)啟發(fā)式算法均采用C++語(yǔ)言，且均使用MSVC 2019 在Windows 系統(tǒng)上編譯后運(yùn)行。

本文在小規(guī)模實(shí)例上運(yùn)用CPLEX算法軟件進(jìn)行了精確算法的實(shí)驗(yàn)，以求得實(shí)例解目標(biāo)值的可靠范圍。本文提出并實(shí)現(xiàn)了一個(gè)基于大規(guī)模鄰域模擬退火搜索的模因算法在小規(guī)模實(shí)例及中等規(guī)模實(shí)例上運(yùn)行，以進(jìn)一步優(yōu)化實(shí)例解。最后，本文設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)消融實(shí)驗(yàn)：通過用單純的鏈接重構(gòu)搜索算子替換模因算法中的局部搜索算子得到了一個(gè)新的啟發(fā)式算法，在部分小規(guī)模及中大規(guī)模實(shí)例上運(yùn)行，并與原模因算法對(duì)比分析。

模因算法的種群大小為20，一般遺傳算法或模因算法的所取大小為20～40[1，3，17，25-26]，大規(guī)模的種群可以提高搜索范圍，但也會(huì)增大初始化種群的開銷。自適應(yīng)大規(guī)模領(lǐng)域局部搜索算子的初始溫度為1 000，最大迭代次數(shù)為400，降溫速率為0.97，上述參數(shù)設(shè)置參考文獻(xiàn)[22]，文獻(xiàn)中給出了多組參數(shù)配置，文中采用了給出的推薦配置之一。初始溫度和降溫速率過大會(huì)導(dǎo)致退火過程無(wú)法收斂，反之則可能導(dǎo)致退火過程收斂過快。最大迭代次數(shù)越大，搜索效果越好，但開銷也相應(yīng)增加。鏈接重構(gòu)搜索算子中切出的鏈路片段的最大長(zhǎng)度為7，該參數(shù)設(shè)置參考文獻(xiàn)[17]精確算法在小規(guī)模實(shí)例上的設(shè)定截止時(shí)間為7 200 s。鏈路片段過大會(huì)導(dǎo)致片段過于完整趨近于路線，鏈路片段過小會(huì)導(dǎo)致其碎片化趨近于單個(gè)城市，都會(huì)失去鏈路重構(gòu)的意義。啟發(fā)式算法在小規(guī)模實(shí)例上的運(yùn)行時(shí)間為60 s，中等規(guī)模實(shí)例的運(yùn)行時(shí)間為600 s，所有實(shí)例均運(yùn)行10次。eil51-3和eil101-5實(shí)例中的城市數(shù)比常規(guī)實(shí)例多出2個(gè)，是為了更好地適配算法輸入輸出的數(shù)據(jù)結(jié)構(gòu)，重復(fù)了專屬城市兩次，這對(duì)于最優(yōu)解值是無(wú)影響的，但是提高了找到最優(yōu)解的難度。

3.3 實(shí)驗(yàn)結(jié)果分析

表2 是精確算法與啟發(fā)式算法在CTSP-CG 小規(guī)模實(shí)例上的求解結(jié)果比較。表2 左側(cè)CLEPX 欄中顯示，在eil21-2 到eil41-3 及eil51-2 等8 個(gè)實(shí)例，CPLEX 均能獲得有效結(jié)果，用時(shí)均少于7 200 s，其上界與下界間隔極小，對(duì)于最小化問題，可以認(rèn)為其上界結(jié)果是真實(shí)值。精確式算法在實(shí)例eil51-4 和eil51-4 到eil101-6 上均超過運(yùn)行時(shí)間7 200 s，并未確定最好解。超過7 200 s的實(shí)例中，僅有eil41-4，eil51-3 和eil51-5 三個(gè)實(shí)例的上界與啟發(fā)式算法所得到的最好解和平均解匹配。

表2 小規(guī)模實(shí)例上的實(shí)驗(yàn)結(jié)果對(duì)比Table 2 Comparisons of results on small scale instances

表2右側(cè)ALNMEM欄顯示，在全部小規(guī)模實(shí)例上，本文提出的模因算法均得到了穩(wěn)定的最好解。從運(yùn)行時(shí)間上看，模因式算法的效果在所有實(shí)例上的運(yùn)行時(shí)間均少于精確式算法。從運(yùn)行結(jié)果上看，模因算法在9個(gè)實(shí)例上超過精確式算法，其余實(shí)例與精確式算法的上界匹配。表2中比較了精確式算法下界和模因算法的平均秩次，發(fā)現(xiàn)模因算法的平均秩次小于精確算法的平均秩次。平均秩次是比較多實(shí)例多組數(shù)據(jù)的一種度量方式。平均秩次計(jì)算方式為比較多組數(shù)據(jù)之間實(shí)例相同的數(shù)據(jù)并排名，從1開始，數(shù)據(jù)值越小則排名序號(hào)越小，若某實(shí)例有多組數(shù)據(jù)排名相同則將排名取平均，例如有兩組數(shù)據(jù)并列第一則兩組數(shù)據(jù)排名均為1.5，最后按組別將每個(gè)實(shí)例數(shù)據(jù)相加并除以實(shí)例數(shù)。平均秩次越小則說(shuō)明該組數(shù)據(jù)結(jié)果越佳。經(jīng)wilcoxon符號(hào)秩檢驗(yàn)分析[27]，分別比較ALNMEM的平均解和最好解與CPLEX的下界，其p值均為0.003 9，小于0.05，具備統(tǒng)計(jì)學(xué)意義的顯著性。

表3 是啟發(fā)式算法在CTSP-CG 中等規(guī)模實(shí)例上的求解結(jié)果比較。中等規(guī)模的CTSP-CG 實(shí)例共有14 個(gè)。表3中基于均勻設(shè)計(jì)的混合伊藤算法（UDHIT?）源于文獻(xiàn)[18]，人工蜂群算法（ABC）源于文獻(xiàn)[20]，迭代兩階段局部搜索（ITPLS）源于文獻(xiàn)[16]。此外，文中根據(jù)CTSP-CG的問題特性對(duì)兩個(gè)算法進(jìn)行了一定修改。對(duì)于UDHIT? 算法、ABC 算法和ITPLS，在原算法的基礎(chǔ)上增加了初始化和搜索時(shí)的限制措施，使得該算法初始化和搜索鄰域的得到的解均為無(wú)沖突的合法解，得到了新的算法ABC*。此外，文中統(tǒng)一將算法的停止條件設(shè)置為600 s截止。

表3 中等規(guī)模實(shí)例上的實(shí)驗(yàn)結(jié)果對(duì)比Table 3 Comparisons of results on medium scale instances of CTSP-CG

UDHIT? 的使用蟻群算法初始化的時(shí)間復(fù)雜度為O(n2)，UDHIT?內(nèi)部有兩個(gè)循環(huán)結(jié)構(gòu)，其中一個(gè)小循環(huán)結(jié)構(gòu)嵌套在一個(gè)大循環(huán)結(jié)構(gòu)中。小循環(huán)結(jié)構(gòu)的時(shí)間復(fù)雜度為O(popSize·n2)。小循環(huán)結(jié)構(gòu)在大循環(huán)結(jié)構(gòu)中的停止條件為最大未改進(jìn)次數(shù)，其值參考文獻(xiàn)[18]設(shè)為60。ABC 初始化需要依次生成路線內(nèi)和路線間鄰域解，其時(shí)間復(fù)雜度可綜合為O(n2)，而一輪迭代的時(shí)間復(fù)雜度為O(popSize·n2)。ITPLS 采用2-opt 和re-insert作為搜索算子，其時(shí)間復(fù)雜度均為O(n2)，此外ITPLS也有兩個(gè)循環(huán)結(jié)構(gòu)，小循環(huán)結(jié)構(gòu)的停止條件為50次[16]。

表3 顯示，模因算法能夠在精確式算法難以求解的中等規(guī)模實(shí)例上取得較好解，且相對(duì)于其他啟發(fā)式算法，模因算法在中等規(guī)模實(shí)例上的求解結(jié)果均較好。經(jīng)wilcoxon 符號(hào)秩檢驗(yàn)分析[27]，無(wú)論最好解或平均解，ALNMEM 與另外三個(gè)算法分別比較的p值均為1.22E-4，小于0.05，具備統(tǒng)計(jì)學(xué)意義的顯著性。而比較平均秩次后，可以認(rèn)為ANLMEM相對(duì)其他啟發(fā)式算法在平均解和最好解上均具有優(yōu)勢(shì)。

新模因算法ALNMEM*與原模因算法ALNMEM在部分實(shí)例下的對(duì)比結(jié)果如表4 所示?？梢钥闯鰞H在實(shí)例eil76-5 上兩算法均穩(wěn)定取得匹配的最好解和平均解。而在實(shí)例eil101-7上，兩算法得到了相同的最好解，但ALNMEM的平均解好于ALNMEM*。而在其他實(shí)例上，ALNMEM 的最好解與平均解均好于ALNMEM*。平均秩次也表明，無(wú)論在平均解還是最好解上ALNMEM相對(duì)ALNMEM*均具有優(yōu)勢(shì)。

表4 不同搜索算子的模因算法的實(shí)驗(yàn)結(jié)果對(duì)比Table 4 Comparisons of memetic algorithms with different searching operation

表5中ALNMEM**是更換ALNMEM中的種群替換策略所得到的新算法。具體而言，是將原種群替換策略中的“考慮多樣性”替換為“不考慮多樣性”，即不進(jìn)行檢測(cè)新解與原解是否重復(fù)，只要新解比種群中的最壞解好，就用新解替換掉種群中的最壞解?？梢钥闯?，在實(shí)例eil76-5 和eil101-7 上兩算法均取得了匹配的最好解和平均解。而在實(shí)例gr229-30，gr666-15 上，原算法ALNMEM 在平均解和最好解上均好于新算法ALNMEM**。平均秩次同樣表明，ANLMEM 相對(duì)ALNMEM**在平均解和最有解上均占有優(yōu)勢(shì)。

表5 不同替換策略的模因算法的實(shí)驗(yàn)結(jié)果對(duì)比Table 5 Comparisons of memetic algorithms with different replace strategy

4 結(jié)語(yǔ)

針對(duì)著色旅行商問題難以有效處理具有沖突的應(yīng)用場(chǎng)景，本文首次提出了一個(gè)考慮沖突圖的著色旅行商問題。本文首先構(gòu)建了帶沖突圖的著色旅行商問題的整數(shù)規(guī)劃模型，使用了CPLEX 軟件進(jìn)行了求解。為了處理更大規(guī)模的問題實(shí)例，本文提出并實(shí)現(xiàn)了一個(gè)有效的模因算法。與精確算法對(duì)比，本文所提出的模因算法展示了優(yōu)越的性能。

后續(xù)工作可聚焦于：（1）將本文所提模因算法應(yīng)用于更多乃至極端狀況下的真實(shí)情景。（2）進(jìn)一步提高本文所提模因算法的自適應(yīng)能力，從而更穩(wěn)定快速地求解。