余 麗，陸 鋒，楊 林

1.中國科學(xué)院 地理科學(xué)與資源研究所 資源與環(huán)境信息系統(tǒng)國家重點實驗室，北京100101；2.中國科學(xué)院大學(xué)，北京100101；3.中國地質(zhì)大學(xué) 信息工程學(xué)院，湖北 武漢430074；4.地理信息工程國家重點實驗室，陜西 西安710054

1 引 言

交通網(wǎng)絡(luò)旅行商路徑優(yōu)化問題（traveling salesman problem，TSP）旨在尋找由起點出發(fā)，有且僅有一次地通過給定點，再回到起點的成本最小的路徑，它是最短路徑算法應(yīng)用的具體體現(xiàn)，也是主流GIS基礎(chǔ)軟件平臺網(wǎng)絡(luò)分析的重要功能之一［1－3］。TSP已經(jīng)被證明是NP難題，多采用啟發(fā)式算法求解，可分為構(gòu)造型［4］和改進型［5］兩類。構(gòu)造型方法的基本思想是直接從距離矩陣中產(chǎn)生一個近似最優(yōu)解，典型算法包括最近鄰法、貪心法、插入法、Clarke－Wright算法等，該類方法實現(xiàn)簡單、運行效率高，但對位置分布特殊的節(jié)點集求解質(zhì)量很差。改進型方法的基本思想是不斷改善給定的可行路徑以尋找更優(yōu)解，典型算法包括局部搜索算法和智能優(yōu)化算法。其中，LKH算法［6］是目前精度最高的近似算法，但效率很低；遺傳算法［7］具有較強的全局尋優(yōu)能力，但進化后期收斂速度緩慢；模擬退火算法［8］具有漸進的收斂性，可依概率收斂到全局最優(yōu)解，但對初始參數(shù)的設(shè)置較為敏感；禁忌搜索算法［9］具有較強的局部尋優(yōu)能力，但對初始解和鄰域結(jié)構(gòu)的依賴性很強；蟻群算法［10］的結(jié)果不依賴于初始路徑的選擇，但因初期缺乏信息素限制了算法的收斂效率。

盡管目前對于小規(guī)模的TSP，精確型算法［11］已能夠計算出全局最優(yōu)解；而對于上百萬的大規(guī)模TSP，啟發(fā)式算法也能夠快速獲得近似最優(yōu)解，但是這些算法并未考慮交通網(wǎng)絡(luò)TSP的應(yīng)用場景，大多使用歐氏距離計算最優(yōu)回路。由于交通網(wǎng)絡(luò)的TSP求解可能會考慮動態(tài)路況和交叉口耗費的影響，計算最優(yōu)回路使用的是網(wǎng)路距離或出行時間，二者與歐氏距離之間不存在線性單調(diào)關(guān)系。因此，歐氏距離下的最優(yōu)回路難以滿足交通網(wǎng)絡(luò)TSP路徑規(guī)劃需求。

綜上所述，單一智能優(yōu)化方法雖各有優(yōu)勢，但由于運算量過大，參數(shù)選擇苛刻，對初值的依賴性強，很難快速實現(xiàn)全局優(yōu)化。目前TSP研究的重點集中在結(jié)合多種優(yōu)化機制和鄰域搜索結(jié)構(gòu)設(shè)計混合啟發(fā)式算法［12－13］，以拓展算法的適用域、提高全局優(yōu)化效果。此外，控制TSP算法的效率和精度的平衡，是目前TSP算法設(shè)計的核心難題。鑒于此，本文結(jié)合遺傳算法良好的全局尋優(yōu)能力和禁忌搜索獨具特色的記憶功能來求解TSP，以期獲得尋優(yōu)能力強、運行效率高、結(jié)果穩(wěn)定性好的TSP解決方案。

2 算法設(shè)計思想

禁忌搜索（tabu search，TS）［14］是一種模擬人腦短期記憶功能的全局逐步尋優(yōu)方法，它使用禁忌準則來避免無效的循環(huán)計算，同時采用藐視準則接受差解，以保證對不同范圍有效路徑的探測，具有較強的局部搜索能力。

