改進(jìn)變鄰域搜索算法在求解VRPMT的應(yīng)用*

宋 強(qiáng) 杜暖男

(廣東理工學(xué)院信息工程系1) 526100 肇慶) (平頂山工業(yè)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與軟件工程學(xué)院2) 平頂山 467001)

改進(jìn)變鄰域搜索算法在求解VRPMT的應(yīng)用*

宋 強(qiáng)1)杜暖男2)

(廣東理工學(xué)院信息工程系1)526100 肇慶) (平頂山工業(yè)職業(yè)技術(shù)學(xué)院計(jì)算機(jī)與軟件工程學(xué)院2)平頂山 467001)

多行程車輛路徑問(wèn)題是標(biāo)準(zhǔn)車輛路徑問(wèn)題的一個(gè)變體，每個(gè)車輛在運(yùn)行期間可以使用不止一次.對(duì)于這種NP-HARD問(wèn)題，提出了1個(gè)改進(jìn)變鄰域搜索算法并設(shè)計(jì)了4個(gè)鄰域結(jié)構(gòu)用于求解和制定多行程路徑問(wèn)題的調(diào)度規(guī)劃.該算法測(cè)試了1組標(biāo)準(zhǔn)實(shí)例問(wèn)題，獲得的解決方法與文獻(xiàn)中提出的5種算法進(jìn)行比較，并得到了較好的結(jié)果.

車輛路徑問(wèn)題；多行程；變鄰域搜索；抖動(dòng)

0 引 言

標(biāo)準(zhǔn)的車輛路徑問(wèn)題(vehicle routing problem，VRP)指的是具有一定容量的相同車輛訪問(wèn)或者交付貨物給若干客戶.其目的是對(duì)車輛行程進(jìn)行規(guī)劃，以最小化總成本 (如行駛時(shí)間、行駛距離等)來(lái)服務(wù)和滿足所有客戶需求.每個(gè)客戶必須只能被訪問(wèn)1次，每個(gè)行程必須開始和結(jié)束于倉(cāng)庫(kù).每輛車的交付貨物的數(shù)量不得超過(guò)車輛的容量，行駛距離不得超過(guò)預(yù)先定義的范圍.

文中主要研究了多行程車輛路徑問(wèn)題(vehicle routing problem with multiple trips，VRPMT)，這是標(biāo)準(zhǔn)VRP的一個(gè)變種，特點(diǎn)是每輛車在工作期間可以使用不止1次.

針對(duì)多行程車輛路徑問(wèn)題的研究，國(guó)內(nèi)研究文獻(xiàn)較少.宋強(qiáng)等[1]為了同時(shí)解決多行程車輛路徑問(wèn)題和配送中心定位問(wèn)題，采用模擬退火的邏輯和交換算法來(lái)獲得最優(yōu)路線，并改善了模擬退火算法中當(dāng)前溫度控制的位置.張媛媛等[2]研究了多行程帶時(shí)間窗口的車輛調(diào)度問(wèn)題，設(shè)計(jì)了計(jì)算路線時(shí)間窗口的具體數(shù)學(xué)模型，并且通過(guò)數(shù)學(xué)推導(dǎo)證明了該時(shí)間窗口是等待費(fèi)用最小的服務(wù)時(shí)間窗口.許爭(zhēng)爭(zhēng)等[3]考慮車輛容量和繞行時(shí)間限制等因素提出了1種基于協(xié)作的3階段算法，通過(guò)案例分析證明了該方法可以更好的提供車輛調(diào)度方案.在國(guó)外，F(xiàn)leischmann[4]首先對(duì)這個(gè)VRPMT進(jìn)行了研究，他針對(duì)著名的節(jié)約算法提出了1個(gè)修改方法和一個(gè)裝箱啟發(fā)式算法.之后許多文獻(xiàn)都提出了啟發(fā)式算法解決問(wèn)題，如3段論啟發(fā)式算法、禁忌搜索算法、1個(gè)多階段構(gòu)建的啟發(fā)式算法、基于自適應(yīng)記憶過(guò)程修改的啟發(fā)式算法及一個(gè)混合遺傳算法[5-9].但是，以上文獻(xiàn)中沒(méi)有研究人員采用改進(jìn)變鄰域算法對(duì)這個(gè)問(wèn)題進(jìn)行相應(yīng)的研究.

變鄰域搜索算法主要由鄰域轉(zhuǎn)換機(jī)制(抖動(dòng))和局部搜索算法組成[10].變鄰域算法的特點(diǎn)是容易找到當(dāng)前解域范圍內(nèi)的最優(yōu)解.其中局部搜索算法構(gòu)造了只接受更優(yōu)解作為下1次操作的個(gè)體，是1種功能強(qiáng)大的局部探索過(guò)程，而抖動(dòng)不考慮解的優(yōu)劣，只要滿足條件即可，很容易產(chǎn)生更多未探索過(guò)的新解.兩者結(jié)合達(dá)到某種平衡就能找到所有問(wèn)題的全局最優(yōu)解.

