姜 婷

?

基于改進(jìn)離散蜂群算法的車輛路徑問(wèn)題求解

姜 婷1,2

(1.安徽經(jīng)濟(jì)管理學(xué)院 信息工程系，安徽 合肥 230059；2.合肥工業(yè)大學(xué) 管理學(xué)院，安徽 合肥 230009)

采用一種改進(jìn)的人工蜂群算法(IABC)求解標(biāo)準(zhǔn)車輛路徑問(wèn)題. 針對(duì)基本人工蜂群算法易陷入局部極小、收斂較慢等缺陷，提出了6種鄰域生成策略，并基于此設(shè)計(jì)了新的局部搜索算法. 引領(lǐng)蜂和跟隨蜂根據(jù)該算法在鄰域空間內(nèi)更新當(dāng)前解. 通過(guò)小規(guī)模和大規(guī)模算例的仿真實(shí)驗(yàn)，將本文算法與其它智能算法以及基本人工蜂群算法進(jìn)行了比較，驗(yàn)證了本文提出的算法無(wú)論在有效性還是穩(wěn)定性上都具有良好的效果.

車輛路徑問(wèn)題；離散蜂群算法；鄰域生成策略；局部搜索算法

隨著我國(guó)經(jīng)濟(jì)進(jìn)入新常態(tài)，電子商務(wù)和物流業(yè)迎來(lái)了新一輪的發(fā)展機(jī)遇，物流配送是其中的重要環(huán)節(jié). 車輛路徑問(wèn)題(Vehicle Routing Problem, VRP)是這一環(huán)節(jié)中非常關(guān)鍵的研究?jī)?nèi)容，屬于組合優(yōu)化領(lǐng)域和運(yùn)籌學(xué)研究的熱點(diǎn)和重點(diǎn). 該問(wèn)題是一個(gè)NP難題，問(wèn)題規(guī)模較大時(shí)只能求得近似解，可以采用群智能優(yōu)化算法進(jìn)行求解. 很多學(xué)者在這方面取得一定的研究成果，如文獻(xiàn)[1][2]采用粒子群算法，文獻(xiàn)[3][4][5]采用遺傳算法，文獻(xiàn)[6][7][8]采用蟻群算法分別研究了物流配送中的車輛路徑問(wèn)題.

人工蜂群算法(Artificial Bee Colony Algorithm, ABC)由Karboga等模擬工蜂的采蜜行為提出[9]. 該算法參數(shù)較少、魯棒性強(qiáng)、編碼較簡(jiǎn)單，適用于絕大多數(shù)的目標(biāo)優(yōu)化問(wèn)題[10-12]. 已有的研究表明，基本人工蜂群算法存在一些不足，如容易陷入局部極小、收斂較慢等[13]. 近幾年，有學(xué)者將人工蜂群算法應(yīng)用于車輛路徑問(wèn)題的求解中. 比如文獻(xiàn)[14]采用改進(jìn)了迭代策略和鄰域構(gòu)成的人工蜂群算法來(lái)求解最優(yōu)路徑選擇；文獻(xiàn)[15]提出了一種基于大規(guī)模鄰域搜索的改進(jìn)人工蜂群算法來(lái)求解帶載重量限制的車輛路徑問(wèn)題；文獻(xiàn)[16]采用基本人工蜂群算法對(duì)車輛路徑問(wèn)題進(jìn)行了求解. 本文在已有研究基礎(chǔ)上，提出了一種新的鄰域構(gòu)成方法，采用改進(jìn)的蜂群算法(Improved Artificial Bee Colony Algorithm, IABC)求解標(biāo)準(zhǔn)車輛路徑問(wèn)題. 實(shí)驗(yàn)表明，本文提出的算法具有較快的收斂速度，并且能夠穩(wěn)定地得到車輛路徑問(wèn)題的可行解.

1 車輛路徑問(wèn)題的數(shù)據(jù)模型

