[摘要] 車輛路徑問題是一個(gè)NP-hard問題，傳統(tǒng)的方法對(duì)其進(jìn)行有效求解，本文分析了蟻群算法在VRP問題中的可行性，并提出了自適應(yīng)策略對(duì)傳統(tǒng)的蟻群算法進(jìn)行改進(jìn)，該策略可以根據(jù)不同搜索階段調(diào)整參數(shù)提高算法的收斂速度。最后，通過蕪湖市的數(shù)據(jù)對(duì)該方法進(jìn)行檢驗(yàn)，實(shí)驗(yàn)結(jié)果顯示，本文提出的自適應(yīng)蟻群算法的性能優(yōu)于傳統(tǒng)的蟻群算法。

[關(guān)鍵詞] 車輛路徑問題 蟻群算法 自適應(yīng)策略

一、引言

車輛路徑問題（VRP）是物流研究領(lǐng)域中一個(gè)具有十分重要理論和現(xiàn)實(shí)意義的問題，該問題可以描述為一個(gè)需求點(diǎn)位置已知的物流服務(wù)網(wǎng)絡(luò)的車輛配送問題，其目標(biāo)就是尋找最小費(fèi)用的車輛配送路線。車輛路徑問題是一個(gè)著名的NP 完全問題，只有當(dāng)其規(guī)模較小時(shí)，才能求得其精確解。近年來，大量的研究結(jié)果顯示，啟發(fā)式算法在求解大規(guī)模車輛路徑問題時(shí)是一種有效的途徑。

蟻群算法（ACO)是由意大利學(xué)者Dorigo等人在20世紀(jì)90年代初首先提出來的，它是繼模擬退火算法、遺傳算法、禁忌搜索算法、人工神經(jīng)網(wǎng)絡(luò)等以后的又一種應(yīng)用于組合優(yōu)化問題的啟發(fā)式搜索算法。比較有代表性的研究有，M.Dorigo等人使用蟻群算法解決TSP問題，然后進(jìn)一步把它們的方法擴(kuò)展到了解決不均衡的TSP、QAP和job-shop調(diào)度問題中；為了克服在Ant-Q中可能出現(xiàn)的停滯現(xiàn)象，Stützle，T.等人提出了MAX-MIN蟻群算法，稱作MMAS，該算法為了避免算法過早收斂非全局最優(yōu)解，將各路經(jīng)的信息素濃度限制在[τmin，τmax]之間，各路徑初始信息素初值設(shè)為最大值τmax，并且一次循環(huán)后只增加路徑最短的螞蟻經(jīng)過路徑的信息素；吳慶洪等人提出了具有變異特征的蟻群算法，在基本蟻群算法中引入變異機(jī)制，充分利用了2-交換法簡潔高效的特點(diǎn)；姚寶珍[4]提出了一種自適應(yīng)的蟻群算法，該算法可以根據(jù)搜索的階段調(diào)整參數(shù);陳等人提出了一種基于分布均勻度的自適應(yīng)蟻群算法，該算法根據(jù)優(yōu)化過程中解的分布均勻度，自適應(yīng)地調(diào)整路徑選擇概率的確定策略和信息量更新策略。蟻群算法作為一種新的啟發(fā)式算法已經(jīng)成功地應(yīng)用到了許多領(lǐng)域，在車輛路徑問題也有很多學(xué)者進(jìn)行了大量的研究，主要有文獻(xiàn)等。本文采用了一種自適應(yīng)的蟻群算法（AACO）來求解車輛路徑問題，并通過一個(gè)實(shí)例對(duì)該算法進(jìn)行了檢驗(yàn)。

二、問題描述

一個(gè)典型車輛路徑問題可以描述為：設(shè)配送中心有M輛車，需要對(duì)N個(gè)顧客進(jìn)行服務(wù)，每個(gè)客戶的需求量為qi(i=1，2，…，N)，每輛車的最大載重量為V。設(shè)結(jié)點(diǎn)集合為C(c0，c1，c2，…，cN)，其中c0代表配送中心，而其它的N點(diǎn)代表N個(gè)顧客；fij表示客戶i到客戶j的阻抗或成本，其可以表示時(shí)間、行駛里程或其它費(fèi)用等，定義變量如下：

