求解旅行商問題的一種新方法

呂善國，曹義親，陳紅麗

（華東交通大學軟件學院，江西南昌330013）

旅行商問題[1]（traveling salesman problems，TSP）是一個經典的組合優化問題，是指在給定了距離的城市集合中求解經過所有城市恰好一次的最短回路，是一個典型的NP難問題[2]。在VLSI芯片設計、機器人控制和車輛選路等許多領域有廣泛的應用[3]。

求解該類問題可以使用精確算法，常用的方法包括：分枝定界法[4]、線性規劃法[5]和動態規劃法[6]等，能保證得到最優解，但計算復雜度隨著網絡規模的增大呈指數增長，是NP困難的。當網絡達到一定規模時，通常使用近似算法或啟發式算法求解TSP。近似算法是把誤差控制在一定范圍的前提下快速得到解決方案，包括構造型算法和改進型算法。構造型算法從某個非法解開始，按一定規則一次性的構造一個合法解；而改進型算法在給定的初始合法解上逐步改進，是一種迭代法。近似算法主要有遺傳算法[7]、蟻群算法[8]、模擬退火算法[9]、人工神經網絡[10]、LK算法[11]、人工免疫算法[12]、粒子群優化算法[13]和混合智能算法[14]等。

因此，尋找一種高效的近似算法來求解旅行商問題意義非常重大。通過對旅行商問題的深入研究，本文提出了一種簡化模型法SModel（simple model）來求解旅行商問題。SModel方法在簡化的網絡模型基礎上，對模型中的路徑進行重構得到旅行商問題的解。

1 簡化網絡的模型

1.1 符號定義

在對具體問題進行描述之前，先給出一些符號的定義。對于給定的圖G=(V,E,W)，其中：V為頂點集合，V＝{v i,i=1,…,n}，E為邊的集合，W為邊的權值集合。D(vi)和SD(vi)均表示節點vi的度，包括節點的入度和出度，區別在于D(vi)表示初始網絡中節點vi的度，而SD(vi)表示被處理過的網絡中節點vi的度；路徑表示從一個節點出發經歷一系列節點最終到達某個節點的通路，兩個端節點的度為1，其余節點的度均為2；環路表示從一個節點出發經歷一系列節點最終回到出發點的路徑，環路中所有節點的度均為2。

1.2 簡化模型

簡化初始圖的模型在一定的約束條件下把一個初始圖簡化為邊的數量較少的圖，在簡化網絡圖的基礎上，進行路徑的選擇，構建滿足要求的路徑。簡化模型記為SModel，其詳細過程包括排序操作和選擇操作。

1）排序操作。對于一個圖G=(V,E,W)，把E中所有邊按照權值從大到小排列，排序后的邊存儲在一個集合SortEdgeArray中。

2）選擇操作。所有排序后的邊按照先后順序進行測試。對于任一條邊 ＜vi,vj＞，如果滿足式（1）的限制，＜vi,vj＞將從SortEdgeArray中刪除，同時，D(vi)和D(vj)都將減1。

當所有的邊都經過測試后，剩下的邊與所有的節點可以構成一個或多個子圖，子圖中絕大多數節點的度都為2，很少一部分節點的度為3或者更大的數字。構建SModel的計算復雜度為O(eln(e))（其中，e為邊的數目）。

2 模型法求解TSP

初始圖轉化為SModel后，將對SModel中的節點和邊進行一次遍歷。所有節點和邊的初始狀態置為0，一旦被遍歷過了，狀態由0轉化為1。

起始節點在度數大于2的節點中隨機選擇，記為vr。遍歷結點vr，狀態由0變為1；在狀態為0的邊集和結點集中選擇與vr相連的邊erj和鄰接點vj，且邊erj狀態由0變為1；將vj作為vr，重復上述過程，直到所有結點均被遍歷過或者找不到狀態為0的結點vr的鄰接點為止。

如果未遍歷完成且找不到狀態為0的結點vr的鄰接點，說明發現了一個局部環。在整個遍歷過程中，可能存在大量的局部環。經分析，所有的局部環分為兩類，分別處理這兩類局部環。

2.1 處理局部環

