基于自適應蟻群算法的車輛路徑問題研究

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

[關鍵詞] 車輛路徑問題 蟻群算法 自適應策略

一、引言

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

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

二、問題描述

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

三、自適應的蟻群算法

1.自適應轉移規(guī)則

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

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

2.自適應信息素更新策略

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

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

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

其中，Q是一個常數，這里設Q=1000。

四、實例研究

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

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

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

五、結論

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

參考文獻:

[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]吳慶洪張紀會徐心和:具有變異特征的蟻群算法.計算機研究與發(fā)展，36(10):1240～1245(1999)

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

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