基于改進離散蜂群算法的車輛路徑問題求解

姜 婷

?

基于改進離散蜂群算法的車輛路徑問題求解

姜 婷1,2

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

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

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

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

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

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

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

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

2 人工蜂群算法及其改進

2.1 基本人工蜂群算法

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

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

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

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

2.2 鄰域生成策略

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

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

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

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

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

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

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

2.3 局部搜索算法

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

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

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

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

3 求解車輛配送路徑問題的人工蜂群算法

3.1 問題編碼

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

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

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

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

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

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

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

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

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

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

4.1 小規(guī)模算例

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

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

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

4.2 大規(guī)模算例

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

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

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

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

5 結(jié)語

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

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

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

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

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

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

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

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

[8] 徐洪麗, 錢 旭, 岳 訓, 等. 一種新的基于logistic混沌映像的自適應(yīng)混沌蟻群優(yōu)化算法求解動態(tài)車輛路徑問題[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] 張 濤, 陳 忠, 呂一兵. 求解最短路徑問題的一種改進的人工蜂群算法[J]. 青海師范大學學報: 自然科學版, 2013(1): 5-7, 13.

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

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

[17] 桑紅燕, 高 亮, 李新宇. 求解批量流水線調(diào)度問題的離散蜂群算法[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] 趙燕偉, 吳 斌, 蔣 麗, 等. 車.輛路徑問題的雙種群遺傳算法求解方法[J]. 計算機集成制造系統(tǒng), 2004, 10(3): 303-306.

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

(責任編輯：陳 丹)

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

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

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