基于此，很多研究采用變鄰域算法來(lái)求解各種問(wèn)題.張曉楠等[11]采用變鄰域分散搜索算法來(lái)求解同時(shí)配集貨的定位-路線問(wèn)題，在保留組合策略的全局搜索能力的基礎(chǔ)上，再運(yùn)用變鄰域搜索算法進(jìn)行局部開發(fā)來(lái)提高可行解質(zhì)量.潘全科等[12]為了解決作業(yè)車間調(diào)度問(wèn)題，充分利用了粒子群算法和變鄰域搜索算法的互補(bǔ)性能，提出1種新的粒子群-變鄰域搜索的混合算法.戈軍等[13]采用聚類方法完成客戶分配和路線規(guī)劃的初始解構(gòu)建，設(shè)計(jì)了最佳改進(jìn)策略實(shí)現(xiàn)算法以獲得在求解質(zhì)量和運(yùn)行時(shí)間上的最佳平衡.

文中提出了1種改進(jìn)變鄰域搜索算法(variable neighborhood search，VNS)來(lái)解決VRPMT，在該算法中，采用4個(gè)不同的鄰域結(jié)構(gòu)，其中2個(gè)用于最小化行程總長(zhǎng)度和超時(shí)，另外2個(gè)用于最小化超時(shí).在抖動(dòng)步驟中，在概率分布的基礎(chǔ)上采用了3種類型的鄰域，通過(guò)比較研究，結(jié)果說(shuō)明提出的算法優(yōu)越于其他研究方法.

1 用于VRPMT的變鄰域搜索

1.1 符號(hào)定義

車輛i的超時(shí)由下列表達(dá)式給出

max(0,DTi-T)

(1)

最長(zhǎng)行駛比率(LTR)用于提供現(xiàn)有方案中的最長(zhǎng)(最差的)超時(shí).

(2)

1.2 方案展示

1.3 初始解

1.4 評(píng)價(jià)函數(shù)

提出的目標(biāo)函數(shù)類似于文獻(xiàn)[8]提出的函數(shù).它是采用1個(gè)由總行駛時(shí)間、超時(shí)和超容量懲罰的相關(guān)計(jì)算得到的1個(gè)動(dòng)態(tài)的函數(shù).

α和β參數(shù)以動(dòng)態(tài)的方式進(jìn)行調(diào)整，以較小的步驟進(jìn)行鄰域擴(kuò)展，并增加插入和交換的移動(dòng)能力.

(4)

1.5 變鄰域下降算法

該變鄰域下降算法采用4個(gè)鄰域結(jié)構(gòu)(N1，N2，N3和N4)尋找每輛車每個(gè)行程的最佳客戶配置.鄰域算符N1包括4種插入位移.從位置i移動(dòng)1個(gè)客戶插入到位置j: ①在同1行程；②在相同車輛的另1個(gè)行程；③在另1輛車的另1個(gè)行程；④第4次移動(dòng)，從位置i移除1個(gè)客戶，并將它插入到相同車輛或另1個(gè)車輛新創(chuàng)建的行程中.第2個(gè)鄰域結(jié)構(gòu)N2從車輛i中移除1個(gè)行程k并把它插入車輛j.第3和第4鄰域結(jié)構(gòu)(N3，N4)交換移動(dòng)過(guò)程.鄰域結(jié)構(gòu)N3采用3次移動(dòng)交換，分別是：①2個(gè)客戶在同1個(gè)行程內(nèi)的位置交換；②相同車輛的2個(gè)不同行程的客戶交換；③來(lái)自2個(gè)不同車輛的2個(gè)行程內(nèi)的2個(gè)客戶交換.第4鄰域N4互換2個(gè)不同車輛的2個(gè)行程.領(lǐng)域結(jié)構(gòu)N1和N3用于最小化多個(gè)行程和超時(shí)時(shí)間的總長(zhǎng)度.而鄰域結(jié)構(gòu)N2和N4用于最小化超時(shí)時(shí)間.提出的可變鄰域下降算法的步驟見算法1.

算法1 變鄰域下降算法(VND)

Input：鄰域集合Nh，h=1,2，…,hmax=4

Initialization：找一個(gè)初始解s；

Repeat

h←1;

Whileh≤hmaxdo

s′←s的最佳鄰域， s′∈Nh(s)

Iff(s′)

s←s′;

h←1;

else

h←h+1

endif

endwhile