標(biāo)準(zhǔn)的車輛路徑問(wèn)題一般是指帶裝載限制的車輛路徑問(wèn)題(Capacitated VRP，CVRP)，該問(wèn)題可描述為：從某物流配送中心出發(fā)，使用輛車向個(gè)客戶送貨. 每個(gè)車輛載重為，每個(gè)客戶的需求為，客戶到客戶的距離為，要求合理安排車輛配送路線， 使配送中心行駛距離最短. 定義變量：；. 則標(biāo)準(zhǔn)VRP數(shù)學(xué)模型[4-5]可描述如下：

其中公式(1)為目標(biāo)函數(shù)，即所有車輛行駛距離最??；公式(2)保證每條配送路線上客戶需求總量不超過(guò)每一臺(tái)車輛的運(yùn)載能力；公式(3)保證每一個(gè)客戶只能被訪問(wèn)一次；公式(4)保證每個(gè)客戶只被一輛車服務(wù)；公式(5)用來(lái)消除子回路；公式(6)和(7)表示變量的取值范圍.

2 人工蜂群算法及其改進(jìn)

2.1 基本人工蜂群算法

人工蜂群算法是群智能優(yōu)化算法的一種，主要包含了蜜源和蜂群兩個(gè)核心要素. 蜜源的位置對(duì)應(yīng)于優(yōu)化問(wèn)題的可行解，其質(zhì)量好壞由適應(yīng)度決定. 蜂群包括引領(lǐng)蜂、跟隨蜂和偵察蜂三種類型. 其中，引領(lǐng)蜂與蜜源一一對(duì)應(yīng)，并以一定概率向其它蜜蜂分享蜜源的相關(guān)信息；跟隨蜂根據(jù)引領(lǐng)蜂分享的信息選擇一個(gè)蜜源，蜜源適應(yīng)度越高，跟隨蜂選擇該蜜源的概率P越大；引領(lǐng)蜂和跟隨蜂在所處蜜源的鄰域內(nèi)搜索新蜜源，如果新蜜源好于原來(lái)蜜源則替換之，否則保留原來(lái)蜜源；如果蜜源經(jīng)次搜索未發(fā)生改變，則相應(yīng)蜜蜂轉(zhuǎn)換成偵察蜂，該偵察蜂將隨機(jī)產(chǎn)生新的蜜源位置.

跟隨蜂選擇蜜源的概率公式如下：

其中，為蜜源個(gè)數(shù)，為第個(gè)蜜源的適應(yīng)度.

引領(lǐng)蜂和跟隨蜂的鄰域搜索公式為：

2.2 鄰域生成策略

基本人工蜂群算法與其它智能算法一樣，在求解復(fù)雜問(wèn)題時(shí)表現(xiàn)出收斂能力不足、易陷入局部最優(yōu)等缺點(diǎn). 為克服這些缺點(diǎn)，同時(shí)考慮到本文求解的車輛配送路徑問(wèn)題的離散特性，本文在文獻(xiàn)[17-18]基礎(chǔ)上提出了6種鄰域生成策略，引領(lǐng)蜂、跟隨蜂隨機(jī)選擇其中的一種策略更新解，描述如下：

1)交換鄰域生成策略(One SWAP)，記為1：將原始解內(nèi)兩個(gè)位置數(shù)據(jù)進(jìn)行互換；

2)前插鄰域生成策略(One INSERT)，記為2：將原始解內(nèi)某一位置的數(shù)據(jù)取出并插入到新的位置；

3)倒轉(zhuǎn)鄰域生成策略(One INVERSE)，記為3：將原始解內(nèi)兩個(gè)位置之間的所有數(shù)據(jù)逆序排列；

4)兩次交換鄰域生成策略(Two SWAPs)，記為4：原始解執(zhí)行兩次交換策略(One SWAP)；

5)前插鄰域生成策略(Two INSERTs)，記為5：對(duì)原始解執(zhí)行兩次前插策略(One INSERT)；

6)倒轉(zhuǎn)鄰域生成策略(Two INVERSEs)，記為6：對(duì)原始解執(zhí)行兩次倒轉(zhuǎn)策略(One INVERSE).