三、自適應(yīng)的蟻群算法

1.自適應(yīng)轉(zhuǎn)移規(guī)則

螞蟻運(yùn)動(dòng)過程中會(huì)優(yōu)先選擇含“信息素”濃度較大的路徑。但是蟻群在搜索過程中，為了使蟻群算法能夠得到全局最優(yōu)解就必須在搜索過程中保持很強(qiáng)的隨機(jī)性，而蟻群算法的收斂又要求一定的確定性，轉(zhuǎn)移規(guī)則必須解決的就是尋找二者的平衡點(diǎn)。轉(zhuǎn)移規(guī)則決定了算法的執(zhí)行效率，當(dāng)源問題確定后，信息素強(qiáng)度（信息素更新策略中確定）和期望度（根據(jù)源問題相關(guān)的貪婪式算法得到）也基本確定，因此如何確定兩個(gè)啟發(fā)式因子（α和β）則非常重要。通常兩個(gè)參數(shù)是通過仿真來確定，大多數(shù)研究中采用的是固定值，這樣就忽略了蟻群在進(jìn)化過程中，信息素和期望度的相對(duì)重要程度。比如在進(jìn)化的最初，系統(tǒng)還沒有信息素存在，這時(shí)，對(duì)于螞蟻的運(yùn)動(dòng)來說，期望信息更加重要，也就是說，確定性信息占主導(dǎo)地位；而隨著信息素更新，螞蟻的運(yùn)動(dòng)將逐漸重視路徑中的信息素強(qiáng)度，也就是蟻群在系統(tǒng)中的累積信息?；诖?，我們?cè)O(shè)計(jì)了一種自適應(yīng)的轉(zhuǎn)移規(guī)則，對(duì)于第i點(diǎn)的第k只螞蟻來說，它選擇下一點(diǎn)j的概率如下：

這里τij是 (i，j)邊信息素的強(qiáng)度；ηij是(i，j)邊的能見度；α和β分別是信息啟發(fā)式因子和能見度啟發(fā)式因子。α的大小反映了蟻群在路徑搜索中隨機(jī)性因素作用的強(qiáng)度，β的大小則反映了蟻群在路徑搜索中確定性因素作用的強(qiáng)度；tabuk是禁忌集合（在TSP問題中已經(jīng)經(jīng)過的點(diǎn)就被認(rèn)為是不可行點(diǎn)）；t是進(jìn)化代數(shù)；T是預(yù)設(shè)的最大進(jìn)化代數(shù)，這里設(shè)T=400；[ ]是取整符號(hào)。

2.自適應(yīng)信息素更新策略

信息素為螞蟻之間提供了間接的通信手段，也就是說，螞蟻可以通過感知信息素濃度來完成彼此間的通信。螞蟻依據(jù)轉(zhuǎn)移規(guī)則沿著不同的點(diǎn)游歷，直至構(gòu)成了一個(gè)源問題的解決方案。每次循環(huán)后，在每條邊上的信息素濃度將依據(jù)更新策略更新。

其中，ρ是信息素殘留系數(shù)，這里ρ=0.8; 是第k只螞蟻在當(dāng)前循環(huán)中在(i，j)邊上的信息素增量，p是蟻群的規(guī)模，在現(xiàn)實(shí)的蟻群系統(tǒng)中，較短路徑上的信息素濃度更高；相似的，在蟻群算法中，與最優(yōu)方案更接近的路徑中獲得的信息素越多，使其在下一循環(huán)中更有吸引力。

在整個(gè)進(jìn)化過程中均采用這種靜態(tài)的更新策略可能會(huì)使算法陷入局部最優(yōu)。比如某條局部最優(yōu)路徑上存在信息素增量，而且隨著進(jìn)化的深入，信息素增量會(huì)越來越大，而如果最佳路徑還未被走過，其上的信息素只有蒸發(fā)項(xiàng)而變得越來越小，在下次搜索被選擇的概率較小，這樣就會(huì)使局部的最優(yōu)路徑很快就占據(jù)了統(tǒng)治地位，使算法陷入局部最優(yōu)。雖然max-min系統(tǒng)一定程度上控制了陷入局部最優(yōu)的可能性，但是更新策略仍然是一個(gè)問題。為此，我們提出了一種自適應(yīng)的信息素更新策略，就是在進(jìn)化的最初，我們采用了較大的信息素增量，而當(dāng)進(jìn)化的一定程度后，減小了信息素增量，使算法可以進(jìn)行詳細(xì)的局部搜索，具體公式如下：

