求解旅行商問(wèn)題的一種新方法

呂善國(guó)，曹義親，陳紅麗

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

旅行商問(wèn)題[1]（traveling salesman problems，TSP）是一個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，是指在給定了距離的城市集合中求解經(jīng)過(guò)所有城市恰好一次的最短回路，是一個(gè)典型的NP難問(wèn)題[2]。在VLSI芯片設(shè)計(jì)、機(jī)器人控制和車(chē)輛選路等許多領(lǐng)域有廣泛的應(yīng)用[3]。

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

因此，尋找一種高效的近似算法來(lái)求解旅行商問(wèn)題意義非常重大。通過(guò)對(duì)旅行商問(wèn)題的深入研究，本文提出了一種簡(jiǎn)化模型法SModel（simple model）來(lái)求解旅行商問(wèn)題。SModel方法在簡(jiǎn)化的網(wǎng)絡(luò)模型基礎(chǔ)上，對(duì)模型中的路徑進(jìn)行重構(gòu)得到旅行商問(wèn)題的解。

1 簡(jiǎn)化網(wǎng)絡(luò)的模型

1.1 符號(hào)定義

在對(duì)具體問(wèn)題進(jìn)行描述之前，先給出一些符號(hào)的定義。對(duì)于給定的圖G=(V,E,W)，其中：V為頂點(diǎn)集合，V＝{v i,i=1,…,n}，E為邊的集合，W為邊的權(quán)值集合。D(vi)和SD(vi)均表示節(jié)點(diǎn)vi的度，包括節(jié)點(diǎn)的入度和出度，區(qū)別在于D(vi)表示初始網(wǎng)絡(luò)中節(jié)點(diǎn)vi的度，而SD(vi)表示被處理過(guò)的網(wǎng)絡(luò)中節(jié)點(diǎn)vi的度；路徑表示從一個(gè)節(jié)點(diǎn)出發(fā)經(jīng)歷一系列節(jié)點(diǎn)最終到達(dá)某個(gè)節(jié)點(diǎn)的通路，兩個(gè)端節(jié)點(diǎn)的度為1，其余節(jié)點(diǎn)的度均為2；環(huán)路表示從一個(gè)節(jié)點(diǎn)出發(fā)經(jīng)歷一系列節(jié)點(diǎn)最終回到出發(fā)點(diǎn)的路徑，環(huán)路中所有節(jié)點(diǎn)的度均為2。

1.2 簡(jiǎn)化模型

簡(jiǎn)化初始圖的模型在一定的約束條件下把一個(gè)初始圖簡(jiǎn)化為邊的數(shù)量較少的圖，在簡(jiǎn)化網(wǎng)絡(luò)圖的基礎(chǔ)上，進(jìn)行路徑的選擇，構(gòu)建滿足要求的路徑。簡(jiǎn)化模型記為SModel，其詳細(xì)過(guò)程包括排序操作和選擇操作。

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

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

當(dāng)所有的邊都經(jīng)過(guò)測(cè)試后，剩下的邊與所有的節(jié)點(diǎn)可以構(gòu)成一個(gè)或多個(gè)子圖，子圖中絕大多數(shù)節(jié)點(diǎn)的度都為2，很少一部分節(jié)點(diǎn)的度為3或者更大的數(shù)字。構(gòu)建SModel的計(jì)算復(fù)雜度為O(eln(e))（其中，e為邊的數(shù)目）。

2 模型法求解TSP

初始圖轉(zhuǎn)化為SModel后，將對(duì)SModel中的節(jié)點(diǎn)和邊進(jìn)行一次遍歷。所有節(jié)點(diǎn)和邊的初始狀態(tài)置為0，一旦被遍歷過(guò)了，狀態(tài)由0轉(zhuǎn)化為1。