2.3 局部搜索算法

為了提高收斂能力、避免算法陷入局部最優(yōu)，本文基于上述的鄰域生成策略構(gòu)建了新的局部搜索算法，用于引領(lǐng)蜂和跟隨蜂更新解的過(guò)程中. 算法步驟如下：

焊接檢驗(yàn)是通過(guò)采用調(diào)查、檢查、度量、試驗(yàn)和監(jiān)測(cè)等方法，把產(chǎn)品的焊接質(zhì)量同其使用要求不斷相比較的過(guò)程。目前在工業(yè)生產(chǎn)中所應(yīng)用的焊接檢驗(yàn)方法主要包括破壞性檢驗(yàn)、非破壞性檢驗(yàn)和聲發(fā)射三大類。

1)建立一個(gè)指定長(zhǎng)度的鄰域列表(NeighborList NL)，如表1所示. 設(shè)原始解為，其鄰域列表長(zhǎng)度為，鄰域生成策略. 鄰域列表中的每行數(shù)據(jù)是對(duì)原始解隨機(jī)選擇生成策略產(chǎn)生，直到填滿該列表，每行數(shù)據(jù)為一個(gè)新解.

2)計(jì)算鄰域列表所有新解的適應(yīng)度，選擇適應(yīng)度最高的新解與原始解比較. 如果大于原始解，則用適應(yīng)度最高的新解替換原始解，反之則保持原始解不變.

3 求解車輛配送路徑問(wèn)題的人工蜂群算法

3.1 問(wèn)題編碼

本文采用自然數(shù)的編碼方式[5]. 0表示配送中心，1～n表示客戶. 每輛車從配送中心出發(fā)，最后返回配送中心，所以每輛車的運(yùn)送路線以0作為開(kāi)始和結(jié)束. 例如，對(duì)于有1個(gè)配送中心、6個(gè)客戶、用2輛車完成配送任務(wù)的問(wèn)題，可以用0-1-2-4-0-6-3-5-0表示一種配送方案. 即車輛1從配送中心出發(fā)，然后服務(wù)了客戶1-2-4，最后返回配送中心；車輛2從配送中心出發(fā)，然后服務(wù)了客戶6-3-5，最后返回配送中心.

3.2 本文采用的改進(jìn)人工蜂群(IABC)算法

1) 設(shè)置算法基本參數(shù)，主要包括食物源規(guī)模、最大迭代次數(shù)和算法終止條件；

2) 隨機(jī)初始化蜂群，計(jì)算每只蜜蜂對(duì)應(yīng)的適應(yīng)度；

3) 引領(lǐng)蜂根據(jù)本文2.3部分設(shè)計(jì)的局部搜索算法產(chǎn)生新解，如果鄰域列表中所有新解的最大適應(yīng)度優(yōu)于原解適應(yīng)度，則替換之，否則保持原解不變；

4)根據(jù)公式(8)計(jì)算跟隨蜂選擇蜜源的概率，然后根據(jù)本文2.3部分設(shè)計(jì)的局域搜索算法鄰域范圍產(chǎn)生新解，如果鄰域列表中所有新解的最大適應(yīng)度優(yōu)于原解適應(yīng)度，則替換之，否則保持原解不變；

6)記錄到目前為止適應(yīng)度最高的解；

7)判斷是否滿足終止條件，如果滿足則輸出最優(yōu)解，算法結(jié)束，否則轉(zhuǎn)步驟3.

4 算例驗(yàn)證及結(jié)果分析

為驗(yàn)證本文算法的有效性，本文以Matlab R2013a為開(kāi)發(fā)環(huán)境，采用Intel Core i3 2.6GHZ、4GB的PC機(jī)，操作系統(tǒng)為Win7.

4.1 小規(guī)模算例

