求解需求可拆分車輛路徑問題的人工蜂群算法

姜婷

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

求解需求可拆分車輛路徑問題的人工蜂群算法

姜婷1,2

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

研究了需求可拆分的車輛路徑問題(SDVRP)的基本數(shù)據(jù)模型，分析了相關解的基本特點，提出了一種改進的人工蜂群算法進行求解。首先，在不考慮車輛容量和拆分需求的前提下，求出TSP大路徑；然后，對TSP大路徑進行切割，在切割的地方對客戶點的需求進行拆分；最后，在前述操作基礎上形成初始解，采用改進人工蜂群算法進行優(yōu)化。在人工蜂群階段，三種蜜蜂在全局和鄰域范圍內不斷優(yōu)化當前解。通過仿真實驗與其它算法對比，驗證了提出的算法在有效性和穩(wěn)定性上，具有良好的效果。

需求可拆分；車輛路徑問題；人工蜂群算法；路徑切割

引言

車輛路徑問題(VRP)是物流運輸和配送環(huán)節(jié)的重要前沿問題，但傳統(tǒng)的VRP問題大都假設每個客戶的配送需求只能由單輛車在單次服務中完成。然而，現(xiàn)實物流中可能出現(xiàn)客戶需求量超過車輛的最大載重能力的情況，因此必須對客戶需求進行拆分。1989年，DROR等人[1]首度提出需求可拆分車輛路徑問題( Split Delivery Vehicle Routing Problem，SDVRP)。Archetti等人[2-4]證明，對客戶需求進行合理拆分，會比傳統(tǒng)VRP的解決方案減少總運輸距離和派車數(shù)量，進而降低物流運作的成本。

與傳統(tǒng)VRP一樣，SDVRP的求解算法分為精確算法和近似算法。精確算法只能求解規(guī)模很小的問題，不能適應發(fā)展迅猛的物流行業(yè)中的車輛路徑問題現(xiàn)狀，因此求解SDVRP一般采用近似算法，主要是啟發(fā)式算法和元啟發(fā)式算法。DROR等人[5]最早提出了采用局部搜索算法解決SDVRP。其后，很多研究者采用禁忌算法求解SDVRP并取得了一定進展。Archetti等人[3]提出了簡單領域搜索禁忌算法、Alemant等人[6]提出了詞匯構造禁忌探索算法、Berbotto[7]提出了隨機粒度禁忌搜索算法、孟凡超等[8]提出了多鄰域搜索禁忌算法、熊浩等[9]提出了三階段禁忌算法分別求解SDVRP。除此之外，也出現(xiàn)了其他啟發(fā)式算法求解該問題的研究成果。如Boudia[10]提出的基因算法，Wilck[11]提出的遺傳算法，隋露斯[12]提出的蟻群算法，劉旺盛等[13]和向婷等[14]提出的聚類算法，汪婷婷[15]、姜婷[16]等提出的蜂群優(yōu)化算法(BCO)，對SDVRP的求解進行了一些有益的嘗試，開拓了新的研究方向。

人工蜂群算法(Artificial Bee Colony, ABC)是群智能算法的一種，于2005年由Karaboga[17]提出，具有參數(shù)少，魯棒性強的特點，在求解NP問題上取得了較好的效果。目前，利用ABC算法求解需求可拆分車輛路徑問題的相關研究很少。本文在已有研究成果基礎上，將離散人工蜂群算法與SDVRP的特征相結合，探索構造了一種先求解再分組的算法，得到SDVRP的近似最優(yōu)解。

1SDVRP的數(shù)學模型

