基于最小調整法求解旅行商問題

費威

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

關鍵詞 旅行商問題；最小調整法；算法有效性

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

1 引 言

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

2 最小調整法求解TSP問題的思想和步驟

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

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

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

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

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

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

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

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

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

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

2.2 最小調整法求解TSP問題的思想步驟

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

設TSP問題的關系矩陣為C

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

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

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

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

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

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

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

2.3 最小調整法求解TSP問題算例

先求出相應指派問題的最優解，具體過程為：

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

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

調整的結果將導致目標函數值的增加.若每次對調都選擇增值最小的進行，當所有的子圈全被破掉后，即得原問題的一個更好的解.

此例中的最優解為：

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

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

此問題的最優解并不唯一，另一最優解求解過程為：

此即另一最優解且無需對調調整：1→2→3→5→4→1.該最優解僅通過最小調整法就可解得.

3 最小調整法求解TSP問題的有效性分析

3.1 關于最小對調的分析

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

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

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