采用文獻(xiàn)[3][5][16]選用的測(cè)試數(shù)據(jù). 該實(shí)例描述如下：1個(gè)配送中心、8個(gè)客戶數(shù)、2輛車. 每輛車載重量為8噸，每個(gè)客戶點(diǎn)的需求量以及客戶點(diǎn)與配送中心的距離詳見(jiàn)文獻(xiàn)[3]，要求合理安排車輛行駛路線， 使所有車輛總的行駛距離最小.

實(shí)驗(yàn)參數(shù)設(shè)置如下：種群規(guī)模設(shè)置為60，最大迭代次數(shù)為50，鄰域列表長(zhǎng)度為5，算法運(yùn)行20次. 實(shí)驗(yàn)結(jié)果表明，本文算法每次運(yùn)行都能得到最優(yōu)解67.5，得到最優(yōu)解所需迭代次數(shù)和需要花費(fèi)的時(shí)間如表2所示. 此外，將相同種群規(guī)模和迭代次數(shù)的該實(shí)例采用不同算法運(yùn)行的結(jié)果如表3所示，算法包括：標(biāo)準(zhǔn)遺傳算法(GA) 和雙種群遺傳算法(DPGA)[19]、混合遺傳算法(HGA)[20]、改進(jìn)微粒群算法(MPSO)[1]、標(biāo)準(zhǔn)人工蜂群算法(ABC)[16]和本文算法.

由表3中的數(shù)據(jù)比較可以看出，在種群規(guī)模和迭代次數(shù)一致的前提下，本文提出的算法的無(wú)論從穩(wěn)定性、可靠性還是速度方面都優(yōu)于表中所列的其它算法. 人工蜂群算法作為一種新型的群智能優(yōu)化算法，在求解車輛配送路徑方面有一定優(yōu)勢(shì)，仍存在易陷于局部最優(yōu)等缺陷. 基本人工蜂群算法中加入局部搜索優(yōu)化后，該缺陷得到了一定改善，求解效果和效率都得以提升.

4.2 大規(guī)模算例

上述實(shí)例規(guī)模較小，不能有效驗(yàn)證算法對(duì)較大規(guī)模問(wèn)題的適用性. VRP LIB是國(guó)際上通用的測(cè)試VRP問(wèn)量的算例庫(kù)，可用來(lái)檢驗(yàn)算法的有效性與性能，在此，選用其中兩個(gè)較大規(guī)模車輛路徑問(wèn)題基準(zhǔn)測(cè)試算例：E-n22- k4.vrp(1個(gè)配送中心、21個(gè)客戶、4輛車、最優(yōu)解為375)和E-n33-k4.vrp(1個(gè)配送中心、32個(gè)客戶、4輛車、最優(yōu)解為835)進(jìn)行仿真實(shí)驗(yàn). 實(shí)驗(yàn)結(jié)果如表4所示. 表4中改進(jìn)遺傳算法實(shí)驗(yàn)數(shù)據(jù)來(lái)自文獻(xiàn)[4]，人工蜂群算法實(shí)驗(yàn)數(shù)據(jù)來(lái)自文獻(xiàn)[16]. 每個(gè)算法運(yùn)行10次. 圖1為算例E-n22- k4采用三種算法在不同種群規(guī)模和迭代次數(shù)下的收斂情況比較圖.

從表4的數(shù)據(jù)可以看出，種群和迭代次數(shù)越小，不同算法之間的效果差異越明顯；種群規(guī)模和迭代次數(shù)越大，相同算法得到解的質(zhì)量越高；當(dāng)種群和迭代次數(shù)都增大到一定值時(shí)，二者對(duì)運(yùn)行結(jié)果的影響變小. 本文算法在這兩個(gè)算例下仍然保持了較好的有效性、穩(wěn)定性和較高的運(yùn)算效率. 在種群規(guī)模較小，迭代次數(shù)較少的情況下，本文算法相較另兩種算法的優(yōu)勢(shì)更加明顯，這意味著在計(jì)算資源較少和時(shí)間較緊的情況下，本文算法的有效性更高.

