費(fèi)威

摘 要 介紹了一種求解旅行商問(wèn)題的新算法“最小調(diào)整法”，給出了該算法求解旅行商問(wèn)題的具體步驟以及有效性證明，對(duì)算法的復(fù)雜性及近似程度進(jìn)行了分析.最后通過(guò)典型算例進(jìn)行了檢驗(yàn)說(shuō)明.與經(jīng)典算法相比，新算法體現(xiàn)了簡(jiǎn)單易行的特點(diǎn)，對(duì)求解旅行商問(wèn)題具有一定的啟發(fā)意義.

關(guān)鍵詞 旅行商問(wèn)題；最小調(diào)整法；算法有效性

中圖分類號(hào) O221.4 文獻(xiàn)標(biāo)識(shí)碼 A

1 引 言

旅行商問(wèn)題（Traveling Salesman Problem，簡(jiǎn)稱TSP）是著名的組合優(yōu)化問(wèn)題[1].經(jīng)典的TSP問(wèn)題可描述為：設(shè)有n個(gè)城市1，…，n，由i城市到j(luò)城市的路程dij已知，一個(gè)旅行商為了推銷貨物，從某一城市出發(fā)，如何選擇一條最優(yōu)路線可以經(jīng)過(guò)所有其他城市，且每個(gè)城市正好經(jīng)過(guò)一次，然后回到出發(fā)點(diǎn).容易看出，旅行商有（n-1）！種方案可供選擇.即使n是較小的兩位數(shù)，這類問(wèn)題仍沒(méi)有較好的有效算法，因此被稱為NPcomplete問(wèn)題.但是TSP問(wèn)題在組合優(yōu)化問(wèn)題中具有廣泛實(shí)際背景和深刻經(jīng)濟(jì)含義.例如，在計(jì)算機(jī)的集成電路設(shè)計(jì)中就出現(xiàn)了這一問(wèn)題，還包括派車(chē)、排序、底板布線、考古學(xué)中的排號(hào)、自動(dòng)鉆井、工件加工順序和郵局收發(fā)信件等其他許多方面，所有這些需要促使學(xué)者們不斷地研究TSP問(wèn)題的算法[2].目前國(guó)內(nèi)外求解TSP問(wèn)題的較好算法有遺傳算法、神經(jīng)網(wǎng)絡(luò)算法、模擬退火算法、蟻群算法和粒子群算法等[3-7]，這些算法中遺傳算法具有較好的全局搜索能力，但優(yōu)化過(guò)程緩慢，結(jié)果準(zhǔn)確度不高；粒子群算法局部搜索能力較弱；蟻群算法等存在計(jì)算速度較慢等缺點(diǎn).因此，以這些算法為基礎(chǔ)，較多學(xué)者相繼提出了改進(jìn)的算法以更好地求解TSP問(wèn)題[8-13].

2 最小調(diào)整法求解TSP問(wèn)題的思想和步驟

最小調(diào)整法[14]是以Dijkstra算法[15]為實(shí)現(xiàn)途徑的一種多項(xiàng)式算法.本文根據(jù)最小調(diào)整法，給出了求解TSP問(wèn)題的一種新的有效啟發(fā)式算法.該算法較

之以往常用的啟發(fā)式算法更加簡(jiǎn)單易行，計(jì)算量?jī)H為O（n2），并且由此得到的近似解一般更接近最優(yōu)解.

下面首先根據(jù)指派問(wèn)題和TSP問(wèn)題的異同點(diǎn)比較，然后提出將TSP問(wèn)題先看做指派問(wèn)題利用最小調(diào)整法求解[16]的具體步驟.

2.1 TSP問(wèn)題與指派問(wèn)題的異同

對(duì)比指派問(wèn)題和TSP問(wèn)題，它們有如下異同點(diǎn)：

第一，指派問(wèn)題中，第i項(xiàng)任務(wù)可以由第i人去完成，因此其解可以在效率矩陣（成本）矩陣的主對(duì)角線上；但TSP問(wèn)題中不存在從Ai城市到Ai城市的情況，其解顯然不會(huì)出現(xiàn)在距離矩陣的主對(duì)角線上，即有i≠j的約束條件.

第二，對(duì)于有n個(gè)人的指派問(wèn)題，其解由n項(xiàng)任務(wù)所組成，這些任務(wù)在效率矩陣中既不同行又不同列；對(duì)于有n個(gè)城市的TSP問(wèn)題，其解由n段行程構(gòu)成，這些行程在距離矩陣中既不同行又不同列.

第三，xij=1或0表示指派問(wèn)題的解，則效率矩陣任一行、任一列的效率參數(shù)之和均為1，即∑ni=1xij=1且∑nj=1xij=1（i，j=1，…，n），即每個(gè)任務(wù)只有一個(gè)人承擔(dān)，每個(gè)人只能承擔(dān)一項(xiàng)任務(wù).TSP問(wèn)題中∑ni=1xij=1且∑nj=1xij=1（i，j=1，…，n），即在回路上僅由1個(gè)城市出發(fā)至第j個(gè)城市；從第i個(gè)城市出發(fā)僅通往1個(gè)城市，即所有中間城市僅通過(guò)一次.