2.1.1 只有1個結點的度大于2的局部環

遍歷過程中發現局部環，若如圖1（a）所示，所有結點中只有1個結點的度大于2，這種類型的環稱為Cycle1。在該環中，只有與結點vs相連的邊大于2，因此需要刪除一條與vs相連的邊。對應Cycle1，破環方法如圖2（b，c，d）所示。

圖1 Cycle1的破環方法Fig.1 The broken ring methods of Cycle1

ve作為這個局部環中最后被遍歷的節點，vn標記為僅次于vs被遍歷到的節點。對于圖1（b），如果ve與環中的某節點（p指針指向的節點）在初始圖中是相連的，同時，沿著遍歷方向的下一個節點與某個狀態為0的節點在初始圖中也相連，則可以刪除p指針指向的節點與其下一個節點之間的連邊和邊 ＜ve,vs＞，并加入新邊連接到狀態為0的結點v，新加入的邊狀態由0變為1，當前節點變為新加入的節點，繼續遍歷；圖1（c）與圖1（b）的處理方法相似，把ve變為vn，p指向節點的下一個結點按照逆遍歷方向選擇。如果仍然不能破壞局部環，就考慮圖1（d）所示的方法來解決。圖1（d）中，v0先于vs被遍歷。如果v0與此環中某節點在初始圖中相連，同時在p指向節點的遍歷方向的下一個節點與其他狀態為0的節點在初始圖中也相連，則新加入的狀態為0的節點變為當前節點，新加入的邊狀態由0變為1，繼續遍歷。

選擇狀態為0的新節點時要滿足總代價增量最小的原則，即增加的兩條邊的權值和與刪除的兩條邊的權值和的差值最小。

2.1.2 多于1個節點的度大于2的局部環

相對于類型Cycle1，局部環中度大于2的節點數目多于1個的環稱為類型Cycle2。在考慮結點之間是否可以連接時，首先計算度數大于2的結點，其破環方法與Cycle1的破環方法類似。

不管是哪種類型的局部環，如果其無法與其他狀態為0的節點相連，則把本次遍歷路徑中的所有節點和邊存儲到一個路徑集中，重新選擇下一次遍歷的初始節點。

2.2 對集中路徑的連接和調節

當SModel遍歷完成，路徑集中的路徑數目通常大于1。如果不同路徑中的端節點是可連接的，則這兩條路徑可以連接為一條路徑。連接方法如圖2（a，b）所示，節點va，vn，vi和vk都是不同路徑中的端節點，對于圖2（a），如果某路徑的一個端節點與另一條路徑中的中間節點（圖2（a）中為vc）是可連接的，而此中間節點的鄰居節點（圖2（a）中為vb）與其另一端的端節點vn是相連的，則這兩條路徑可以合并為一條路徑。對于圖2（b），如果一條路徑的兩個端節點與另一條路徑中相鄰的兩個節點分別相連（vi與vc相連，vk與vd相連，vi和vk是一條路徑的兩個端點，vc和vd在另一條路徑中相鄰），則這兩條路徑可以合并為一條。

重復上面的操作，直到所有路徑合并為一條，稱其為全局路徑。

2.3 生成全局環

如圖2（c）所示，vb與vc為鄰居節點，vb與端點va在同一側，vc與vk也在同一側，如果一對鄰居節點分別與不同側的端節點相連，則全局路徑可以轉換為全局環。例如，vc與va相連，vb與vk相連，增加邊＜vb,vk＞ ，＜va,vc＞ ，刪除邊 ＜vb,vc＞ ，則完成所有操作。增加和刪除邊的操作要遵循最小增量原則。

3 實驗分析

求解TSP問題的近似算法性能標準包括算法的運行時間和解的質量。通常以相對于最優解的誤差為評價標準，計算公式如下

式中：R為解，Opt為最優解。

以下給出在TSPLIB[15]的典型實例上進行的測試結果，如表1所示。實例名稱中的數字表示實例的規模，如實例Eil51的規模為51。Opt是TSPLIB中的最優解，即最短路徑值Min即最短路徑是簡化模型法的最優解與Opt的誤差，Avg是簡化模型法的平均解與Opt的誤差，n是遍歷過程中發現的局部環數目。

