姜婷

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

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

姜婷1,2

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

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

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

引言

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

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

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

1SDVRP的數(shù)學(xué)模型

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

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

2求解SDVRP的人工蜂群算法

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

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

2.1解的基本分析

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

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

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

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

根據(jù)第(3)點(diǎn)，文獻(xiàn)[9]作了相關(guān)分析，證明子路徑可以在大TSP解的基礎(chǔ)上在共同點(diǎn)處進(jìn)行切割得到，同時(shí)對(duì)共同點(diǎn)的需求進(jìn)行拆分。

2.2算法步驟

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

(1) 算法初始化

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

(2) 問題編碼和形成基礎(chǔ)結(jié)構(gòu)

將車場(chǎng)和客戶點(diǎn)進(jìn)行編碼，車場(chǎng)編號(hào)為0,客戶編號(hào)為自然數(shù)。在此基礎(chǔ)上，采用2-opt形成TSP大路徑。為降低編碼難度，該階段不考慮車輛容量和拆分需求，只提供一個(gè)基礎(chǔ)結(jié)構(gòu)。

(3) 生成初始解

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

(4) 迭代改進(jìn)

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

算法1領(lǐng)域搜索算法

輸入：當(dāng)前解s

輸出：新解s′

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

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

(3)計(jì)算s′需求被全部服務(wù)的最小插入代價(jià)minf，路徑設(shè)為rf；

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

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

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

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

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

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

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

3實(shí)驗(yàn)仿真及結(jié)果分析

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

實(shí)驗(yàn)數(shù)據(jù)為15個(gè)客戶點(diǎn)的SDVRP問題，車輛的最大運(yùn)載量為500，車場(chǎng)的坐標(biāo)為原點(diǎn)?？蛻酎c(diǎn)信息見表1。

表1客戶點(diǎn)的信息

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

表2本文算法求解結(jié)果

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

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

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

4結(jié)束語

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

[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] 孟凡超,陸志強(qiáng),孫小明.需求可拆分車輛路徑問題的禁忌搜索算法[J].計(jì)算機(jī)輔助工程,2010,19(1):78-83.

[9] 熊浩,鄢慧麗.需求可拆分車輛路徑問題的三階段禁忌算法[J].系統(tǒng)工程理論與實(shí)踐,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年中國(guó)控制與決策會(huì)議論文集.沈陽:東北大學(xué)出版社,2008:997-1001.

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

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

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

[16] 姜婷.求解配送中心選址的改進(jìn)人工蜂群算法[J].四川理工學(xué)院學(xué)報(bào):自然科學(xué)版,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

國(guó)家自然科學(xué)基金項(xiàng)目(71271071);安徽省哲學(xué)社科規(guī)劃項(xiàng)目(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