遺傳算法（genetic algorithm，GA）［15］是一種適用于求解大規(guī)模多目標函數(shù)全局優(yōu)化問題的方法，可從解空間的多點出發(fā)進行自我學(xué)習(xí)式的廣泛探索，具有很強的全局尋優(yōu)能力。

在標準禁忌搜索算法［9］中，鄰域的構(gòu)造僅采用簡單的移動操作，解之間高度的相似性削弱了算法跳出局部最優(yōu)陷阱的能力，而遺傳算法中的變異算子能產(chǎn)生具有新特性的個體，有效增加了路徑組合的多樣性，因此可以結(jié)合兩種算法的優(yōu)點設(shè)計混合型算法［16－17］。此外，依概率發(fā)生的交叉和變異行為不能完全保證種群的持續(xù)性進化。因此，本文采用簡化的遺傳算法：直接進行變異來構(gòu)建初始回路的鄰域，再挑選出優(yōu)秀個體進入局部搜索。

本文設(shè)計的TSP遺傳禁忌搜索算法（genetic tabu search algorithm，GTSA）首先使用遺傳變異算子作為分散策略構(gòu)造鄰域，使群體中的個體廣泛地分布在解空間的大部分區(qū)域，保證算法的全局尋優(yōu)能力；然后使用禁忌搜索作為集中策略進行局部的爬山優(yōu)化，使個體不斷突破已經(jīng)到達過的局部最優(yōu)解，避免早熟收斂。分散決策體現(xiàn)了群體智慧，有利于提高解空間的多樣性；集中決策保證了全局執(zhí)行力，有利于加大獲得全局最優(yōu)解的概率。同時，隨著迭代次數(shù)的增加，分散決策逐步形成對集中決策的約束力量。在兩者的相互作用中，內(nèi)部競爭加劇，最終收斂到近似最優(yōu)解。

GTSA的核心元素包括以下7個部分。

適應(yīng)度函數(shù)：它是衡量一條回路質(zhì)量優(yōu)劣的標準，通常使用路徑長度來評估個體的適應(yīng)度。第x條路徑的長度計算公式（1），dis（·）表示相鄰兩點間的距離，Cn（i）表示第i個點

鄰域：變換初始回路中途經(jīng)點的位置，產(chǎn)生的新回路集合稱為初始回路的鄰域。遺傳算法的變異算子能增加解空間的多樣性。為了改善禁忌搜索的鄰域結(jié)構(gòu)，擴大局部搜索的范圍，本文依次使用交換、簡單逆序、插入和移位變異算子［18］來構(gòu)建初始回路的鄰域。

移動：初始回路轉(zhuǎn)移到它的鄰域中的最優(yōu)回路，稱為一次移動。被采納的移動即為下一次迭代過程的初始回路。

候選解集：初始回路的鄰域子集。遺傳算法的選擇算子能引導(dǎo)算法朝著搜索空間中可能的最優(yōu)區(qū)域進行探測。為了加快禁忌搜索的速度，本文使用了精英選擇法，從初始回路的鄰域中挑選出最優(yōu)的10個回路構(gòu)成候選解集，參與禁忌搜索。

禁忌表：一種存放禁忌對象的數(shù)據(jù)結(jié)構(gòu)。一般情況下，禁忌表中的對象不能被選作為產(chǎn)生鄰域的新解，以防止出現(xiàn)循環(huán)搜索和陷入局部最優(yōu)解。

藐視準則：當候選解集中的最優(yōu)對象比歷史最優(yōu)解還要好時，即使該對象被禁忌，仍可以替代歷史最優(yōu)解，作為下一次迭代過程的初始解，即特赦該禁忌對象。還有一種特赦情況是：若候選解集中的所有對象都被禁忌，則特赦最優(yōu)候選解。

終止條件：算法達到預(yù)設(shè)的迭代次數(shù)，或者在固定周期內(nèi)連續(xù)求得的最優(yōu)解不變，二者滿足其一即可終止計算過程，其中固定周期設(shè)置為算法迭代次數(shù)的0.6倍。