比較算例E-n33-k4和算例E-n22- k4的運(yùn)行結(jié)果，前者比后者客戶數(shù)增加了11，即問(wèn)題規(guī)模增大，搜索空間相應(yīng)增大. 此時(shí)，改進(jìn)遺傳算法和基本人工蜂群算法即使增大種群規(guī)模和迭代次數(shù)，效果也并不明顯(如得到最優(yōu)解的次數(shù)為0). 其原因是VRP屬于NP-Hard問(wèn)題，客戶數(shù)增加導(dǎo)致搜索空間急劇增大. 本文算法由于設(shè)計(jì)了較為合理的鄰域結(jié)構(gòu)，提高了算法的收斂速度，同時(shí)避免了早熟，因而能在問(wèn)題規(guī)模增大時(shí)仍能得到較優(yōu)的求解效果.

從圖1中可以看出，本文算法在不同種群規(guī)模和迭代次數(shù)中都可以穩(wěn)定地得到較優(yōu)的解. 沒(méi)有鄰域優(yōu)化的基本蜂群算法相較于改進(jìn)遺傳算法，求解結(jié)果也有一定的優(yōu)勢(shì). 實(shí)驗(yàn)結(jié)果驗(yàn)證了文獻(xiàn)[9][13]的結(jié)論，即人工蜂群算法因其較好的全局搜索能力等特點(diǎn)，在求解優(yōu)化問(wèn)題相較于其它智能算法更具有競(jìng)爭(zhēng)力. 同時(shí)，人工蜂群算法的開(kāi)發(fā)能力較弱，需要構(gòu)建較為合理的鄰域搜索策略，以提高其局部尋優(yōu)速度.

5 結(jié)語(yǔ)

本文提出了一種改進(jìn)的離散人工蜂群算法，用于求解車輛配送路徑問(wèn)題. 為避免基本人工蜂群算法收斂速度較慢和陷入局部最優(yōu)等問(wèn)題，設(shè)計(jì)了新的鄰域生成策略和局部搜索算法，用于更新引領(lǐng)蜂和跟隨蜂的原始解. 通過(guò)小規(guī)模和大規(guī)模算例的實(shí)驗(yàn)，驗(yàn)證了本文算法的有效性和穩(wěn)定性，以及人工蜂群算法在車輛配送路徑問(wèn)題求解中運(yùn)用局部搜索算法進(jìn)行優(yōu)化的必要性.

[1] 肖健梅, 李軍軍, 王錫淮. 求解車輛路徑問(wèn)題的改進(jìn)微粒群優(yōu)化算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2005, 11(4): 577-581.

[2] 劉 娜, 雷秀娟. 免疫PSO算法求解多庫(kù)房帶時(shí)間窗VRP[J]. 計(jì)算機(jī)工程與應(yīng)用, 2010, 46(5): 236-239.

[3] 劉芳華, 趙建民, 朱信忠. 基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化的研究[J]. 計(jì)算機(jī)技術(shù)與發(fā)展, 2009, 19(7): 83-86.

[4] 周生偉, 蔣同海, 張榮輝. 改進(jìn)遺傳算法求解VRP問(wèn)題[J]. 計(jì)算機(jī)仿真, 2012, 30(12): 140-143, 157.

[5] 周艷聰, 孫曉晨, 余偉翔. 基于改進(jìn)遺傳算法的物流配送路徑優(yōu)化研究[J]. 計(jì)算機(jī)工程與科學(xué), 2012, 34(10): 118-122.

[6] 張澤彬, 郝志峰, 黃 翰, 等. 求解車輛路徑問(wèn)題的多鄰域下降搜索蟻群優(yōu)化算法[J]. 南京大學(xué)學(xué)報(bào): 自然科學(xué)版, 2012, 48(1): 91-98.

[7] 孫 晶, 白艷萍. 改進(jìn)的混合型蟻群算法在VRP問(wèn)題中的應(yīng)用[J]. 黑龍江大學(xué)自然科學(xué)學(xué)報(bào), 2014, 31(3): 328-334.

