基于最小調(diào)整法求解旅行商問題

費威

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

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

中圖分類號 O221.4 文獻標識碼 A

1 引 言

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

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

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

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

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

2.1 TSP問題與指派問題的異同

對比指派問題和TSP問題，它們有如下異同點：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

因此，旅行商問題的最短路線為：1→4→5→3→2→1，最短路線長為f=20.

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

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

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

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

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

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

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

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