until不能獲得任何改進(jìn)為止

returns;

1.6 抖動(dòng)

給定1個(gè)鄰域結(jié)構(gòu)N，Nm表示在鄰域N中的第m個(gè)連續(xù)的移動(dòng).在抖動(dòng)步驟中，將m次移動(dòng)應(yīng)用到鄰域(N1,N3和N4).對(duì)于每1個(gè)從1到m的i 的取值，我們將選擇1個(gè)基于概率Pk分布的鄰域結(jié)構(gòu)Nk(k∈{1,3,4})，進(jìn)行隨機(jī)的移動(dòng).

1.7 變鄰域搜索

該變鄰域搜索算法的主要步驟是：初始化，抖動(dòng)，用變鄰域下降(variableneighborhooddescent，VND)算法進(jìn)行局部搜索和評(píng)估，這些步驟見算法2.

算法2 變鄰域下降算法(VND)

Input: 鄰域集合Nh，h=1,2，…,hmax，

Initialization: 找一個(gè)初始解s;

Repeat

h←1;

Whileh≤hmaxdo

s′←對(duì)s進(jìn)行抖動(dòng)，

s″←VND(s′)

Iff(s″)

s←s″;

h←1;

else

h←h+1

endif

endwhile

until符合終止條件A

returns;

首先從初始解決方案s開始，接下來(lái)，通過(guò)對(duì)方案s執(zhí)行抖動(dòng)步驟設(shè)計(jì)1個(gè)解決方案s′，該解決方案將作為VND算法尋找1個(gè)局部最優(yōu)s″的基礎(chǔ).在評(píng)價(jià)步驟中，如果f(s″)

2 計(jì)算結(jié)果

該改進(jìn)VNS算法采用來(lái)自Christofides改編的VRP數(shù)據(jù)集進(jìn)行測(cè)試.相關(guān)的算法采用C++語(yǔ)言編寫，并在戴爾筆記本電腦T2130@1.86GHz，1GRAM上運(yùn)行.采用了由文獻(xiàn)[5-9]等發(fā)現(xiàn)的標(biāo)準(zhǔn)進(jìn)行比較研究，采用發(fā)明人的姓名縮寫分別簡(jiǎn)稱為TG，BM，PS1，OV和PS2，并結(jié)合最長(zhǎng)行駛比(LTR)對(duì)結(jié)果進(jìn)行比較.在程序運(yùn)行的基礎(chǔ)上，設(shè)定以下參數(shù)用于生成計(jì)算結(jié)果，α∈(0.001,0.999)，ε1=0.001，β∈[1，100]，ε2=0.01.在抖動(dòng)過(guò)程中，在鄰域(N1，N3和N4)執(zhí)行hmax=3的移動(dòng)，并分別選擇概率為0.6，0.4和0.2.

通過(guò)表1看到，VNS算法能夠在104個(gè)樣例中的99個(gè)樣例中找出可行的解決方案，包括任意1個(gè)早期工作都無(wú)法解決的實(shí)例.對(duì)于算法PS1，TG，BM和PS2，幾乎所有的算法在解決帶時(shí)間T1的標(biāo)準(zhǔn)樣例時(shí)都遇到了一些困難，解決方案的成功率低于73%.而算法VNS和OV的成功率明顯優(yōu)于其他算法，分別為90.38%和88.46%.

表1 通過(guò)改進(jìn)VNS算法和其他標(biāo)準(zhǔn)找到的可行解的數(shù)量

在表2展示了提出的算法，以及上面提到的其他文獻(xiàn)中都不能找到可行解的標(biāo)準(zhǔn)樣例的數(shù)量. 表2利用LTR比率說(shuō)明了比較結(jié)果，其中在每個(gè)標(biāo)準(zhǔn)樣例中該VNS算法都無(wú)法找到可行解.從這些結(jié)果我們注意到從5個(gè)未解決的標(biāo)準(zhǔn)樣例中該改進(jìn)VNS算法提供了4個(gè)樣例的最佳解決方案，其次是OV算法也提供了和VNS算法相同的結(jié)果，CMT1實(shí)例稍差些.BM算法提供的F71實(shí)例也獲得了最佳結(jié)果.

表2 用于不可行解決方案的最長(zhǎng)行駛比(LTR)的比較

表3給出了針對(duì)每個(gè)實(shí)例的5次比較的平均CPU時(shí)間.表4為當(dāng)NV=7和T=154時(shí)CMT4新的可行解.結(jié)果表明，該VNS算法在解決這些標(biāo)準(zhǔn)實(shí)例時(shí)相對(duì)較快.

表3 平均CPU時(shí)間 s

表4 當(dāng)NV=7和T=154時(shí)CMT4新的可行解