3 算法實現(xiàn)

本文提出的TSP遺傳禁忌搜索算法的具體實現(xiàn)過程如圖1所示。

圖1 TSP遺傳禁忌搜索算法具體過程Fig.1 Genetic tabu search algorithm for TSP

在搜索過程中可能會刪除候選解集中的最優(yōu)禁忌對象，因此候選解集不存在全部禁忌的狀態(tài)。當候選解集為空時，繼續(xù)在上一次的初始解附近搜索。該算法的時間復(fù)雜度為O（n2）。

4 試驗與討論

4.1 試驗環(huán)境

本文基于MapGIS二次開發(fā)平臺實現(xiàn)了求解TSP的遺傳禁忌搜索算法，并采用北京市二環(huán)以內(nèi)的道路網(wǎng)絡(luò)對算法進行了測試，網(wǎng)絡(luò)包含1884個節(jié)點和2645條路段。試驗中按隨機采樣的方法從網(wǎng)絡(luò)中提取6組節(jié)點，數(shù)據(jù)規(guī)模依次為5、10、20、40、80、160，并將計算結(jié)果與禁忌搜索、遺傳算法和ArcGIS軟件的結(jié)果進行對比。測試環(huán)境如表1所示。

表1 測試環(huán)境Tab.1 Test environment

4.2 算法評價指標

本文采用解的精度增長率AGR（accuracy growth rate）、穩(wěn)定性Stability和時間耗費Time Cost來評價算法的性能［19］。解的精度增長率計算公式中，D為ArcGIS得到的TSP路徑長度，作為參考值；L為本文所涉及的3種算法得到的最優(yōu)值。結(jié)果穩(wěn)定性的計算公式中，C為同一組數(shù)據(jù)測試的總次數(shù)，默認值值為20；B為C次測試結(jié)果中的最優(yōu)解，I為C次測試中得到B的次數(shù)。時間耗費是指算法的CPU耗時，單位為s

遺傳算法和禁忌搜索均為啟發(fā)式算法，故同一組數(shù)據(jù)的多次計算結(jié)果很難完全相同，使用式（2）時采用如下假設(shè)：當兩次計算結(jié)果的AGR的差值小于1%時，認為兩者相等。

4.3 參數(shù)設(shè)置

根據(jù)現(xiàn)有算法的參數(shù)設(shè)置經(jīng)驗［7，20］，各參數(shù)取值如表2所示，N為節(jié)點個數(shù)。

4.4 試驗結(jié)果

4.4.1 算法精度

當滿足終止條件時，不同TSP算法的求解精度如表3所示。當節(jié)點數(shù)在20以內(nèi)時，3種算法的計算結(jié)果與參考值（ArcGIS的計算結(jié)果）相同；隨著節(jié)點數(shù)的成倍增長，GTSA和GA算法的求解質(zhì)量均優(yōu)于參考值（平均提升了3%），比TS算法平均提升了9%。

表2 算法的參數(shù)設(shè)置Tab.2 Parameters of tabu algorithm and genetic algorithm

表3 不同TSP算法的精度增長率比較Tab.3 Comparison of accuracy growth rate with three TSP algorithms

由于TS的平均精度最低，因此以TS算法的計算精度為基準，分析3種算法的收斂性，表4為3種算法收斂到指定精度的解時的計算次數(shù)?？梢姡M數(shù)據(jù)中GTSA的收斂速度最快；隨著數(shù)據(jù)規(guī)模的增大，GTSA快速收斂的優(yōu)勢愈加明顯。當N＝160時，GTSA的收斂速度是TS的6.8倍。當解值收斂到同一精度時，3種算法中計算次數(shù)的最大值小于3N。因此，可將迭代次數(shù)由40N改為3N，以減少計算冗余。

表4 不同TSP算法的收斂性比較Tab.4 Comparison of the convergence with three TSP algorithms

