冉令龍，李琳，鄭學東

（沈陽航空航天大學 a.理學院，b.計算機學院，沈陽 110136）

旅行商問題（travelling salesman problem，TSP）是組合優(yōu)化中典型的NP-hard問題［1］，在實際生活中有廣泛的應用，如：電網(wǎng)規(guī)劃、車輛調度和機器人控制等［2-3］。研究TSP問題的求解具有重要的意義。目前求解TSP問題的算法主要分為精確算法和啟發(fā)式算法兩類。精確算法有分支定界、線性規(guī)劃和動態(tài)規(guī)劃法等［4-5］。精確算法可求得小規(guī)模TSP問題最優(yōu)解，在處理大規(guī)模問題時，很難在有限時間內(nèi)得到問題的最優(yōu)解。隨著問題規(guī)模的增大，許多研究［6-8］多采用啟發(fā)式算法進行求解。啟發(fā)式算法包括蟻群算法（ant colony optimization，ACO）、遺傳算法（genetic algorithm，GA）、模擬退火算法（simulated annealing， SA）以及禁忌搜索算法等。TS作為一種啟發(fā)式算法，在求解函數(shù)優(yōu)化問題中表現(xiàn)出優(yōu)良的性能［9-11］，但同時也存在對初始解依賴較強的缺陷，好的初始解對TS算法求解有較大的幫助。

本文在基本禁忌搜索算法的基礎上，分別采用隨機生成初始解算法、改良圈算法（modi‐fied circle algorithm， ICA）、CW節(jié)約算法和貪婪算法（greedy algorithm）產(chǎn)生初始解，選擇4種算法中效果最佳的算法生成初始解，將其作為TS算法的初始解。在鄰域變換過程中，比較Insert鄰域、Swap鄰域和2-opt鄰域的計算效果，選擇計算效果最優(yōu)的鄰域結構。仿真實驗分別采用文獻［12］、 ［13］中的算例與標準TSPLIB數(shù)據(jù)庫中的算例進行計算，實驗結果驗證了本文算法的有效性。

1 TSP問題數(shù)學模型

TSP問題可描述為：假設有一個旅行商要訪問n座城市，各城市間距離已知，路徑限制是每個城市只能被訪問一次，旅行商從初始城市出發(fā)，在遍歷所有城市后，最后返回初始城市，求最短路徑的巡回方案。

TSP問題數(shù)學模型［14］如式（1）所示

式中：g（x）為路徑總長度；d（yi，yi+1）為第i個訪問城市到第i+1個訪問城市的距離；y=（y1，y2，…，yn）表示訪問城市的順序；n為訪問城市個數(shù)；1，2，…，n表示訪問城市序號。

TSP問題按其距離矩陣分為對稱和非對稱性TSP問題，本文研究對稱性TSP問題。

2 改進的禁忌搜索算法

TS算法是由美國科羅拉大學Fred Glover教授在1986年首次提出［15］。TS算法通過引入相應的禁忌表來避免重復搜索，并對禁忌區(qū)域中的一些優(yōu)良狀態(tài)進行特赦，避免算法陷入局部最優(yōu)，是一種全局迭代尋優(yōu)的算法。

TS算法具備強大的局部搜索能力和記憶功能，但其對初始解的依賴性較強，較好的初始解可使算法快速找到最優(yōu)解。為降低初始解對算法的影響，提高TS算法的計算效率，本文比較了隨機生成初始解算法、ICA算法、CW節(jié)約算法和貪婪算法4種方法生成初始解，將其中最好的初始解作為TS算法的初始解進行迭代，進而尋求最優(yōu)解。

ICA算法［16］求解TSP問題的基本思想是先隨機生成路徑，形成一個Hamilton圈，隨機交換Hamilton圈內(nèi)除起始點和終止點外的兩個點位置，若交換后的路徑總長度小于交換前的路徑總長度，接受此次交換，成功交換次數(shù)加1，更新最短路徑，直至成功交換次數(shù)達到設置的改良次數(shù)，結束搜索。ICA算法搜索隨機性不高，較難得到全局最優(yōu)解，易陷入局部最優(yōu)。因此，該算法常用于構造初始解，并結合相關啟發(fā)式算法求解TSP問題。

CW節(jié)約算法是Clark等17］提出的一種解決車輛路徑問題較為有效的啟發(fā)式算法，其求解TSP問題基本原理如下：生成一條只包含起始點和終止點的初始路徑，從所有需要訪問城市中隨機選擇一個城市插入到初始路徑中，計算剩余城市在所有可能插入位置的節(jié)約值，將節(jié)約值從大到小降序排列，把節(jié)約值最大的城市插入到最佳可行位置，直至車輛經(jīng)過所有需要訪問的城市后返回出發(fā)城市。

貪婪算法［18］生成TSP問題初始解的方法為從第一個城市出發(fā)，每次在沒有到達的城市中選擇距離最近的一個城市訪問，依次進行，直至經(jīng)過所有訪問城市，最后返回出發(fā)城市。

根據(jù)TSP問題的特點，本文設計了3種鄰域結構，從中選擇計算效果最佳的鄰域結構。

