徐文強，周揚名，王 喆

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

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

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

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

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

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

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

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

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

本文所作的工作如下：

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

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

（3）通過替換模因算法中的搜索算子進行了消融實驗。實驗結果驗證了模因算法中局部搜索算子的有效性。而通過替換模因算法中的種群更新算子進行的消融實驗，則驗證了種群更新算子的有效性。

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

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

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

1.1 問題描述

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

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

1.2 整數規(guī)劃模型

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

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

目標函數為：

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

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

旅行商k被禁止訪問其他旅行商的專屬城市，同時其他旅行商也被禁止訪問旅行商k的專屬城市。也就是說不存在一條這樣的邊，它由一個專屬城市到另一個不同旅行商專屬城市構成，

0號城市需由m個旅行商各自訪問且僅訪問一次：

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

所有非0 號城市都只由一個城市連入且只連出一個城市：

一個非0號城市只能被一個旅行商城市所訪問：

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

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

當兩個共享城市存在沖突時，這兩個城市不能由同一個旅行商訪問：

2 模因算法

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

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

2.1 解的表示與評估

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

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

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

2.2 算法框架

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

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

2.3 種群初始化

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

種群初始化方法如下：

解的初始化的偽代碼

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

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

種群初始化方法則是在解的初始化的基礎上初始化多個解。同時，種群初始化在確保種群多樣性上也有實際需求，因此需要檢測是否有重復解。本文采用判斷初始解的值是否完全相同的方式，即，來判斷解是否重復。

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

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

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

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

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

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

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

2.5 解的重組

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

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

該重組方案分為兩個階段，在圖4所示實例中階段1有3個步驟，階段2有1個步驟。圖4所示實例所選兩個本解于步驟1 左側表示。左父本解的結構為lr1={0,1,4,0},lr2={0,2,5,0},lr3={0,3,7,6,0} 。右父本解的結構為rr1={0,4,1,0},rr2={0,2,6,0},rr3={0,7,3,5,0} 。其中，1，2，3號城市均為專屬城市，5，6，7號城市及0號倉庫（depot）城市均為共享城市。

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

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

2.6 種群更新

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

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

2.7 算法時間復雜度分析

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

3 實驗與結果分析

3.1 基準實例

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

表1 實驗中使用的CTSP-CG實例Table 1 Instances of CTSP-CG used in experiments

3.2 實驗設置

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

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

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

3.3 實驗結果分析

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

表2 小規(guī)模實例上的實驗結果對比Table 2 Comparisons of results on small scale instances

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

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

表3 中等規(guī)模實例上的實驗結果對比Table 3 Comparisons of results on medium scale instances of CTSP-CG

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

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

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

表4 不同搜索算子的模因算法的實驗結果對比Table 4 Comparisons of memetic algorithms with different searching operation

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

表5 不同替換策略的模因算法的實驗結果對比Table 5 Comparisons of memetic algorithms with different replace strategy

4 結語

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

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