[8] 徐洪麗, 錢(qián) 旭, 岳 訓(xùn), 等. 一種新的基于logistic混沌映像的自適應(yīng)混沌蟻群優(yōu)化算法求解動(dòng)態(tài)車輛路徑問(wèn)題[J]. 計(jì)算機(jī)應(yīng)用研究, 2012, 29(6): 2058-2060.

[9] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Kayseri: Eroiyes University, 2005.

[10] SINGH A. An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem[J]. Applied Soft Computing, 2009, 9(2): 625-631.

[11] PAN Q K, TASGETIREN M F, SUGANTHAN P N, CHUA T J. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2010, 181(12): 2455-2468.

[12] XU CHUNFAN, DUAN LLAIBIN. Artificial bee colony optimized edge potential function approach to target recognition for low-altitude aircraft[J].

Pattern Recognition Letters, 2010, 31(13): 1759-1772.

[13] AKAY B, KARABOGA D. A Modified artificial for real-parameter optimization[J]. Information Sciences, 2012, 192(6): 120-142.

[14] 張 濤, 陳 忠, 呂一兵. 求解最短路徑問(wèn)題的一種改進(jìn)的人工蜂群算法[J]. 青海師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2013(1): 5-7, 13.

[15] 林鎮(zhèn)澤. 求解雙層車輛路徑問(wèn)題的改進(jìn)人工蜂群算法[D]. 廣州: 華南理工大學(xué), 2014.

[16] 王志剛, 夏慧明. 求解車輛路徑問(wèn)題的人工蜂群算法[J]. 計(jì)算機(jī)工程與科學(xué), 2014, 36(6): 1088-1094.

[17] 桑紅燕, 高 亮, 李新宇. 求解批量流水線調(diào)度問(wèn)題的離散蜂群算法[J]. 中國(guó)機(jī)械工程, 2011, 22(18): 2195-2202.

[18] LI X, YIN M. A discrete artificial bee colony algorithm with composite mutation strategies for permutation flow shop scheduling problem[J]. Scientia Iranica, doi:10.1016/j.scient.2012.10.034: 1921-1935.

[19] 趙燕偉, 吳 斌, 蔣 麗, 等. 車.輛路徑問(wèn)題的雙種群遺傳算法求解方法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2004, 10(3): 303-306.

[20] 姜昌華, 戴樹(shù)貴, 胡幼華. 求解車輛路徑問(wèn)題的混合遺傳算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2007, 13(10): 2047-2052.

(責(zé)任編輯：陳 丹)

Solving Vehicle Routing Problem by an Improved Artificial Bee Colony Algorithm

JIANG Ting1, 2

(1. Department of Information Engineering, Anhui Economic Management College, Hefei 230059, China;2. School of Management, Hefei University of Technology, Hefei 230009, China )

In this paper, we use an improved artificial bee colony algorithm(IABC)for solving standard vehicle routing problem. In order to avoid slow convergence and local optimum, we propose six neighborhood generating strategies. Meanwhile, we design a new local search algorithm based on the strategies. The leader bees and follower bees update the current solution in the neighborhood by this algorithm. Through the simulation experiment of large and small scale examples, the proposed algorithm was compared with some intelligent optimization algorithms and the basic artificial bee colony algorithm. Experimental results show that the proposed algorithm has good performance in both effectiveness and stability.

Vehicle routing problem; Improved artificial bee colony algorithm; Neighborhood generating strategy; Local search algorithm

TP391

A

2095-4476(2016)02-0009-06

2016-02-20;

2016-02-29

安徽省哲學(xué)社科規(guī)劃項(xiàng)目(AHSKY2015D71); 安徽省社科創(chuàng)新發(fā)展研究課題(A2015020); 安徽省高校優(yōu)秀青年人才基金重點(diǎn)項(xiàng)目(2013SQRL111ZD)

姜 婷(1976— ), 女, 安徽滁州人, 安徽經(jīng)濟(jì)管理學(xué)院信息工程系副教授, 合肥工業(yè)大學(xué)管理學(xué)院博士研究生, 主要研究方向: 決策支持系統(tǒng), 群體智能.