為簡化問題及便于進行算法效果比較，本文設定的研究對象為單車場、單車型、沒有時間窗限制、純裝貨(或純卸貨)的SDVRP，采用大多文獻通用的模型進行研究。具體描述如下：有n個客戶，由同一車場最大載重量為W的多輛車進行服務，每個客戶的需求可以被一輛或者多輛車滿足，求解當總行駛距離最短時每個車輛的行駛路徑。

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中，式(1)是SDVRP的目標函數(shù)，即要求總線路距離最短；式(2)表示進入某點總的車輛數(shù)與離開某點總的車輛數(shù)相等；式(3)表示每個客戶至少被訪問一次；式(4)表示線路中的子回路被消除；式(5)表示表示每輛車裝載的總量不能超過其運載能力上限；式(6)表示當車輛訪問某客戶點時該客戶才能被服務；式(7)表示客戶點需求被完全滿足；式(8)表示每條線路滿足客戶需求量不會超過客戶需求的總量。

2求解SDVRP的人工蜂群算法

人工蜂群算法是模擬蜜蜂的采蜜行為提出的算法，將求解問題的目標具體化為個體適應度值進行求解。雇傭蜂、觀察蜂和偵查蜂在全局和鄰域范圍內搜索優(yōu)質蜜源，通過不斷迭代，以適應度高的解不斷替代適應度低的解，逐步提高解的質量，直到達到結束條件。

本文求解SDVRP的基本思路是：首先按旅行商問題(Traveling Salesman Problem，TSP)進行求解，構造一個大TSP解。然后以車輛容量為標準對該解進行切割和拆分，尋找最優(yōu)切割方案使總路徑長度最低，得到最優(yōu)近似解。其中，大TSP解指的是在不考慮車輛容量限制和客戶點需求拆分的前提下，包括車場和顧客所有節(jié)點的TSP路線組合。如1個車場8個客戶點的某個大TSP解是0-1-3-6-2-5-4-7-8-0，切割后的解是0-1-3-6-2-0-5-4-7-8-0?？梢钥闯觯瑥墓?jié)點2-5的連接處進行了切割，即原本直接連接的節(jié)點2和節(jié)點5改為分別與車場相連。切割增加的成本為2-5的節(jié)約值，即節(jié)點2和節(jié)點5到車場的距離之和減去節(jié)點2至節(jié)點5的距離。

2.1解的基本分析

通過對文獻[1,3,5,13]研究，假設包括客戶點與車場在內所有的點與點距離關系符合三角形不等式(即兩邊之和大于第三邊)，SDVRP的求解被證明有如下特點：

(1)如果客戶需求與車輛最大運載能力相等，則該客戶點的需求不應拆分。

(2) 客戶點被拆分的數(shù)量小于路線的總數(shù)量。

(3) 如果問題有可行解，則經(jīng)過優(yōu)化的解的任意兩條線路最多只會存在一個共同點。

根據(jù)第(3)點，文獻[9]作了相關分析，證明子路徑可以在大TSP解的基礎上在共同點處進行切割得到，同時對共同點的需求進行拆分。

2.2算法步驟

本文提出的SDVRP的求解方法屬于先求解再分組的類型：第一階段不考慮車輛容量和拆分需求，求出TSP大路徑；第二階段對TSP大路徑進行切割，在切割的地方對客戶點的需求進行拆分，切割后形成的多條子路徑滿足容量限制。在此基礎上形成初始解，采用人工蜂群算法進行優(yōu)化。具體步驟如下：

(1) 算法初始化

設置蜂群規(guī)模SN、最大迭代次數(shù)MaxCycle、鄰域最大搜索次數(shù)limit。

(2) 問題編碼和形成基礎結構

將車場和客戶點進行編碼，車場編號為0,客戶編號為自然數(shù)。在此基礎上，采用2-opt形成TSP大路徑。為降低編碼難度，該階段不考慮車輛容量和拆分需求，只提供一個基礎結構。

(3) 生成初始解

對TSP大路徑進行切割，同時在切割點進行需求拆分，形成子路徑。該階段采用簡單切割方法，即累加客戶需求量直到達到車輛的最大容量。將不同切割方案形成的路徑組合按目標函數(shù)值降序排列，取前SN個作為初始解，記為x1,x2,…,xSN。將前一半設為當前解，最優(yōu)解為x1。

(4) 迭代改進

