簡述解決TSP問題的智能優化算法

○李葶

（同濟大學中德學院 上海 200092）

隨著我國經濟的持續快速發展，人們對交通運輸的各種需求也顯著增長。從1999年到2010年，我國公路總長度從130萬公里上升到370萬公里，增長幅度為185%，同期我國注冊的車輛數量由1500萬輛上升到8000萬輛，增長幅度為433%，明顯高于中國公路總長的增長幅度。由于車輛數量的激增，導致城市交通擁堵嚴重，交通事故頻發，物流成本居高不下，物流時效性也無法得到保證。我國物流成本占GDP的比重持續偏高，約為20%，遠高于發達國家物流成本占GDP的比重10%，以及中等發達國家的16%。而城市閑置土地資源的緊缺，導致修建和拓寬道路的成本越來越高，且修建和拓寬道路的速度遠遠趕不上城市車輛的增長速度，此時提高城市道路的利用率、安全性和舒適性以及降低城市物流成本就成為我們急需解決的問題。

物流配送調度系統就是針對以上問題提出的，它能提供可靠的交通信息、高效快速的應急服務，在降低物流成本方面有著顯著的成效，能滿足現代物流經濟性、準時性和靈活性的多種需求。迄今為止，國外研究物流配送調度系統的理論和算法已經不少，并且在實際應用方面取得顯著的成果，如美國IBM基于最短路徑法和啟發式算法研究出來的VSPX系統，日本富士通以節約法為核心研發出來的VSS系統，以及美國美孚以掃描法為核心研究出來的HPCAD系統。但是國內在這方面的研究僅停滯于初步理論階段，在開發實用的物流配送調度系統方面還是一片空白。造成這種現象的根本原因在于大部分算法只考慮了TSP（Traveling salesman problem）問題的部分約束條件，且設置了許多假設條件，限制了他們的應用范圍，在實際應用中缺乏靈活性。由于研發物流配送調度系統的核心在于解決貼合實際的TSP問題，因此研究可以妥善解決TSP問題的算法，并在此基礎上開發出智能的物流配送調度系統具有現實的理論意義和實踐意義。

一、TSP問題

1、TSP問題的簡介

TSP問題也稱旅行推銷員問題、貨郎擔問題，是經典的組合優化問題，最早的記錄來自于1759年歐拉研究的騎士周游問題，即對象棋中的64個方格，走訪每個方格有且僅有一次。TSP問題的歷史可以分成以下幾個階段：1800—1900年，首次描述TSP問題；1920—1930年，TSP問題得到較好的定義；1940—1950年，研究人員意識到TSP問題是個難題；1954年，42個城市的TSP問題求得最優解；1980年，Crowder和Padberg求解了318個城市的問題；1987年，Padberg和Rinaldi求解了2392個城市的問題；1992年，美國Rice大學的CRPC研究小組解決了 3038個城市的問題；1994年，Applegate、Bixby和Chvatal等人解決了7393個城市的問題；1998年，CRPC研究解決了美國13509個城市組成的TSP問題；2003年，Hisao Tamaki發現了TSPLIB中pla33810的一個次優解；2004年，Keld Helsguan發現了pla85900問題的一個次優解。

2、TSP問題的數學模型

TSP問題可以表達為，給定k個城市，i、j為城市編號，0≤i≤k，0≤j≤k。dij代表從城市 i到 j的距離，解決 TSP 問題就是尋找一條最短的閉合路徑，使得每個城市剛好遍歷一次。

二、求解TSP問題的各種解法

目前求解TSP問題的主要方法主要分兩類：精確求解算法和近似求解算法。

精確求解算法通過搜索整個問題的全部解空間，在所有解集中求得最優解。精確求解算法包括整數規劃法、動態規劃法、分支定界算法等，這類算法雖然可以得到精確解，但由于過大的搜索空間范圍導致計算時間過長，計算效率非常低下，很少用于實際應用。最早用于解決TSP問題的精確求解算法是窮舉法，思路簡單，可以直觀快速地求出少量城市點數的最優解，但是求解大規模數據集時運算量太大，運算效率不高，時間上難以承受。

近似求解法又可稱為啟發式求解算法，部分近似求解算法又被稱為智能優化算法。典型的近似算法有插入算法、r-opt算法和最近鄰算法等，這類算法雖然可以較快的計算出可行解，但是其接近最優解的程度不夠令人滿意。智能優化算法主要包括神經網絡算法、遺傳算法、禁忌搜索算法、模擬退火法、粒子群算法和蟻群算法等，是近幾年來非常活躍的研究領域，它是利用仿生學的原理，讓算法在計算過程中不斷自我調整，使之具備自適應能力。智能優化算法雖然不能在有限的時間內獲得最優解，但其接近最優解的程度是非常可喜的。

求解TSP問題的算法很多，要評價和比較各種算法的優劣，必須有一個綜合的性能評價標準，TSP算法的綜合性能評價標準包括：算法求解的精確程度，即接近最優解的程度；求解算法的復雜度，包括時間的復雜度和空間的復雜度；求解算法的適應性，即算法在各個領域的通用程度；求解算法的嚴密性，即保證求解算法充分的理論基礎。

綜合比較，智能優化算法是一類綜合性能比較強的TSP算法，也是目前最適合用于開發物流配送調度系統的算法，本文將對幾種智能優化算法進行詳細說明。

1、神經網絡算法

