人工蜂群算法在單時間窗車輛路徑問題中的應用

摘 要：單時間窗車輛路徑問題（VRPTW）是運籌學領域的經典問題，在實踐中有著廣泛的應用。文章中我們使用人工蜂群算法（ABC）來求解該問題。針對VRPTW的特點，我們用3種局部搜索算法對解進行優化。用solomon標準測試集對算法進行檢驗，該算法的結果表明在求解此問題時表現較好。

關鍵詞：人工蜂群算法；車輛路徑問題；局部搜索

引言

Solomon[1]在1986年最早對VRPTW進行啟發式算法研究。吳勇[2]提出多群粒子群算法來求解VRPTW，除了每個粒子群初始解生成不同外，還在每個粒子群中加入記憶功能加速收斂。葛金輝[3]對禁忌搜索算法進行了改進，首先隨機構造多個初始解，從中選取最好的作為算法初始解，并構造了隨搜索過程發生改變動態禁忌表，提高優化能力。何小鋒[4]針對蟻群算法易陷入局部最優和收斂速度慢的問題，結合量子計算提出一種粒子蟻群算法，提高了算法的全局搜索能力。楊進[5]用ABC算法對該問題進行了研究。

1 單時間窗車輛路徑問題定義

VRPTW的每一個客戶都有一個與之對應的時間段[ai，li]，稱之為時間窗。車輛離開配送中心的時間，車輛在邊（i，j）的行駛時間tij，每個顧客需要的服務時間si均已知。每個客戶的服務開始時間必須位于其時間窗內，當服務開始后車輛必須在客戶i處停留si，需要注意的是當車輛在ai前到達客戶i，需要等待直到服務開始。

VRPTW的目標是找到具有最小成本的K條線路，總結如下：每條線路開始并結束于配送中心；每一個客戶只能被一輛車服務一次；由一輛車服務的所有客戶的總需求不能超過車輛的容量限制C；以及對于每一個客戶i，在時間段[ai，li]內開始服務，且服務時間為si。

2 人工蜂群算法的基本原理

在ABC[6]算法中，人工蜜蜂種群包括3類蜜蜂：雇傭蜂、跟隨蜂以及偵查蜂。跟隨蜂是指在跳舞區等待食物源信息并選擇食物源的蜜蜂，雇傭蜂是指自己出去尋找食物源并將食物源的信息通過在跳舞區域跳舞傳遞給跟隨蜂的蜜蜂，偵查蜂是在某種條件下隨機的尋找食物源。在ABC算法中雇傭蜂和跟隨蜂各占種群數量的1/2，每一個食物源都對應著一個雇傭蜂。當一個食物源被雇傭蜂以及跟隨蜂放棄后，這個食物源對應的雇傭蜂就變為偵查蜂。

3 人工蜂群算法在VRPTW中的簡單應用

3.1 初始解生成

文章初始解生成采用Solomon提出的插入啟發式算法[7]，這是一種連續構造線路的啟發式方法，與并行相對應。該算法是基于時間和距離兩種因素，每條路徑首先選擇一個種子客戶，然后選擇沒有分配路徑的客戶添加到該線路，直到這條路徑達到約束限制，如果還存在沒有分配路徑線路的客戶，那么重復上述插入過程，直到所有的客戶都分配路徑。

3.2 鄰域搜索

我們在ABC算法中的鄰域搜索中采用3種局部搜索組合的方式，其順序為：2_opt*：任選兩條路徑，均一分為二，互換首尾，重新組合；重新插入（內）：這種方法是隨機選擇一個客戶，將其插入到新的位置，新的位置可以與原來的位置處于同一路徑，但不能與原位置重復；重新插入（外）：這種方法是隨機選擇一個客戶，將其插入到新的位置，新的位置與原位置位于不同路徑。

3.3 偵查蜂

在偵查蜂階段，每次迭代只允許一個偵查蜂替換一個解，但不是完全隨機的產生一個新解，而是在原來解的基礎上進行一次搜索，不論得到的新解適應度好壞，都替換掉原解。

（1）選中要拋棄的解F，計算F中所有客戶的等待時間w，并進行排序，選擇等待時間最長的ns個客戶。

（2）這里要用到每個客戶的鄰域概念：對于客戶i，計算其與每一個客戶的相似程度，用Ne來表示Ne（i）=0.5*|li-lj|+0.5*dij，然后根據nl確定與客戶i相似度最高的nl個客戶（Ne越小相似度越高）。

（3）將第一步中選中的ns個客戶，并結合第二步確定這ns個客戶的鄰域集合S，因為不同客戶的鄰域可能出現重疊，因此集合S的最大長度為ns+ns*nl，將集合S中的客戶從F中移除，得到F'，等待重新插入。

（4）用并行插入啟發式算法[8]將集合S中的客戶重新插入到F'中。替換掉F，更新適應度值。

3.4 實驗

為了驗證算法有效性我們選取了最常使用的Solomon標準測試集。在這里我們選取C1類數據共8組數據測試算法。我們采用Matlab進行編程，參數設置如下：ns=10，nl=6，limit=50，種群規模NP=10，程序迭代次數為1000，運行10次。

從人工蜂群算法得到的結果看共有6組數據得到了最優值，分別為C101，C104-109，成功率為66.7%。其中C101，C105-107，4組數據的平均值也達到了最優解，表明在求解這幾組數據時算法的穩定性較好，從平均值來看不管是最優值誤差還是平均值誤差均在1%以內，證明上述人工蜂群算法在求解C1類數據時的表現較好。

參考文獻

[1]Solomon M M. On the worst-case performance of some heuristics for the vehicle routing and scheduling problem with time window constraints[J]. Networks，1986，16（2）：161-174.

[2]吳勇，葉春明，馬慧民，等.基于并行粒子群算法的帶時間窗車輛路徑問題[J].計算機工程與應用，2007，43（14）：223-226.

[3]葛金輝.有時間窗的車輛路徑問題及改進禁忌搜索算法[J].吉林大學學報：理學版，2011，49（1）：105-111.

[4]何小鋒，馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統工程理論與實踐，2013，33（5）：1255-1261.

[5]楊進，馬良.蜂群優化算法在帶軟時間窗的車輛路徑問題中的應用[J].預測，2010，29（6）：67-70.

[6]Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical report-tr06， Erciyesuniversity， engineering faculty， computer engineering department，2005.

[7]Solomon M M. Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints[J].Operations Research，1987，35（2）：254-266.

[8]Potvin J Y， Rousseau J M. A parallel route building algorithm for the vehicle routing and scheduling problem with time windows[J].European Journal of Operational Research，1993，66（3）：331-340.