步驟1針對每一個當前解進行如下操作：將所有的客戶節(jié)點按照其刪除節(jié)約代價降序排列并形成序列，然后此基礎上進行刪除和重新插入操作，選擇插入代價最小的與原解進行比較，該步驟相當于雇傭蜂的鄰域搜索。如果新解的目標函數(shù)值小于原解，則代替原解，否則保持原解不變。該步驟具體過程如算法1所示。

算法1領域搜索算法

輸入：當前解s

輸出：新解s′

(1)從當前解s中刪除客戶節(jié)點i,將形成的解賦值為s′；

(2)將i重新插入到不同位置，形成序列Li；

(3)計算s′需求被全部服務的最小插入代價minf，路徑設為rf；

(4)計算s′需求被部分服務的最小插入代價minp，路徑設為rp，計算該路徑能滿足需求的前m個元素；

(5)比較minf和minp，如果前者小于等于后者，則將節(jié)點i的需求拆分并插入到路徑rf中；否則將滿足需求的前m個元素rp插入到路徑rp中；

(6)產(chǎn)生并輸出新解s′

步驟2將步驟1產(chǎn)生新解的適應度除以所有解的適應度之和得到跟隨蜂的跟隨概率。然后繼續(xù)采用步驟1的局部搜索操作，找到適應度更高的解。

步驟3偵查蜂通過隨機方式產(chǎn)生新解，替換掉超過limit次數(shù)未發(fā)生改變的解；

步驟4記錄到目前為止適應度最高的解；

步驟5判斷是否滿足終止條件，如果滿足則輸出最優(yōu)解。

3實驗仿真及結果分析

為驗證算法有效性，本文采用文獻[13]中的數(shù)據(jù)進行測試，算法由Matlab R2013a實現(xiàn)，在操作系統(tǒng)為Win7、CPU為Intel Core i3 2.6GHZ、內存為4GB的計算機上運行。

實驗數(shù)據(jù)為15個客戶點的SDVRP問題，車輛的最大運載量為500，車場的坐標為原點?？蛻酎c信息見表1。

表1客戶點的信息

本文取種群規(guī)模設置為60，最大迭代次數(shù)為50，搜索閾值次數(shù)為10，算法運行10次。計算采用歐幾里得距離。采用本文提出的算法，10次實驗結果見表2，最優(yōu)路徑見表3，與其他算法的比較結果見表4。

表2本文算法求解結果

表3本文算法求得最優(yōu)路徑

表4不同算法的最優(yōu)結果

以上實驗結果表明，人工蜂群算法在求解SDVRP是有效且穩(wěn)定的，求解速度較快，為1～2s。最優(yōu)解為1757.6 km，比傳統(tǒng)VRP方法降低了11.68%。本文算法效果優(yōu)于群智能算法之一的蟻群算法，接近并略好于聚類和BCO算法。實驗表明，本文算法說明對客戶需求的拆分可以縮短車輛路徑，從而讓降低物流成本成為可能。

4結束語

需求可拆分的車輛路徑問題是對傳統(tǒng)VRP的一定改變，客戶的需求可以被不止一輛車服務，因此需求可以被拆分，這對節(jié)約車輛成本、縮短行駛路徑是有益的。本文在已有研究的基礎上總結了該問題求解的特點，提出了采用改進的人工蜂群進行求解。該算法首先在不考慮車輛容量限制和拆分需求的前提下使用2-OPT設計大TSP路徑，然后對TSP進行切割和拆分，形成初始解。接著，通過雇傭蜂、跟隨蜂、偵查蜂在全局和鄰域范圍內不斷優(yōu)化當前解，直到達到限制條件。本文算法拓寬了SDVRP求解的思路，但算法還有一定的改進空間，還需采用更多的數(shù)據(jù)案例進行測試并驗證。

[1] DROR M,TRUDEAUP.Savings by split delivery routing[J].Transportation Science,1989,23(2):141-145.

[2] ARCHETTIC C,MANSINI R,SPERANZA M G.Complexity and reducibility of the skip delivery problem[J].Transportation Science,2005,39(2):182-187.