算法的精度和耗時關(guān)系曲線如圖2所示。試驗結(jié)果表明，當精度增長率控制在［－10%，0］時，GTSA的平均收斂速度比GA快一倍；且隨著精度的不斷提升，GTSA的效率優(yōu)勢不斷擴大。當解的質(zhì)量優(yōu)于參考值時，精度每提高一個百分點，耗時則成指數(shù)級增長，但GTSA的運行效率仍然領(lǐng)先。當節(jié)點數(shù)在20以內(nèi)時，GTSA和TS算法的最大耗時之差僅為2%。然而，隨著途經(jīng)節(jié)點數(shù)的增加，TS算法首先失效，無法獲得指定精度的解；而GA算法則隨后出現(xiàn)無法在多項式時間內(nèi)獲得較參考值更優(yōu)解的情況。

圖2 TSP算法精度—耗時曲線Fig.2 Curve of accuracy growth rate and time cost with three TSP algorithms

4.4.2 算法穩(wěn)定性

算法的穩(wěn)定性試驗結(jié)果如圖3（a）所示。其中GA1、TS1和GTSA1分別表示滿足終止條件時算法的穩(wěn)定性，此時GA和GTSA的AGR范圍均為［0，5%］，TS的 AGR范圍為［－10%，0］?？梢钥闯?，未對精度進行人工干預(yù)時，隨著數(shù)據(jù)規(guī)模的逐步增大，GTSA和GA穩(wěn)定性均急劇下降（GTSA的平均穩(wěn)定度僅為0.83）；而TS對于6組數(shù)據(jù)均保持著0.95以上的穩(wěn)定度。

基于式（2）的假設(shè)，當算法的AGR在［－1%，1%］時，認為算法的計算結(jié)果與參考值相等。由于解的質(zhì)量優(yōu)于參考值時，GTSA和GA算法的耗時呈指數(shù)級增長；因此將算法的AGR控制在［－1%，0］，以保證算法效率與精度的平衡。此時3種算法的穩(wěn)定性如圖3（b）所示。結(jié)果顯示，當前參數(shù)設(shè)置下的TS對于后3組數(shù)據(jù)已無法獲得滿足條件的可行解；而GTSA和GA的穩(wěn)定性得到了顯著提升，此時GTSA對于6組數(shù)據(jù)的穩(wěn)定度均達到1，這說明在允許的誤差范圍內(nèi)，一定的精度損失對于提高算法的穩(wěn)定性具有積極的作用。

圖3 TSP算法的精度控制對穩(wěn)定性的影響Fig.3 The influence of the accuracy on the stability with three TSP algorithms

4.4.3 算法效率

算法耗時和數(shù)據(jù)規(guī)模的關(guān)系（圖4）顯示，隨著節(jié)點數(shù)成倍增加，求解TSP的4種方法的耗時均呈指數(shù)級增長，其中GA增長最快；當途徑節(jié)點數(shù)增加至40，TS算法失效，無法獲得指定精度的解，詳見圖3。當N＝5時，GTSA與GA的耗時之比為1；而當N＝160時該比值降為30%。前3組數(shù)據(jù)中，GTSA的運行效率略優(yōu)于ArcGIS；而后3組數(shù)據(jù)中，GTSA的運行效率與ArcGIS持平。

圖4 精度誤差1%以內(nèi)時的算法效率Fig.4 Efficiency of three TSP algorithms when the precision error is less than 1%

4.4.4 結(jié)果展示

當解的精度誤差控制在1%以內(nèi)時，GTSA的穩(wěn)定性和運行效率均優(yōu)于TS和GA，并達到ArcGIS的水平。此時，GTSA對6組數(shù)據(jù)的TSP計算結(jié)果如圖5所示。

圖5 遺傳禁忌搜索算法針對不同節(jié)點數(shù)求解TSP的結(jié)果（精度誤差在1%以內(nèi)）Fig.5 Results of genetic tabu search algorithm when the precision error is less than 1%

4.5 討 論