人工神經網絡（Artificial Neural Network,簡稱ANN），又名神經網絡（Neural Network,簡稱NN），是一種通過模擬動物神經網絡的特點進行數據分析的方法。1985年，Hopfield和Tank首次將這種算法應用于求解TSP問題。它的主要思想是用能量函數替代TSP問題中的目標函數，通過能量函數確定神經元之間的相互連接權限，隨著網絡狀態的逐漸變化，當能量達到平衡時，就可以得到局部最優解。

由于神經網絡是一種數據驅動型非線性映射模型，可以實現任何復雜的因果關系映射，能夠從大量的歷史數據中進行聚類和學習，進而找到某些行為變化規律，因此可以用來處理難以用數學模型描述的系統，具有很強的并行性、自適應、聯想記憶、容錯魯棒以及任意逼近非線性等特性。目前神經網絡技術在解決TSP問題上取得了一定的成績，但是神經網絡存在嚴重缺陷，很難確定算法的參數，必須通過多次反復的數據測試才能獲得一個相對較好的參數，因此嚴重限制了神經網絡的適用范圍。

2、遺傳算法

遺傳算法是Holland于1973年首次提出的，是一種模擬生物界自然選擇和遺傳機制的隨機搜索算法。它的基本思想是將TSP問題的求解表示成“染色體”的適者生存的過程，通過“染色體”的一代代的進化，即通過選擇、交叉和變異等操作，最終得到“最適應環境”的個體，從而求得最優解或滿意解。

遺傳算法能準確模擬自然界生物進化過程中的染色體，整個遺傳過程操作簡單，在數據優化過程中不受外界條件的限制，能用簡單的計算方法實現全局解空間的搜索。但是遺傳算法中容易出現“早熟”現象，必須通過設置變異概率來控制“早熟”，高的變異率擴大了搜索空間，有利于誘導產生更加優秀的個體，但是交叉概率和變異概率過大會導致收斂速度過慢，迭代次數過大。因此實現收斂速度和最優解之間的平衡是遺傳算法的一大難點。

3、禁忌搜索算法

禁忌搜索算法是由Fred Glovert等于1986年首次提出的，是一種全局性逐步尋優的鄰域搜索算法，可以模擬人類記憶功能的尋優特征，通過局部鄰域搜索機制和相應的禁忌準則來避免重復搜索，并通過藐視準則赦免一些被禁忌的優良狀態，進而保證多樣化的有效搜索，最終實現全局優化。

在禁忌搜索算法的搜索過程中，鄰域結構、候選解、禁忌長度、禁忌對象、藐視準則、終止準則等都是影響算法性能的關鍵因素。且禁忌搜索算法對初始解和鄰域結構有較大的依賴性，由于禁忌算法串行的搜索機制，一個不理想的初始解將直接影響到搜索質量。

4、模擬退火法

現代模擬退火算法是由Kirkpatrick S等于1983年提出，是基于Mente Carlo迭代求解策略的一種隨機尋優算法。它通過模擬物理中固體物質的退火過程，結合具有概率突跳特性的Metropolis抽樣策略，在解空間中隨機尋找目標函數的全局最優解，在降溫過程中不斷重復抽樣，最終實現問題的最優解。

模擬退火算法解的優越性依賴初始溫度和退火時間，當初始溫度過低或者退火速度過快，算法將陷入局部最優解。但是如果迭代次數較高，隨著退火速度的降低將極大增加運行時間。

5、蟻群算法

蟻群算法是由意大利學者Dorigo M于1991年首次提出，是一種模擬自然界螞蟻尋找食物的過程來計算路徑的算法，通過群體間信息素的交換和相互合作尋求最優解的過程。螞蟻獨立尋找食物，在找尋食物的路程中會釋放信息素，信息素會影響隨后的螞蟻對路徑的選擇，信息素越強的路徑，越可能被螞蟻選擇。對于螞蟻算法來說，各條路徑的初始信息素相同，但是隨著時間的推移，較優路徑上的信息素會越來越多，最后實現尋求最優解或次優解的目的。

螞蟻算法中，螞蟻數量M的設置是影響算法性能的重要因素，M過小會導致未被所搜索過的路徑信息素趨向于0，全局搜索能力太差，穩定性變差。M過大會導致所有路徑上的信息素過于平均，隨機性太強，收斂速度過慢，信息正反饋能力過弱。有研究表明，M取值范圍在[0.6n,0.9n]（n代表城市規模），螞蟻算法的收斂速度和接近全局最優解的能力最理想。

在螞蟻算法中，總信息量Q表示循環一周螞蟻釋放的信息素的總和，Q也同樣對螞蟻算法的性能有很大的影響。Q越大信息素增長越快，正反饋效果越好，算法收斂速度越快。研究表明，Q的取值與TSP問題的規模和路徑長度有關，在小規模的TSP問題中，Q一般取100。

螞蟻算法具有正反饋、并發性、較強的魯棒性、易于其他算法相結合等優點，但是螞蟻算法易出現停滯現象。

[1]國家發展和改革委員會經濟運行調節局、南開大學現代物流研究中心：中國現代物流發展報告（2010）[M].中國物資出版社，2010.

[2]唐納德,J.鮑爾索科斯、戴維J.克勞斯：物流管理[M].機械工業出版社，1999.

[3]林志毅：改進的遺傳算法求解TSP問題[D].武漢理工大學，2006.

[4]Helsgaun K.An effectiveimplementation oftheLin-Kernighan traveling salesman heuristic[J].European Journal of Operational Research,2000.