[3] ARCHETTICC,SAVELSBERGH M W,SPERANZA M G.Worst-caseanalysis for split delivery vehicle routing problems[J].Transportation Science,2006,40(2):226-234.

[4] ARCHETTIC C,FEILLET D,GENDREAU M,etal.Complexity of the VRP and SDVRP[J].Transportation Research Part C:Emerging Technologies,2011,19(5):741-750.

[5] DROR M,TRUDEAUP.Split delivery routing[J].Naval Research Logistics,1990,37(3):383-402.

[6] ALEMAN R E,HILL R R.A tabu search with vocabulary building approach for the vehicle routing problem with split demands[J].International Journal of Metaheuristics,2010,1(1):55-80.

[7] BERBOTTO L,GARCIA S,NOGALES F J.A randomized granular tabu search heuristic vehicle routing problem with for the split delivery vehiclerouting problem[J].Annals of Operations Research,2014,222(1):153-173.

[8] 孟凡超,陸志強,孫小明.需求可拆分車輛路徑問題的禁忌搜索算法[J].計算機輔助工程,2010,19(1):78-83.

[9] 熊浩,鄢慧麗.需求可拆分車輛路徑問題的三階段禁忌算法[J].系統(tǒng)工程理論與實踐,2015,35(5):1230-1235.

[10] BOUDIA M,PRINS C,REGHIOUI M.An effective memetic algorithm with population management for the split delivery vehicle routing problem[C]//Proceedings of the 4th International Workshop on Hybrid Metaheuristics(HM 2007),Dortmund,Germany,October 8-9,2007:16-30.

[11] WILCK IV J H, CAVALIER T M.A genetic algorithm for the split delivery vehicle routing problem[J].American Journal of Operations Research,2012,2(2):207-216.

[12] 隋露斯,唐加福,潘震東,等.用蟻群算法求解需求可拆分車輛路徑問題[C]//2008年中國控制與決策會議論文集.沈陽:東北大學出版社,2008:997-1001.

[13] 劉旺盛,楊帆,李茂青,等.需求可拆分車輛路徑問題的聚類求解算法[J].控制與決策,2012,27(4):535-541.

[14] 向婷,潘大志.求解需求可拆分車輛路徑問題的聚類算法[J].計算機應用,2016,36(11):3141-3145.

[15] 汪婷婷,倪郁東,何文玲.需求可拆分車輛路徑問題的蜂群優(yōu)化算法[J].合肥工業(yè)大學學報:自然科學版,2014,37(8):1015-1018,1024.

[16] 姜婷.求解配送中心選址的改進人工蜂群算法[J].四川理工學院學報:自然科學版,2016,29(1):24-28.[17] KARABOGA D.An idea based on honey bee swarm for numerical optimization[R].Kayseri:Computer Engineering Department,EngineeringFaculty,Eroiyes University,2005.

Artificial Bee Colony Algorithm for Split Delivery Vehicle Routing Problem

JIANGTing1,2

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

Basic data model of split delivery vehicle routing problem (SDVRP) is studied. Based on the analysis of the basic characteristics of the related solutions, an improved artificial bee colony algorithm is proposed to solve the problem. First,the big TSP path is sought out in the premise without considering the capacity of the vehicle and the requirements of split. Second,the big TSP path is split, meanwhile the customer's needs is cut. Finally,the initial solution is formed on the basis of the above operations.In the phase of artificial bee colony, the current solution is continuously optimized by three kinds of bees in the global scale and neighborhood. Compared with other algorithms, the simulation results show that the proposed algorithm is effective and stable.

split delivery vehicle routing problem; vehicle routing problem; artificial bee colony algorithm; path cut

2017-04-19

國家自然科學基金項目(71271071);安徽省哲學社科規(guī)劃項目(AHSKY2015D71);安徽省社科創(chuàng)新發(fā)展研究課題(A2015020)

姜 婷(1976-),女,安徽滁州人,副教授,博士生,主要從事決策支持系統(tǒng)、群體智能方面的研究,(E-mail)744583170@qq.com

1673-1549(2017)03-0006-04

10.11863/j.suse.2017.03.02

TP391

A