起始節(jié)點(diǎn)在度數(shù)大于2的節(jié)點(diǎn)中隨機(jī)選擇，記為vr。遍歷結(jié)點(diǎn)vr，狀態(tài)由0變?yōu)?；在狀態(tài)為0的邊集和結(jié)點(diǎn)集中選擇與vr相連的邊erj和鄰接點(diǎn)vj，且邊erj狀態(tài)由0變?yōu)?；將vj作為vr，重復(fù)上述過(guò)程，直到所有結(jié)點(diǎn)均被遍歷過(guò)或者找不到狀態(tài)為0的結(jié)點(diǎn)vr的鄰接點(diǎn)為止。

如果未遍歷完成且找不到狀態(tài)為0的結(jié)點(diǎn)vr的鄰接點(diǎn)，說(shuō)明發(fā)現(xiàn)了一個(gè)局部環(huán)。在整個(gè)遍歷過(guò)程中，可能存在大量的局部環(huán)。經(jīng)分析，所有的局部環(huán)分為兩類(lèi)，分別處理這兩類(lèi)局部環(huán)。

2.1 處理局部環(huán)

2.1.1 只有1個(gè)結(jié)點(diǎn)的度大于2的局部環(huán)

遍歷過(guò)程中發(fā)現(xiàn)局部環(huán)，若如圖1（a）所示，所有結(jié)點(diǎn)中只有1個(gè)結(jié)點(diǎn)的度大于2，這種類(lèi)型的環(huán)稱為Cycle1。在該環(huán)中，只有與結(jié)點(diǎn)vs相連的邊大于2，因此需要?jiǎng)h除一條與vs相連的邊。對(duì)應(yīng)Cycle1，破環(huán)方法如圖2（b，c，d）所示。

圖1 Cycle1的破環(huán)方法Fig.1 The broken ring methods of Cycle1

ve作為這個(gè)局部環(huán)中最后被遍歷的節(jié)點(diǎn)，vn標(biāo)記為僅次于vs被遍歷到的節(jié)點(diǎn)。對(duì)于圖1（b），如果ve與環(huán)中的某節(jié)點(diǎn)（p指針指向的節(jié)點(diǎn)）在初始圖中是相連的，同時(shí)，沿著遍歷方向的下一個(gè)節(jié)點(diǎn)與某個(gè)狀態(tài)為0的節(jié)點(diǎn)在初始圖中也相連，則可以刪除p指針指向的節(jié)點(diǎn)與其下一個(gè)節(jié)點(diǎn)之間的連邊和邊 ＜ve,vs＞，并加入新邊連接到狀態(tài)為0的結(jié)點(diǎn)v，新加入的邊狀態(tài)由0變?yōu)?，當(dāng)前節(jié)點(diǎn)變?yōu)樾录尤氲墓?jié)點(diǎn)，繼續(xù)遍歷；圖1（c）與圖1（b）的處理方法相似，把ve變?yōu)関n，p指向節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)按照逆遍歷方向選擇。如果仍然不能破壞局部環(huán)，就考慮圖1（d）所示的方法來(lái)解決。圖1（d）中，v0先于vs被遍歷。如果v0與此環(huán)中某節(jié)點(diǎn)在初始圖中相連，同時(shí)在p指向節(jié)點(diǎn)的遍歷方向的下一個(gè)節(jié)點(diǎn)與其他狀態(tài)為0的節(jié)點(diǎn)在初始圖中也相連，則新加入的狀態(tài)為0的節(jié)點(diǎn)變?yōu)楫?dāng)前節(jié)點(diǎn)，新加入的邊狀態(tài)由0變?yōu)?，繼續(xù)遍歷。

選擇狀態(tài)為0的新節(jié)點(diǎn)時(shí)要滿足總代價(jià)增量最小的原則，即增加的兩條邊的權(quán)值和與刪除的兩條邊的權(quán)值和的差值最小。

2.1.2 多于1個(gè)節(jié)點(diǎn)的度大于2的局部環(huán)