Insert鄰域：在生成的初始城市序列中隨機選擇兩個不同位置a和b，將位置a對應的城市插入位置b，記為Insert（a，b）；如生成初始城市序列R=［1， 5， 2， 4， 3， 6， 7］，隨機選取的城市為［5， 3］，則Insert鄰域變換如圖1所示。

圖1 Insert鄰域

Swap鄰域：在生成的初始城市序列中隨機選擇兩個不同位置a和b，將位置a和b對應的城市交換，記為Swap（a，b）；如生成初始城市序列R=［1， 5， 2， 4， 3， 6， 7］，隨機選取的城市為［5， 3］，則Swap鄰域變換如圖2所示。

圖2 Swap鄰域

2-opt鄰域：在生成的初始城市序列中隨機選擇兩個不同位置a和b，將位置a和b對應的城市交換，將位置a和b對應城市之間的所有城市進行倒序排列；如生成初始城市序列R=［1， 5， 2， 4， 3， 6， 7］，隨機選取城市為［5， 3］，則2-opt鄰域變換如圖3所示。

圖3 2-opt鄰域

改進的TS算法求解TSP的步驟如下：

步驟1：設置算法基本參數(shù)，即禁忌表長度為TL，候選解個數(shù)為K，最大迭代次數(shù)為Tmax；

步驟2：用隨機生成初始解算法、ICA算法、CW算法和貪婪算法生成初始解，選擇其中最優(yōu)的初始解，判斷它是否滿足終止條件：若滿足，則輸出最優(yōu)解，算法結束；否則，轉入步驟3；

步驟3：用Insert鄰域、Swap鄰域和2-opt鄰域結構產(chǎn)生鄰域解，選擇其中計算結果最優(yōu)的鄰域結構，在它生成的若干鄰域解中挑選K個候選解，計算目標值，選取結果較好的候選解；

步驟4：判斷候選解是否滿足特赦準則：若滿足，特赦候選解，更新當前最優(yōu)解，將其加入禁忌表，更新禁忌表；否則，選擇候選解中未被禁忌的最優(yōu)解作為當前最優(yōu)解，更新禁忌表；

步驟5：重復步驟3和步驟4，直至滿足程序終止條件，結束搜索。

改進的TS算法流程圖見圖4所示。

圖4 改進的TS算法流程圖

3 仿真實驗

仿真實驗分別采用了文獻［12］、［ 13］中的算例與標準TSPLIB數(shù)據(jù)庫中的算例，將本文算法的計算結果與算例中的實驗結果進行比較。本文算法用Python實現(xiàn)，在Window10操作系統(tǒng)，處理器為Inter（R）Core（TM）i7-7700（2.80Ghz），8 GB內(nèi)存的電腦上運行。

文獻［12］中的城市數(shù)為31，城市分布散點如圖5所示。

圖5 31座城市分布散點圖

3.1 本文算法參數(shù)設置

本文比較了在不同禁忌長度和候選集規(guī)模組合下的最優(yōu)解結果，并確定了禁忌長度和候選集規(guī)模的最優(yōu)參數(shù)。

3.1.1 禁忌長度的選擇

禁忌長度是禁忌搜索算法中的一個關鍵參數(shù)，作為放置在禁忌表中對象的禁忌周期，進行一次迭代，周期減少一次，直至周期為0時解除禁忌。禁忌長度的選擇影響最終最優(yōu)解的結果。文獻［12］的算例采用隨機生成初始解算法，設置K=200、N=100，采用2-opt鄰域變換。本文算法的禁忌長度分別為10、15、20、22，在不同禁忌長度下，重復運行3次程序，AVG為3次計算結果平均值，具體計算結果如表1所示，計算結果如圖6所示。

表1 本文算法禁忌長度選擇對比結果

圖6 禁忌長度選擇對比圖

從圖6可知，在其他參數(shù)固定的情況下，禁忌長度從10增大到20，計算結果逐漸減??；禁忌長度從20增大到22，計算結果相近。

從表1可得，當TL=22時，計算結果平均值最小，最短路徑平均長度為15 466。因此，在其他參數(shù)固定條件下，本文取TL=22。

3.1.2 候選集選擇

候選集從鄰域解中產(chǎn)生，隨機選擇幾個鄰域解或選表現(xiàn)較好的解作為候選解。本實驗設置TL=22、N=100，采用2-opt鄰域變換，設置候選解集個數(shù)分別為50、100、150和200。在不同候選解集下，重復運行3次程序，AVG為3次計算結果平均值，具體計算結果如表2和圖7所示。

表2 候選解選擇對比結果

圖7 候選集選擇對比圖

從表2可知，當K=200時，計算得到路徑最短距離平均值最小，最短路徑平均長度為15 466。因此，在其他參數(shù)固定條件下，本文將候選解的數(shù)量設置為200。由圖7可知，在其他參數(shù)固定時，候選集數(shù)量從50增大到200，所得最短距離逐漸減小。

3.2 初始解選擇

TS算法對初始解依賴性較強，好的初始解能提高算法計算效率。本文采用文獻［12］、［13］中算例，分別采用隨機生成初始解算法、ICA算法、CW節(jié)約算法和貪婪算法生成初始解，并選擇計算效果最佳算法作為本文算法初始解。