禁忌搜索算法的結(jié)果易受初始解和鄰域結(jié)構(gòu)的影響，但局部搜索能力強。遺傳算法在進化后期收斂速度緩慢，但全局尋優(yōu)效果好。兩種算法結(jié)合后產(chǎn)生的遺傳禁忌搜索算法整體性能明顯優(yōu)于兩種單一的智能優(yōu)化方法，可滿足實際應(yīng)用需求。此外，4種遺傳變異算子構(gòu)造鄰域的過程是一個子任務(wù)之間相互獨立的循環(huán)操作，它具有模塊化和數(shù)據(jù)弱相關(guān)的特點，符合任務(wù)并行處理的機制。因此，可以考慮將遺傳禁忌搜索算法進行并行化，以充分利用多核或集群的計算資源，最大限度地提升算法的運行效率。這是遺傳禁忌搜索算法的一個潛在優(yōu)勢。遺傳禁忌搜索算法的并行優(yōu)化實現(xiàn)方法將在后續(xù)工作中展開深入研究。

同時，變異算子雖然增加了解空間的多樣性，提升了算法獲得全局最優(yōu)解的概率，但是變異本身是盲目的，它無法保證遺傳禁忌搜索算法以概率1收斂于全局最優(yōu)解。后續(xù)工作中需要補充試驗探討不同的構(gòu)建初始路徑算法的特性，以及分析變異算子、鄰域大小、禁忌長度等參數(shù)對算法性能的影響。

5 結(jié) 論

本文設(shè)計了一種求解交通網(wǎng)絡(luò)旅行商問題的遺傳禁忌搜索算法。算法采用遺傳變異算子作為分散策略構(gòu)造鄰域，使得解空間的多樣性增強，能以更大的概率獲得全局最優(yōu)解；再使用禁忌搜索作為集中策略進行局部探測，加快了算法的后期收斂速度。與單純的禁忌搜索和遺傳算法相比，在求解精度相同的情況下，本文算法的魯棒性更強，運行效率更高，穩(wěn)定性更好。當解的精度損失控制在1%以內(nèi)時，本文算法的運行效率已達到ArcGIS的水平。同時，遺傳算法的并行特性使得本文算法的并行實現(xiàn)成為可能。在后續(xù)工作中，需要進一步研究如何使算法能夠適應(yīng)不同分布形態(tài)的節(jié)點集，以提高算法的普適性；同時需要研究如何對序貫算法進行并行化改造，以充分地利用計算資源，最大限度地提升算法的運行效率。

［1］LU Feng.Shortest Path Algorithms：Taxonomy and Advance in Research［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：269－275.（陸鋒.最短路徑算法：分類體系與研究進展［J］.測繪學(xué)報，2001，30（3）：269－275.）

［2］YU Haicong，LU Feng.A Multi－modal Multi－criteria Route Planning Method Based on Genetic Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2014，43（1）：89－96.（于海璁，陸鋒.一種基于遺傳算法的多模式多標準路徑規(guī)劃方法［J］.測繪學(xué)報，2014，43（1）：89－96.）

［3］LI Qingquan，LI Qiuping，F(xiàn)ANG Zhixiang.An Emergency Evacuation Routing Optimization Method Based on Spacetime Congestion Concept［J］.Acta Geodaetica et Cartographica Sinica，2011，40（4）：517－523.（李清泉，李秋萍，方志祥.一種基于時空擁擠度的應(yīng)急疏散路徑優(yōu)化方法［J］.測繪學(xué)報，2011，40（4）：517－523.）

［4］QI Yutao，LIU Fang，JIAO Licheng.Immune Algorithm with Self－adaptive Reduction for Large－scale TSP［J］.Journal of Software，2008，9（16）：1265－1273.（戚玉濤，劉芳，焦李成.求解大規(guī)模TSP問題的自適應(yīng)歸約免疫算法［J］.軟件學(xué)報，2008，9（16）：1265－1273.）

［5］ZOU Peng，ZHOU Zhi，CHEN Guoliang，et al.A Multilevel Reduction Algorithm to TSP［J］.Journal of Software，2003，14（1）：35－42.（鄒鵬，周智，陳國良，等.求解TSP問題的多級歸約算法［J］.軟件學(xué)報，2003，14（1）：35－42.）

