○李葶

（同濟(jì)大學(xué)中德學(xué)院 上海 200092）

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

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

一、TSP問題

1、TSP問題的簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

2、遺傳算法

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

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

3、禁忌搜索算法

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

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

4、模擬退火法

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

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

5、蟻群算法

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

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

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

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

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

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

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

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