第四，指派問(wèn)題不存在回路問(wèn)題，但TSP問(wèn)題解的各段行程首尾相接，必然構(gòu)成一個(gè)回路.

通過(guò)比較指派問(wèn)題和TSP問(wèn)題的特點(diǎn)，上述第一和第四點(diǎn)說(shuō)明指派問(wèn)題與TSP問(wèn)題有區(qū)別，第二和第三點(diǎn)則是相同的.如果置TSP問(wèn)題原始距離矩陣主對(duì)角線元素為一個(gè)相當(dāng)大的正數(shù)M或記為“×”時(shí)，把TSP問(wèn)題當(dāng)作指派問(wèn)題去求解，這種指派問(wèn)題就具備了TSP問(wèn)題的第一和第四點(diǎn)中某些特點(diǎn)了，然后再對(duì)該解檢驗(yàn)其作為T(mén)SP問(wèn)題的可行性.

2.2 最小調(diào)整法求解TSP問(wèn)題的思想步驟

若把帶權(quán)完全圖G當(dāng)前結(jié)點(diǎn)當(dāng)成任務(wù)的承擔(dān)者，另外結(jié)點(diǎn)當(dāng)成任務(wù)，邊的權(quán)（城市間距離）為完成任務(wù)所用時(shí)間，則尋求最優(yōu)Hamilton回路[14，15]是把圖中結(jié)點(diǎn)怎樣與別的結(jié)點(diǎn)進(jìn)行單一指派，使每個(gè)結(jié)點(diǎn)既是一個(gè)結(jié)點(diǎn)的任務(wù)承擔(dān)者，又是另一個(gè)結(jié)點(diǎn)的任務(wù)，這種指派使完成任務(wù)時(shí)間最短以及滿足這些指派所確定的路徑（旅行商走過(guò)的路徑即指派路徑）構(gòu)成一個(gè)回路的條件.指派路徑構(gòu)成一個(gè)回路是在一般指派問(wèn)題中增加的條件.

設(shè)TSP問(wèn)題的關(guān)系矩陣為C

其中元素cij表示由第i城市到第j城市的距離.

步驟1 取每列的一個(gè)最小值畫(huà)圈，即得到一個(gè)最小方案.若這些畫(huà)圈元素又分屬于不同行，則得到相應(yīng)指派問(wèn)題的最優(yōu)解，轉(zhuǎn)步驟3；否則轉(zhuǎn)步驟2.

步驟2 應(yīng)把有兩個(gè)或兩個(gè)以上畫(huà)圈元素行中的一個(gè)改畫(huà)到同列別處，待到某一無(wú)圈行中有一元素畫(huà)上圈，則算一次調(diào)整.如此進(jìn)行，直到每行均有一個(gè)畫(huà)圈元素時(shí)為止，然后轉(zhuǎn)入步驟3即可.而每次調(diào)整均以目標(biāo)函數(shù)（其值為各畫(huà)圈元素之和）增值最小為原則.

步驟3 如果從步驟1或2得到的指派問(wèn)題最優(yōu)解元素的任一行指標(biāo)i出發(fā)，先到其列指標(biāo)j為下一行指標(biāo)的元素出發(fā)，再到其列指標(biāo).如此進(jìn)行下去，最后回到以i為列指標(biāo)的元素，便形成一個(gè)圈.若圈中的元素恰為n個(gè)，則所得方案即為最優(yōu)方案；否則便會(huì)形成兩個(gè)或兩個(gè)以上的子圈，它不是最優(yōu)解，需進(jìn)行再調(diào)整，轉(zhuǎn)步驟4.

步驟4 以增值最小的原則實(shí)行對(duì)調(diào)調(diào)整.所謂對(duì)調(diào)調(diào)整，就是在任意兩個(gè)子圈中各取一個(gè)元素，如cij與cst，交換它們的列標(biāo)號(hào)，變成cit與csj，其結(jié)果是這兩個(gè)子圈便合成一個(gè)圈，該變化如圖1所示

由圖1可知，這4個(gè)元素形成一個(gè)矩形，調(diào)整是把矩形原先對(duì)角線上的兩個(gè)畫(huà)圈元素cij與cst的圈轉(zhuǎn)給了另一對(duì)角線上的兩個(gè)畫(huà)圈元素cit與csj.顯然經(jīng)過(guò)調(diào)整，目標(biāo)函數(shù)將增加為Δf=（cit+csj）-（cij+cst）.考慮所有可能的對(duì)調(diào)調(diào)整，取其中增值最小的，加以調(diào)整，便破掉一圈.如此進(jìn)行，直到無(wú)子圈為止.

