簡述解決TSP問題的智能優(yōu)化算法

○李葶

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

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

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

一、TSP問題

1、TSP問題的簡介

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

2、TSP問題的數(shù)學模型

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

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

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

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

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

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

綜合比較，智能優(yōu)化算法是一類綜合性能比較強的TSP算法，也是目前最適合用于開發(fā)物流配送調(diào)度系統(tǒng)的算法，本文將對幾種智能優(yōu)化算法進行詳細說明。

1、神經(jīng)網(wǎng)絡(luò)算法

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

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

2、遺傳算法

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

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

3、禁忌搜索算法

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

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

4、模擬退火法

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

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

5、蟻群算法

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

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

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

螞蟻算法具有正反饋、并發(fā)性、較強的魯棒性、易于其他算法相結(jié)合等優(yōu)點，但是螞蟻算法易出現(xiàn)停滯現(xiàn)象。

[1]國家發(fā)展和改革委員會經(jīng)濟運行調(diào)節(jié)局、南開大學現(xiàn)代物流研究中心：中國現(xiàn)代物流發(fā)展報告（2010）[M].中國物資出版社，2010.

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

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

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