［6］HELSGAUN K.An Effective Implementation of the Lin－Kernighan Traveling Salesman Heuristic［J］.European Journal of Operational Research，2000，126（1）：106－130.

［7］XI Yugeng.Survey on Genetic Algorithm［J］.Control Theory and Applications，1996，13（6）：697－708.（席裕庚，柴天佑，惲為民.遺傳算法綜述［J］.控制理論與應(yīng)用，1996，13（6）：697－708.）

［8］KIRKPATRICK S，GELATT J C D，VECCHI M P.Optimization by Simulated Annealing［J］.Science，1983，220（4596）：671－680.

［9］GLOVER F，KELLY J P，LAGUNA M.Genetic Algorithms and Tabu Search：Hybrids for Optimization［J］.Computers and Operations Research，1995，22（1）：111－134.

［10］DAI Qiguo，JI Junzhong，LIU Chunnian.Knowledge－guiding Pheromone Control Strategy of Ant Colony Optimization［J］.Journal of Beijing University of Technology，2011，37（8）：1236－1241.（代啟國，冀俊忠，劉椿年.蟻群算法中基于知識引導(dǎo)的信息素控制策略［J］.北京工業(yè)大學(xué)學(xué)報，2011，37（8）：1236－1241.）

［11］SYLVIA B，GENEVIEVE L.Finding the Exact Integrality Gap for Small Traveling Salesman Problems［J］.Integer Programming and Combinatorial Optimization，2002（2337）：83－92.

［12］WANG Ling，ZHENG Dazhong.Meta－h(huán)euristic Algorithms：a Review［J］.Control and Decision，2000，15（3）：257－262.（王凌，鄭大鐘.Meta－h(huán)euristic算法研究進展［J］.控制與決策，2000，15（3）：257－262.）

［13］THAMILSELVAN R，BALASUBRAMANIE P.A Genetic Algorithm with a Tabu Search for Traveling Salesman Problem［J］.International Journal of Recent Trends in Engineering，2009，1（1）：607－610.

［14］FRED G.Future Paths for Integer Programming and Links to Artificial Intelligence［J］.Computers and Operations Research，1986，13（5）：533－549.

［15］GREFENSTETTE J J，GOPAL R，ROSMAITA B，et al.Genetic Algorithm for TSP［C］∥Proceedings of the First International Conference on Genetic Algorithms of the First International Conference on Genetic Algorithms and Their Applications.Pittsburg：Psychology Press，1985：160－168.

［16］YANG N，TIAN W F，JIN Z H.Crossover Tabu Search for Traveling Salesman Problem［J］.Journal of System Simulation，2006，18（4）：897－908.

［17］KE Ke，ZHANG Shiying.Research on the Tabu Hierarchy Genetic Algorithm［J］.Control and Decision，2001，16（4）：480－483.（柯珂，張世英.禁忌－遞階遺傳算法研究［J］.控制與決策，2001，16（4）：480－483.）

［18］LIU Jun，WANG Jiesheng.Solving Traveling Salesman Problem（TSP）with Pseudo Parallel Genetic Algorithms［J］.Control Theory and Applications，2007，24（2）：279－282.（劉軍，王介生.旅行商問題（TSP）的偽并行遺傳算法［J］.控制理論與應(yīng)用，2007，24（2）：279－282.）

［19］GAO Song，LU Feng.The Kth Shortest Path Algorithms：Accuracy and Efficiency Evaluation［J］.Journal of Image and Graphics，2009，14（8）：1677－1683.（高松，陸鋒.K則最短路徑算法效率與精度評估［J］.中國圖象圖形學(xué)報，2009，14（8）：1677－1683.）

［20］SEXTONA R S，ALIDAEEB B，DORSEY R E，et al.Global Optimization for Artificial Neural Networks：A Tabu Search Application［J］.European Journal of Operational Research，1998，106（2）：570－584.