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

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

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

引言

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

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

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

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

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

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

3 人工蜂群算法在VRPTW中的簡單應(yīng)用

3.1 初始解生成

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

3.2 鄰域搜索

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

3.3 偵查蜂

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

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

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

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

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

3.4 實驗

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

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

參考文獻

[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].計算機工程與應(yīng)用，2007，43（14）：223-226.

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

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

[5]楊進，馬良.蜂群優(yōu)化算法在帶軟時間窗的車輛路徑問題中的應(yīng)用[J].預(yù)測，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.