其中，Q是一個(gè)常數(shù)，這里設(shè)Q=1000。

四、實(shí)例研究

為了驗(yàn)證自適應(yīng)蟻群算法的有效性，本文采用蕪湖市的數(shù)據(jù)對(duì)該算法進(jìn)行了檢驗(yàn)。蕪湖市的人口數(shù)量大約為222萬人，面積為3，317平方公里，其道路網(wǎng)的長度為1，622公里。本文選取是由1個(gè)配送中心服務(wù)22個(gè)客戶（大型購物中心）的實(shí)例。

本節(jié)假設(shè)所有中心的車隊(duì)都由容量為1的均一車型組成，并將每個(gè)客戶的需求都按比例縮放到[0，1]（圖1）。然后使用Visual C++.Net 2003實(shí)現(xiàn)該算法，同時(shí)運(yùn)行在由8臺(tái)計(jì)算機(jī)（512M內(nèi)存、3000MHZ處理器）組成的集群環(huán)境。為了評(píng)價(jià)自適應(yīng)蟻群算法（AACO）的性能，本文將該方法與傳統(tǒng)的蟻群算法（ACO）以及MMAS[2]，在同樣參數(shù)下三種方法運(yùn)行10次，圖2和圖3分別顯示的是三種算法的計(jì)算結(jié)果和運(yùn)行時(shí)間。

我們可以發(fā)現(xiàn)三種算法的優(yōu)化質(zhì)量和計(jì)算時(shí)間上存在差異，AACO在優(yōu)化質(zhì)量和計(jì)算時(shí)間上是三者中最好的，而MMAS的優(yōu)化質(zhì)量略優(yōu)于ACO的優(yōu)化質(zhì)量，這是因?yàn)镸MAS將各路徑的信息素濃度限制在[τmin ， τmax ]之間，各路徑初始信息素初值設(shè)為最大值τmax，并且一次循環(huán)后只增加路徑最短的螞蟻經(jīng)過路徑的信息素，從而避免算法過早收斂非全局最優(yōu)解。而自適應(yīng)策略可以根據(jù)搜索的不同階段自適應(yīng)調(diào)整參數(shù)，擴(kuò)大搜索空間，從而提高算法的優(yōu)化質(zhì)量，同時(shí)可以明顯的加快算法的收斂速度。實(shí)驗(yàn)結(jié)果顯示，本文提出的自適應(yīng)蟻群算法可以明顯地改進(jìn)傳統(tǒng)的蟻群算法。

五、結(jié)論

車輛路徑問題是物流分配研究的一個(gè)重要問題。由于車輛的裝載能力不同，本文建立了同時(shí)考慮可變成本和車輛的固定成本的物流配送模型?？紤]物流配送問題是在眾多顧客中尋找最短路徑，是NP-hard問題。本文采用了自適應(yīng)的蟻群算法。最后，利用蕪湖市的數(shù)據(jù)對(duì)該方法進(jìn)行檢驗(yàn)，結(jié)果表明此方案提高了解的質(zhì)量并節(jié)約求解的運(yùn)行時(shí)間。

參考文獻(xiàn):

[1]Dorigo， M.， Maniezzo， V.， Colorni， A.，( 1996); The Ant System: Optimization by a Colony of Cooperating Agents， IEEE Transactions on Systems， Mans， and Cybernetics 1 (26)， p.29～41

[2]吳慶洪張紀(jì)會(huì)徐心和:具有變異特征的蟻群算法.計(jì)算機(jī)研究與發(fā)展，36(10):1240～1245(1999)

[3]姚寶珍:自適應(yīng)并行蟻群算法. 模式識(shí)別與人工智能. 2007， 20(4):458～461

[4]陳沈潔秦玲等:基于分布均勻度的自適應(yīng)蟻群算法.軟件學(xué)，2003.14(08):1379～1387