相對(duì)于類(lèi)型Cycle1，局部環(huán)中度大于2的節(jié)點(diǎn)數(shù)目多于1個(gè)的環(huán)稱為類(lèi)型Cycle2。在考慮結(jié)點(diǎn)之間是否可以連接時(shí)，首先計(jì)算度數(shù)大于2的結(jié)點(diǎn)，其破環(huán)方法與Cycle1的破環(huán)方法類(lèi)似。

不管是哪種類(lèi)型的局部環(huán)，如果其無(wú)法與其他狀態(tài)為0的節(jié)點(diǎn)相連，則把本次遍歷路徑中的所有節(jié)點(diǎn)和邊存儲(chǔ)到一個(gè)路徑集中，重新選擇下一次遍歷的初始節(jié)點(diǎn)。

2.2 對(duì)集中路徑的連接和調(diào)節(jié)

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

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

2.3 生成全局環(huán)

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

3 實(shí)驗(yàn)分析

求解TSP問(wèn)題的近似算法性能標(biāo)準(zhǔn)包括算法的運(yùn)行時(shí)間和解的質(zhì)量。通常以相對(duì)于最優(yōu)解的誤差為評(píng)價(jià)標(biāo)準(zhǔn)，計(jì)算公式如下

式中：R為解，Opt為最優(yōu)解。

以下給出在TSPLIB[15]的典型實(shí)例上進(jìn)行的測(cè)試結(jié)果，如表1所示。實(shí)例名稱中的數(shù)字表示實(shí)例的規(guī)模，如實(shí)例Eil51的規(guī)模為51。Opt是TSPLIB中的最優(yōu)解，即最短路徑值Min即最短路徑是簡(jiǎn)化模型法的最優(yōu)解與Opt的誤差，Avg是簡(jiǎn)化模型法的平均解與Opt的誤差，n是遍歷過(guò)程中發(fā)現(xiàn)的局部環(huán)數(shù)目。

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

表1 各實(shí)例測(cè)試結(jié)果Tab.1 Test results of examples

實(shí)驗(yàn)中每個(gè)實(shí)例至少運(yùn)行100次，從實(shí)驗(yàn)結(jié)果看出，測(cè)試實(shí)例的平均解與最優(yōu)解非常接近，這是由于從全局入手來(lái)構(gòu)造SModel，避免了陷入局部最優(yōu)的狀態(tài)。另外，簡(jiǎn)化模型法得到的最優(yōu)解與TSPLIB中的最優(yōu)解的誤差基本都小于10%，是可以接受的。值得注意的是，局部環(huán)的數(shù)目在一定程度上可以表示簡(jiǎn)化模型法的計(jì)算復(fù)雜度。

簡(jiǎn)化模型法解決TSP問(wèn)題的時(shí)耗小。實(shí)驗(yàn)中，對(duì)節(jié)點(diǎn)規(guī)模為1 000到5 000個(gè)節(jié)點(diǎn)的隨機(jī)網(wǎng)絡(luò)圖進(jìn)行了處理，其運(yùn)行時(shí)間與節(jié)點(diǎn)規(guī)模的關(guān)系如圖3所示。顯然，隨著節(jié)點(diǎn)規(guī)模的增加，運(yùn)行時(shí)間也會(huì)增加，但是增長(zhǎng)程度與線性曲線接近。

圖3 節(jié)點(diǎn)規(guī)模為1 000到5 000的時(shí)間消耗Fig.3 Time consumption from 1 000 to 5 000 nodes

4 總結(jié)

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

[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]萬(wàn)穎瑜，周智，陳國(guó)良，等.SizeScale：求解旅行商問(wèn)題（TSP）的新算法[J].計(jì)算機(jī)研究與發(fā)展，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]陳冬華.旅行商問(wèn)題推廣及其混合智能算法[J].華東交通大學(xué)學(xué)報(bào)，2011，28（2）：102-106.

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