破圈所說(shuō)的“圈”指的是歐拉圈，它可以分為廣義的和狹義的兩種：在n個(gè)城市的TSP問(wèn)題中，廣義的圈可以由n個(gè)城市任選兩個(gè)以上的城市任意排列構(gòu)成；而狹義的圈則被嚴(yán)格規(guī)定為指派問(wèn)題最優(yōu)解即xij=1所在位置，也就是最優(yōu)解中的畫(huà)圈元素所構(gòu)成的回路.狹義的圈在討論TSP問(wèn)題時(shí)被簡(jiǎn)稱為“圈”.因此，此處可以將“圈”定義為用指派問(wèn)題最優(yōu)解所確定的，從一個(gè)城市到另一些城市，然后再返回到那個(gè)城市的一個(gè)閉合回路.對(duì)于大規(guī)模問(wèn)題，求最短調(diào)整路線可用標(biāo)號(hào)算法，

2.3 最小調(diào)整法求解TSP問(wèn)題算例

先求出相應(yīng)指派問(wèn)題的最優(yōu)解，具體過(guò)程為：

以此例的指派問(wèn)題最優(yōu)解為c13，c32，c21，c45，c54，轉(zhuǎn)步驟3.檢驗(yàn)結(jié)果此方案形成兩個(gè)子圈：（c13，c32，c21）和（c45，c54）如圖2（a）和（b）.

容易看出在兩個(gè)子圈中任意各取一個(gè)元素，交換它們的列下標(biāo)，則這兩個(gè)圈便合成一個(gè)圈.例如將圖2（a）的c13與（b）的c45的列下標(biāo)對(duì)調(diào)或交換便成為：c15，c54，c43，c32，c21.于是便破掉一個(gè)圈，此例經(jīng)處理便得到一個(gè)可行方案.上述處理相當(dāng)于若把分屬于不同圈中的兩元素看成為矩形一對(duì)角線的二頂點(diǎn)，則其圈調(diào)換給了該矩形另外一條對(duì)角線的兩個(gè)頂點(diǎn)對(duì)應(yīng)的元素，即：

調(diào)整的結(jié)果將導(dǎo)致目標(biāo)函數(shù)值的增加.若每次對(duì)調(diào)都選擇增值最小的進(jìn)行，當(dāng)所有的子圈全被破掉后，即得原問(wèn)題的一個(gè)更好的解.

此例中的最優(yōu)解為：

因此，旅行商問(wèn)題的最短路線為：1→4→5→3→2→1，最短路線長(zhǎng)為f=20.

此例還有其他多種破圈方案在此不再累述.在最小調(diào)整最優(yōu)方案的基礎(chǔ)上實(shí)施對(duì)調(diào)調(diào)整可在圖中直接完成，以上例兩個(gè)圈進(jìn)行說(shuō)明：即以一個(gè)圈中的畫(huà)圈元素與另一個(gè)圈的每個(gè)畫(huà)圈元素連線，以該線為對(duì)角線的矩形的另兩個(gè)頂點(diǎn)元素即交叉對(duì)角線的兩個(gè)頂點(diǎn)元素，計(jì)算這兩個(gè)元素之和與原畫(huà)圈兩個(gè)頂點(diǎn)元素之和的差，若為0則該對(duì)調(diào)調(diào)整就是最優(yōu)調(diào)整；若不為0，繼續(xù)將該圈中其他畫(huà)圈元素仿此處理，最后取差值最小的進(jìn)行對(duì)調(diào)調(diào)整.若最小調(diào)整法的最優(yōu)方案形成兩個(gè)以上的圈，也可按照上述兩兩圈分別進(jìn)行對(duì)調(diào)調(diào)整差值計(jì)算比較，并進(jìn)行對(duì)調(diào)調(diào)整，直至最終形成一個(gè)圈為止.

此問(wèn)題的最優(yōu)解并不唯一，另一最優(yōu)解求解過(guò)程為：

此即另一最優(yōu)解且無(wú)需對(duì)調(diào)調(diào)整：1→2→3→5→4→1.該最優(yōu)解僅通過(guò)最小調(diào)整法就可解得.

3 最小調(diào)整法求解TSP問(wèn)題的有效性分析

3.1 關(guān)于最小對(duì)調(diào)的分析

給定TSP問(wèn)題的矩陣C，考慮以指派問(wèn)題作為它的松弛問(wèn)題.記指派問(wèn)題的解為：itjt=1，t=1，…，n，其余ij=0（也可記：ci1j1，ci2j2，…，cinjn），相應(yīng)最優(yōu)值為

按下述行列銜接規(guī)則排列（1）中的元素：任取一元素citjt排在首位，若其行標(biāo)為it列標(biāo)為jt，則將以jt為行標(biāo)的元素排在其后，使得每一元素的列標(biāo)都是緊接其后元素的行標(biāo)，直到以it為列標(biāo)的元素排上為止.易見(jiàn)，如果上述排列所經(jīng)歷的元素恰為n個(gè)，則指派問(wèn)題的解即為T(mén)SP的最優(yōu)解，TSP的最優(yōu)值也是式（1），而上述排列過(guò)程正好給出最優(yōu)路線.若排列所經(jīng)元素個(gè)數(shù)k

ci1i2，ci2i3，…，citit+1，…，ciki1