3.2.1 文獻［13］算例

文獻［13］中有21個客戶的位置坐標數(shù)據(jù)，本文算法設置參數(shù)TL=10，N=100，K=30，鄰域結構為2-opt，改良次數(shù)T=20，將不同算法得到初始解代入TS算法，重復運行5次實驗，其中AVG為5次計算結果的平均值，計算結果如表3所示。

表3 文獻［13］算例實驗結果

從表3可知，貪婪算法計算結果平均值最小，最短路徑平均長度為264.8，相較隨機生成初始解算法、ICA算法和CW節(jié)約算法最短路徑平均長度分別減少5.0、4.0和1.2。

3.2.2 文獻［12］算例

實驗采用文獻［12］中的31個城市數(shù)據(jù)坐標，設置參數(shù)TL=22、N=100、K=200、T=20，鄰域結構為2-opt，將不同算法得到初始解代入TS算法，重復運行5次實驗，其中AVG為5次計算結果的平均值，計算結果如表4所示。

表4 文獻［12］算例實驗結果

從表4可知，貪婪算法計算結果平均值最小，最短路徑平均長度為15 444，相較隨機生成初始解算法、ICA算法和CW節(jié)約算法最短路徑平均長度分別減少66、64和54。因此，本文選擇貪婪算法作為算法初始解。

3.3 鄰域結構

為增加解的多樣性，本文算法提出基于變鄰域搜索的干擾機制，比較了Insert鄰域、Swap鄰域和2-opt鄰域求解文獻［12］中算例的近優(yōu)解結果。設置TL=22、N=100、K=200，在不同鄰域結構下，重復運行5次實驗，AVG為5次計算結果平均值，計算結果如表5所示。

表5 不同鄰域算法結果

從表5可知，當鄰域結構為2-opt時，計算結果平均值最小，最短路徑平均長度為15 427，相較采用Insert鄰域和Swap鄰域所得最短路徑平均長度分別減少84和12。因此，本文選擇2-opt鄰域結構。

3.4 算例比較

本文采用文獻［12］數(shù)據(jù)和算法、TSPLIB數(shù)據(jù)庫中算例和結果來驗證本文算法的有效性。

3.4.1 文獻［12］算法與本文算法計算結果比較

為保證實驗結果的可靠性，本文算法參數(shù)設置與文獻［12］一致。設文獻［12］算法與本文算法最優(yōu)值分別為a和b，偏差率計算公式如式（2）所示

在迭代次數(shù)分別為100、500和1 000時，重復運行5次實驗，計算結果如表6所示。從表6可知，迭代次數(shù)為100、500和1 000時，本文算法計算結果均優(yōu)于文獻［12］算法計算結果。在求解精度上，本文算法與文獻［12］算法相比有很大的提高。迭代次數(shù)從100增加到1000，偏差率逐漸減小。當?shù)螖?shù)為1 000時，本文算法計算結果最優(yōu)，最短路徑長度為15 382。最短路徑方案如圖8所示，迭代次數(shù)與最優(yōu)解變化關系如圖9所示。

表6 文獻［12］與本文算法計算結果比較

圖8 本文算法最短路線方案

圖9 迭代次數(shù)與最優(yōu)解變化關系圖

3.4.2 TSPLIB數(shù)據(jù)庫算例與本文算法計算結果的比較

本文采用TSPLIB數(shù)據(jù)庫中的Dantzig42、Berlin52、St70進行算例測試，重復運行5次實驗，其中n為城市數(shù)量，AVG為5次計算結果平均值，opt為本文算法最優(yōu)值，ref為TSPLIB參考值，計算結果如表7所示。參考值為TSPLIB數(shù)據(jù)庫中相應最優(yōu)值，偏差率計算方法如式（3）所示

表7 TSPLIB最優(yōu)解與本文算法實驗結果比較

從表7可知，本文算法計算Dantzig42實例的最優(yōu)解達到TSLIB標準庫的最優(yōu)解。Ber‐lin52和St70實例的最優(yōu)解與TSPLIB標準庫中的最優(yōu)解相比，偏差率在3%以內(nèi)，本文算法在小規(guī)模案例下，計算結果較為理想。

4 結論

本文針對TSP問題的特點，通過隨機生成初始解算法、ICA算法、CW節(jié)約算法和貪婪算法生成初始解，選擇計算結果最優(yōu)的貪婪算法對TS算法的初始解進行優(yōu)化，提出一種改進的禁忌搜索算法。仿真實驗中，通過不同情況下參數(shù)比較，確定禁忌長度和候選集的最優(yōu)參數(shù)。仿真實驗結果表明：相較文獻［12］中算法的最優(yōu)解，本文算法的最優(yōu)解更接近全局最優(yōu)解，說明本文算法能夠有效解決TSP問題。在與TSPLIB標準庫算例比較中，本文算法在小規(guī)模算例中計算結果與TSPLB標準庫參考值之間的偏差率不超過3%，驗證了本文算法求解TSP問題的有效性和可行性。