最后，基于以上提供的不同結(jié)果，考慮到能夠找到可行解的標(biāo)準(zhǔn)實(shí)例的數(shù)量，求解的質(zhì)量以及尋找分配的CPU時(shí)間，該算法相比其他算法是很有競(jìng)爭(zhēng)力的，它可以歸類為解決VRPMT問(wèn)題的最佳算法.

3 結(jié) 束 語(yǔ)

提出1種改進(jìn)變鄰域搜索算法(VNS)來(lái)解決帶多行程的車輛路徑問(wèn)題.采用4個(gè)不同的鄰域結(jié)構(gòu)，其中2個(gè)用于最小化行程總長(zhǎng)度和超時(shí)，另外2個(gè)用于最小化超時(shí).在抖動(dòng)步驟中，在概率分布的基礎(chǔ)上采用了3種類型的鄰域.比較研究表明，該算法與其他文獻(xiàn)中的結(jié)果相比提供了較高質(zhì)量的求解結(jié)果，說(shuō)明本文提出的算法優(yōu)越于其他研究方法.在未來(lái)的工作中，該算法可以擴(kuò)展到求解混合車輛的車隊(duì)問(wèn)題或帶多車廂的車輛路徑問(wèn)題.

[1]宋強(qiáng),劉凌霞.多行程車輛路徑問(wèn)題和配送中心定位問(wèn)題的研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2016,46(7):103-113.

[2]張媛媛,曾曉燕.多行程帶時(shí)間窗的車輛調(diào)度問(wèn)題研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2015,45(7):1-7.

[3]許爭(zhēng)爭(zhēng),唐加福.基于協(xié)作的三階段啟發(fā)式算法求解多行程車輛行程問(wèn)題[J].南開大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,48(5):51-59.

[4]FLEISCHMANN B. The vehicle routing problem with multiple use of vehicles[J].Working Paper, Fachbereich Wirschaftswissenschaften,1990(1):55-58.

[5]TAILLARD E, LAPORTEV G,GENDREAU M. Vehicle routing problem with multiple use of vehicles[J]. Journal of the Operational Research Society,1996,47(8):1065-1070.

[6]BRANDAO J, MERCER A. The multi-trip vehicle routing problem[J].Journal of the Operational Research Society,1998,49(8):799-805.

[7]PETCH R J, SALHI S. A multi-phase constructive heuristic for the vehicle routing problems with multiple trips[J]. Discrete Applied Mathematics,2003,133(1):69-92.

[8]OLIVERA A, VIERA O. Adaptive memory programming for the vehicle routing problem with multiple trips[J]. Computers & Operations Research,2007,34(1):28-47.

[9]SALHI S, PETCH R J.A GA based heuristic for the vehicle routing problem with multiple trips[J]. Journal of Mathematical Modeling and Algorithms,2007,6(4):591-613.

[10]JARBOUI B, DERBEL H S, HANAFI, et al. Variable neighborhood search for location routing[J]. Computers & Operations Research,2013,40(1):47-57.

[11]張曉楠,范厚明,李劍鋒.同時(shí)配集貨定位—路線問(wèn)題的變鄰域分散搜索算法[J].計(jì)算機(jī)集成制造系統(tǒng),2015,21(9)：2535-2548.

[12]潘全科,王文宏,朱劍英.基于粒子群優(yōu)化和變鄰域搜索的混合調(diào)度算法[J].計(jì)算機(jī)集成制造系統(tǒng),2007,13(2):323-328.

[13]戈軍,周蓮英.面向動(dòng)態(tài)車輛路徑的改進(jìn)變鄰域搜索算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(23):71-74.

Application of Improved Variable Neighborhood Search Algorithm for VRPMT

SONG Qiang1)DU Nuannan2)

(DepartmentofInformationEngineering,GuangdongPolytechnicCollege,Zhaoqing526100,China)1)(SchoolofComputerandSoftwareEngineering,PingdingshanIndustrialCollegeofTechnology,Pingdingshan467001,China)2)

The vehicle routing problem with multiple paths is a variant of the standard VRP, where each vehicle can be used more than once during the working period. For this NP-Hard problem, this paper proposes an improved variable neighborhood search algorithm in which four neighborhood structure are designed to find the planning of paths. The algorithm is tested on a set of benchmark problems and the obtained solutions are compared with five previously proposed algorithms. Encouraging results are obtained.

vehicle routing; multipath; variable neighborhood search; shaking

2016-10-26

*河南省科技攻關(guān)基金項(xiàng)目資助(142102210231)

TP301.6

10.3963/j.issn.2095-3844.2017.01.006

宋強(qiáng)(1971—)：男，副教授，博士生，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)控制技術(shù)與算法優(yōu)化