圖2 處理路徑的方法Fig.2 The method of dealing with path

表1 各實例測試結果Tab.1 Test results of examples

實驗中每個實例至少運行100次，從實驗結果看出，測試實例的平均解與最優解非常接近，這是由于從全局入手來構造SModel，避免了陷入局部最優的狀態。另外，簡化模型法得到的最優解與TSPLIB中的最優解的誤差基本都小于10%，是可以接受的。值得注意的是，局部環的數目在一定程度上可以表示簡化模型法的計算復雜度。

簡化模型法解決TSP問題的時耗小。實驗中，對節點規模為1 000到5 000個節點的隨機網絡圖進行了處理，其運行時間與節點規模的關系如圖3所示。顯然，隨著節點規模的增加，運行時間也會增加，但是增長程度與線性曲線接近。

圖3 節點規模為1 000到5 000的時間消耗Fig.3 Time consumption from 1 000 to 5 000 nodes

4 總結

本文提出了一種求解旅行商問題的新方法。新算法對初始網絡進行簡化得到簡化模型（SModel），然后處理模型中的局部環，刪除冗余的邊，生成多條路徑，再對生成的路徑進行重構，最終得到滿足要求的全局環路。在TSPLIB中典型實例上的實驗結果表明，該算法在求解速度和求解能力方面都能得到比較令人滿意的結果。

[1]LAWLER E L，LENSTRA J K，RINNOOY KAN A H G，et al.The traveling salesman problem[M].Chichester：John Wiley&Sons，1985：51-78.

[2]GAREY M R，JOHNSON D S.Computers and intractability：a guide to the theory of NP-Completeness[M].San Francisco：W H Freeman，1979：25-30.

[3]萬穎瑜，周智，陳國良，等.SizeScale：求解旅行商問題（TSP）的新算法[J].計算機研究與發展，2002，39（10）：1294-1302.

[4] CARPANETO G，TOTH P.Some new branching and bounding criteria for the asymmetric traveling salesman problem[J].Management Science，1980，26（7）：736-743.

[5]G DANTZIG，R FULKERSON，S JOHNSON.Solution of a large scale traveling salesman problem[J].Operations Research，1954，2（4）：393-410.

[6]BELLMAN R.Dynamic programming treatment of the traveling salesman problem[J].JACM，1962（9）：61-63.

[7]SU F，ZHU F，YIN Z，et al.New crossover operator of genetic algorithms for the TSP[C]//Yu lean.International Joint Conference on Computational Sciences and Optimization.Jinan，China：IEEE Computer Society，2009：666-669.

[8] ZHOU Y.Runtime Analysis of an ant colony optimization algorithm for TSP instances[J].IEEE Transactions on Evolutionary Computation，2009，13（5）：1083-1092.

[9]SONG C，LEE K.Extended simulated annealing for augmented TSP and multi-salesmen TSP[C]//Don Wunsch，Michael Hasselmo，et al.Proceedings of the International Joint Conference on Neural Networks.Portland，Oregon：IEEE Neural Networks Society，2003：2340-2343.

[10] ABDEL-MOETTY S.Traveling salesman problem using neural network techniques[C]//Ahmed Zoweil，Dokki，Giza.The 7th International Conference on Informatics and Systems.Cairo，Egypt：IEEE Conference Publications Program，2010：1-6.

[11]LIN S，KERNIGHAN B.An effective heuristic algorithm for the traveling salesman problem[J].Operation Research，1973，21（2）：486-515.

[12] HUNT J，COOKE D.Learning using an artificial immune system[J].Journal of Network and Computer Applications，1996，19（2）：189-212.

[13]JAMES K，EBERHART R.Adiscrete binary version of the particle swarm algorithm[J].Proceeding of the IEEE International Conference on Systems，Man and Cybernetics，1997（5）：4104-4108.

[14]陳冬華.旅行商問題推廣及其混合智能算法[J].華東交通大學學報，2011，28（2）：102-106.

[15]REINELT G，TSPLIB.Atravelling salesman problem library[J].ORSAJournal of Computer，1991，3（4）：376-384.