饒衛(wèi)振，金 淳，劉 鋒，楊 磊

(1.山東科技大學(xué)經(jīng)濟(jì)管理學(xué)院，山東青島266590；2.大連理工大學(xué)系統(tǒng)工程研究所，遼寧，大連116024；3.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工學(xué)院，遼寧，大連116025)

一類動(dòng)態(tài)車輛路徑問(wèn)題模型和兩階段算法

饒衛(wèi)振*1，金 淳2，劉 鋒3，楊 磊1

(1.山東科技大學(xué)經(jīng)濟(jì)管理學(xué)院，山東青島266590；2.大連理工大學(xué)系統(tǒng)工程研究所，遼寧，大連116024；3.東北財(cái)經(jīng)大學(xué)管理科學(xué)與工學(xué)院，遼寧，大連116025)

針對(duì)一類動(dòng)態(tài)車輛路徑問(wèn)題，分析4種主要類型動(dòng)態(tài)信息對(duì)傳統(tǒng)車輛路徑問(wèn)題的本質(zhì)影響，將動(dòng)態(tài)車輛路徑問(wèn)題(Dynamic Vehicle Routing Problem,DVRP)轉(zhuǎn)化為多個(gè)靜態(tài)的多車型開(kāi)放式車輛路徑問(wèn)題(The Fleet Size and Mixed Open Vehicle Routing Problem,FSMOVRP)，并進(jìn)一步轉(zhuǎn)化為多個(gè)帶能力約束車輛路徑問(wèn)題(Capacitated Vehicle Routing Problem,CVRP)，基于CVRP模型建立了DVRP模型；然后，在分析DVRP問(wèn)題特點(diǎn)基礎(chǔ)上，提出兩階段算法，第一階段基于利用K-d trees對(duì)配送區(qū)域進(jìn)行分割的策略，提出了復(fù)雜度僅為O(nlogn)的快速構(gòu)建型算法，第二階段通過(guò)分析算法搜索解空間結(jié)構(gòu)原理，設(shè)計(jì)混合局部搜索算法；最后，基于現(xiàn)有12個(gè)大規(guī)模CVRP標(biāo)準(zhǔn)算例，設(shè)計(jì)并求解36個(gè)DVRP算例.求解結(jié)果表明了模型和兩階段算法的有效性.

物流工程；兩階段算法；動(dòng)態(tài)車輛路徑問(wèn)題；K-d樹(shù)分割策略；算法搜索解空間

1 引 言

車輛路徑問(wèn)題(Vehicle Routing Problem,VRP)自1959年Dantzig等[1]提出以來(lái)一直受到人們的廣泛關(guān)注，其研究意義毋庸置疑.隨著移動(dòng)通訊(Global System of Mobile communication,GSM)、電子商務(wù)(Electronic Commerce,EC)、全球定位系統(tǒng)(Global Positioning System,GPS)和智能交通系統(tǒng)(Intelligence Transport System,ITS)等技術(shù)的發(fā)展，物流配送企業(yè)能夠方便地獲取顧客狀態(tài)、交通路況和任務(wù)車輛狀態(tài)等實(shí)時(shí)信息.因此，基于傳統(tǒng)VRP問(wèn)題考慮配送中實(shí)時(shí)信息的動(dòng)態(tài)車輛路徑問(wèn)題(Dynamic Vehicle Routing Problem,DVRP)成為熱點(diǎn)研究問(wèn)題.

由于DVRP問(wèn)題的理論和實(shí)踐意義，自Psaraftis[2,3]在1988年提出DVRP問(wèn)題以來(lái)，很多學(xué)者在該領(lǐng)域做了廣泛研究[4]，如Larsen研究了DVRP問(wèn)題的動(dòng)態(tài)程度特征指標(biāo)的計(jì)算方法[5]；Brotcorne等研究了急救車的動(dòng)態(tài)調(diào)度問(wèn)題，其主要考慮新客戶的在線出現(xiàn)[6]；隨后研究考慮實(shí)時(shí)交通 信 息 的 DVRP學(xué) 者 還 有 Taniguchi[7]和Fleischmann[8].Melachrinoudis考慮了醫(yī)療服務(wù)的特殊環(huán)境對(duì)DVRP問(wèn)題的影響，并構(gòu)建了相應(yīng)模型[9].在最近2年里，Khouadjia[10]和Ferrucci[11]分別研究了具有動(dòng)態(tài)客戶的DVRP問(wèn)題，并提出了相應(yīng)的求解策略；Albareda-Sambola通過(guò)研究驗(yàn)證了將DVRP按時(shí)段分割處理的可行性[12]；Ghannadpour研究了多目標(biāo)DVRP問(wèn)題[13].針對(duì)DVRP問(wèn)題，部分國(guó)內(nèi)學(xué)者也進(jìn)行了較為廣泛的研究，如郭耀煌等在綜述當(dāng)前DVRP研究現(xiàn)狀的基礎(chǔ)上[14]，分別研究了DVRP問(wèn)題的求解策略[15]和模型[16]；劉霞[17]和Hong[18]研究了帶時(shí)間窗的DVRP問(wèn)題；陳久梅等研究了裝卸一體化的DVRP問(wèn)題，并提出了分區(qū)求解策略[19].葛顯龍研究了聯(lián)合配送的開(kāi)放式DVRP問(wèn)題[20].

綜上所述，當(dāng)前已有部分學(xué)者對(duì)DVRP研究做了較為深入的研究，但當(dāng)前針對(duì)DVRP的研究鮮見(jiàn)分析與VRP的本質(zhì)區(qū)別，并且現(xiàn)有求解算法設(shè)計(jì)強(qiáng)調(diào)求解質(zhì)量，而對(duì)算法合并動(dòng)態(tài)事件生成新方案的速度方面考慮較少[4].本文通過(guò)分析發(fā)現(xiàn)，DVRP問(wèn)題能夠轉(zhuǎn)化為多車型開(kāi)放式車輛路徑問(wèn)題(The Fleet Size and Mixed Open Vehicle Routing Problem,FSMOVRP)，并進(jìn)一步轉(zhuǎn)化為經(jīng)典的能力約束VRP問(wèn)題(Capacitated VRP,CVRP).首先，基于經(jīng)典的CVRP模型，建立了DVRP模型.然后，基于模型提出一個(gè)有效的兩階段算法，并通過(guò)設(shè)計(jì)和求解標(biāo)準(zhǔn)DVRP算例驗(yàn)證了本文模型與算法的有效性.

2 問(wèn)題建模

2.1 問(wèn)題分析

DVRP與傳統(tǒng)的靜態(tài)CVRP問(wèn)題的主要區(qū)別是，在配送過(guò)程中會(huì)出現(xiàn)新的信息，本文稱為動(dòng)態(tài)事件.動(dòng)態(tài)事件主要存在4種類型，包括：

(1)新顧客出現(xiàn)；

(2)老顧客改變需求；

(3)交通堵塞或中斷；

(4)配送車輛拋錨.

本文研究的DVRP問(wèn)題除了經(jīng)典CVRP中的假設(shè)外還包括：

(1)如果是執(zhí)行配送任務(wù)，設(shè)配送的貨物為同質(zhì)物品，每輛車均滿載后開(kāi)始執(zhí)行任務(wù)；如果是回收任務(wù)，每輛車均空車開(kāi)始執(zhí)行任務(wù).

(2)僅考慮局部交通中斷情況(即局部發(fā)生嚴(yán)重的交通堵塞或道路管制問(wèn)題)，不考慮大面積的交通癱瘓導(dǎo)致無(wú)可行方案的情況.

(3)車輛在出現(xiàn)拋錨后，在配送周期內(nèi)不能夠完全修理好.

當(dāng)任何動(dòng)態(tài)事件發(fā)生后，基于原有信息所得到的方案在當(dāng)前情況下可能質(zhì)量非常低劣甚至不可行，所以需要結(jié)合當(dāng)前信息，對(duì)方案重新優(yōu)化以及時(shí)修正方案.求解該問(wèn)題關(guān)鍵在于，此時(shí)已有部分車輛完成部分配送服務(wù)，所在位置已不在配送中心.對(duì)于這樣的車輛重新優(yōu)化配送路線，等價(jià)于起點(diǎn)(終點(diǎn))不在配送中心的開(kāi)放式VRP(Open VRP,OVRP)問(wèn)題，并且由于這些車輛已完成部分配送服務(wù)，此時(shí)服務(wù)能力為車輛所剩貨物量，因此等價(jià)于多車型OVRP問(wèn)題(The Fleet Size and Mixed OVRP,FSMOVRP).FSMOVRP問(wèn)題可以進(jìn)一步轉(zhuǎn)化為CVRP問(wèn)題，將不在配送中心的車輛起點(diǎn)或終點(diǎn)虛擬為一個(gè)顧客，且需求量為當(dāng)前最大車載量Q與當(dāng)前車型載量之差，并將該虛擬顧客設(shè)定為必須第一個(gè)(最后一個(gè))接受服務(wù)的顧客.如圖1(a)、圖1(b)所示為出現(xiàn)新顧客后的一個(gè)DVRP問(wèn)題，轉(zhuǎn)化為一個(gè)CVRP問(wèn)題示意圖.

圖1 DVRP轉(zhuǎn)化為CVRP示意圖Fig.1 A demonstration of transformation from DVRP to CVRP

同理，對(duì)于出現(xiàn)尚未服務(wù)的老顧客改變需求和車輛出現(xiàn)拋錨時(shí)，通過(guò)更新當(dāng)前尚未服務(wù)的顧客可以做類似處理.而當(dāng)出現(xiàn)交通中斷時(shí)，相當(dāng)于求解一個(gè)更新顧客間行駛成本后的CVRP問(wèn)題，在此不再贅述.因此DVRP可以轉(zhuǎn)化分解為多個(gè)CVRP問(wèn)題.

2.2 數(shù)學(xué)模型

符號(hào)表示：

t0——配送開(kāi)始時(shí)刻；

tend——配送結(jié)束時(shí)刻；

T——配送周期等于tend-t0；

s——整個(gè)配送周期T中動(dòng)態(tài)事件(信息)出現(xiàn)的次數(shù)；

Eventi—— 第i次動(dòng)態(tài)事件，1次動(dòng)態(tài)事件指的是出現(xiàn)1次新信息，0≤i≤s；

EventTimei——第 i次動(dòng)態(tài)事件發(fā)生的時(shí)刻，0≤i≤s，t0≤EventTimei＜tend，且 令EventTime0=t0；

n——所有出現(xiàn)的顧客數(shù)量；

ki——在時(shí)刻點(diǎn)EventTimei正要到達(dá)時(shí)在執(zhí)行配送任務(wù)的車輛數(shù)量，ki≥0；

mi——在時(shí)刻點(diǎn)EventTimei正要到達(dá)時(shí)方案中車輛數(shù)量，顯然mi≥ki；

Q——表示在配送中心車輛的最大服務(wù)能力；

L——表示單輛車的最大行程約束；

Qik——在時(shí)刻點(diǎn)EventTimei第k輛任務(wù)車輛已耗費(fèi)的服務(wù)能力，0≤Qik≤Q，0≤i≤s，0≤k≤ki；

Lik——在時(shí)刻點(diǎn)EventTimei第k輛任務(wù)車輛已行駛的距離，0≤Lik≤L，0≤i≤s，0≤k≤ki；

v——所有車輛的行駛速度，為確保每輛車均能夠在周期內(nèi)完成任務(wù)設(shè)L/v≤0.5T；

Di——表示在時(shí)刻點(diǎn)EventTimei下的距離矩陣，其內(nèi)部的元素為；

qi——顧客i的需求量，max(qi)≤Q,1≤i≤n.

δ——?jiǎng)討B(tài)程度，等于在配送過(guò)程中出現(xiàn)新顧客的數(shù)量占總顧客數(shù)量的比率[5].

由以上分析得到，DVRP可以分解為(s+1)個(gè)CVRP問(wèn)題，可得DVRP在時(shí)刻點(diǎn)EventTimei下的數(shù)學(xué)規(guī)劃模型為

目標(biāo)函數(shù)：

約束條件：

式(1)為總行程最小目標(biāo)；式(2)和式(3)為車載量與行駛距離約束；式(4)和式(5)為計(jì)劃從配送中心派送車輛的載量與行駛距離約束；式(6)和式(7)表示每個(gè)客戶恰好僅被1輛車服務(wù)；式(8)約束了所有車輛的起終點(diǎn)都在配送中心；式(9)表示每輛車行駛的路徑軌跡恰好為一個(gè)簡(jiǎn)單圈；式(10)為變量含義和取值；式(11)約束每輛正在執(zhí)行任務(wù)的車輛必須首先服務(wù)當(dāng)前所在位置對(duì)應(yīng)的虛擬顧客，以使配送的路徑為簡(jiǎn)單圈從而由FSMOVRP轉(zhuǎn)化為CVRP問(wèn)題.式(12)表示動(dòng)態(tài)事件發(fā)生的時(shí)刻點(diǎn)在配送周期之內(nèi)，且呈時(shí)間序列狀態(tài).

3 兩階段算法

根據(jù)上述建模思想，求解該模型的最大挑戰(zhàn)在于對(duì)算法速度有非常高的要求.因?yàn)椋?dāng)動(dòng)態(tài)事件發(fā)生的比較頻繁時(shí)，就要求算法能夠在短時(shí)間內(nèi)求解問(wèn)題.本文設(shè)計(jì)了一個(gè)兩階段算法：改進(jìn)貪婪算法和混合大鄰域算法.采用該兩階段算法求解DVRP的流程圖，如圖2所示.

圖2 兩階段算法求解DVRP流程圖Fig.2 Flow chart of two-stage algorithms for solving dynamic vehicle routing problem

如圖2所示，本文求解DVRP問(wèn)題基于“先完成后完善”的思想.首先采用改進(jìn)貪婪算法結(jié)合新的信息，快速生成一個(gè)質(zhì)量滿意的方案；然后充分利用下一個(gè)動(dòng)態(tài)事件出現(xiàn)之前的這段時(shí)間，采用混合大鄰域算法繼續(xù)改進(jìn)當(dāng)前車輛的計(jì)劃行駛路線；最后，當(dāng)出現(xiàn)下一個(gè)動(dòng)態(tài)事件后再重復(fù)這一過(guò)程，直到配送過(guò)程結(jié)束.

3.1 改進(jìn)貪婪算法

經(jīng)典貪婪算法(Greedy,GR)求解過(guò)程中初期效果非常好，但構(gòu)造后期會(huì)導(dǎo)致質(zhì)量迅速下降.另外，GR要求對(duì)任意2個(gè)顧客形成的距離從小到大排序，那么相當(dāng)于對(duì)n(n-1)/2條邊排序，根據(jù)排序算法GR算法的復(fù)雜度至少為O(n2logn)，該復(fù)雜度會(huì)隨著n的增加而迅速增加.本文提出2個(gè)分別提高GR求解質(zhì)量和求解速度的策略，得到改進(jìn)GR(Improved GR,IMGR).

IMGR提高質(zhì)量策略的思想是，讓離配送中心較遠(yuǎn)的邊更短，而離配送中心較近的邊更長(zhǎng)，從而GR將會(huì)優(yōu)先連接離配送中心較遠(yuǎn)的點(diǎn)，使貪婪算法構(gòu)造后期質(zhì)量改進(jìn)從而提高整體算法的質(zhì)量；提高速度的策略是，據(jù)GR運(yùn)算原理，其主要計(jì)算量為求最鄰近點(diǎn)計(jì)算，并且實(shí)際物流配送中，兩點(diǎn)間的路網(wǎng)距離和直線距離高度相關(guān).在此，我們采用K-d trees(K-dimensional binary search trees)法近似求解區(qū)域中的最鄰近點(diǎn)，本文將配送區(qū)域作為2維平面，因此K=2，其詳細(xì)執(zhí)行原理參照Bentley的文獻(xiàn)[21].該算法的性能在求解大規(guī)模CVRP問(wèn)題中已得到驗(yàn)證，結(jié)合K-d trees的IMGR的求解復(fù)雜度僅為O(nlogn)，并且求解世界上顧客數(shù)量達(dá)到20 000的規(guī)模最大標(biāo)準(zhǔn)算例的求解質(zhì)量與理論最優(yōu)解的偏差僅為5.18%[22].

3.2 混合大鄰域算法

通過(guò)文獻(xiàn)[23]研究旅行商問(wèn)題(Traveling Salesman Problem,TSP)的求解算法發(fā)現(xiàn)，當(dāng)算法搜索解空間結(jié)構(gòu)(問(wèn)題解空間中的可行解為節(jié)點(diǎn)，互為鄰域的可行解之間存在邊)類似于小世界網(wǎng)絡(luò)時(shí)，其對(duì)應(yīng)的算法求解質(zhì)量更優(yōu)，且只具有某一特定算法規(guī)則的算法，其解空間結(jié)構(gòu)更類似于規(guī)則網(wǎng)絡(luò).

由于TSP是CVRP的子問(wèn)題，因此其上述結(jié)論對(duì)CVRP具有一定借鑒意義.根據(jù)復(fù)雜網(wǎng)絡(luò)理論可知，多個(gè)規(guī)則網(wǎng)絡(luò)混合后得到的網(wǎng)絡(luò)會(huì)更類似于小世界網(wǎng)絡(luò)[24].因此，多個(gè)特定算法規(guī)則進(jìn)行合理混合，就可能得到有效的算法.基于該思想，本文采用改進(jìn)CVRP問(wèn)題解的4種車輛路徑間基本規(guī)則(Swap、Exchange、Cross-Exchange和Inter-relocate)和4種車輛路徑中規(guī)則(2-opt、Lin-Kernighan、Intrarelocate和Or-opt)，設(shè)計(jì)了一個(gè)混合大鄰域算法(Hybrid Large Neighborhood Algorithm,HLNA)，其求解規(guī)則偽代碼如圖3所示.

圖3 混合大鄰域算法偽代碼Fig.3 Pseudo codes of HLNA

4 算例設(shè)計(jì)與求解

4.1 算例設(shè)計(jì)

為了測(cè)試本文提出模型和算法的有效性，本文以當(dāng)前世界上最大的12個(gè)CVRP算例[25]為數(shù)據(jù)基礎(chǔ)，按照動(dòng)態(tài)程度δ分別為0.25、0.50和0.75構(gòu)造36個(gè)大規(guī)模動(dòng)態(tài)車輛路徑問(wèn)題標(biāo)準(zhǔn)算例，算例中相關(guān)參數(shù)設(shè)定如表1所示.

表1 36個(gè)DVRP算例中相關(guān)參數(shù)值Table 1 The parameters values of 36 DVRP instances

需要注意的是本文設(shè)計(jì)的標(biāo)準(zhǔn)算例中只考慮了新顧客出現(xiàn)，其主要原因是

(1)后三種動(dòng)態(tài)事件與當(dāng)前執(zhí)行方案密切相關(guān)；

(2)后三種動(dòng)態(tài)事件發(fā)生后，根據(jù)本文模型也均可以轉(zhuǎn)化為CVRP問(wèn)題，故在此設(shè)計(jì)的算例不影響測(cè)試本文算法的性能.

表1中設(shè)新顧客在整個(gè)配送周期中按標(biāo)號(hào)升序方式均勻地出現(xiàn).

4.2 算例求解

為了對(duì)比分析單獨(dú)使用IMGR(參數(shù)α=0.70)和IMGR+HLNA(參數(shù)p=0.05)聯(lián)合使用的效果，本文分別用該兩種方式求解在4.1節(jié)設(shè)計(jì)的36大規(guī)模動(dòng)態(tài)車輛路徑問(wèn)題的標(biāo)準(zhǔn)算例，求解環(huán)境：Studio Visual C++6.0；CPU為Inter(R)core(TM)Q9400，內(nèi)存為4.0G，主頻為2.66GHz，其求解質(zhì)量如表2所示，求解總耗時(shí)如表3所示，需要注意的是，求解質(zhì)量為求解路徑長(zhǎng)度與對(duì)應(yīng)靜態(tài)算例已知最優(yōu)解的偏差.

表2 IMGR與IMGR+HLNA求解36個(gè)算例質(zhì)量Table 2 The solution quality comparison of IMGR and IMGR+HLNA

表3 IMGR和IMGR+HLNA求解36個(gè)算例總耗時(shí)Table 3 The total running time of IMGR and IMGR+HLNA

由求解結(jié)果可知，對(duì)于規(guī)模相同的算例，動(dòng)態(tài)程度越大IMGR與IMGR+HLNA的求解質(zhì)量會(huì)越差.并且相比較而言，IMGR+HLNA的求解質(zhì)量要優(yōu)于IMGR，通過(guò)對(duì)比表2所示的不同算例相鄰動(dòng)態(tài)事件間隔可以發(fā)現(xiàn)，動(dòng)態(tài)事件發(fā)生的越頻繁，IMGR+HLNA的求解質(zhì)量?jī)?yōu)勢(shì)越不明顯，這是因?yàn)橛糜贖LNA進(jìn)一步改進(jìn)的時(shí)間非常緊迫.

由上述求解質(zhì)量結(jié)果可以得到以下啟示：

(1)HLNA是元啟發(fā)式算法，需要更充足的運(yùn)行時(shí)間才能保證改進(jìn)IMGR的求解結(jié)果，當(dāng)運(yùn)行時(shí)間非常有限時(shí)(不足60 s)，IMGR+HLNA與IMGR幾乎有類似的求解結(jié)果.

(2)IMGR+HLNA在時(shí)間緊迫的情況下對(duì)于有些算例的求解質(zhì)量甚至略低于IMGR(如DVRPLi14400動(dòng)態(tài)程度δ=0.75時(shí))，這說(shuō)明在動(dòng)態(tài)車輛路徑算例中，當(dāng)前更優(yōu)的求解結(jié)果并不一定會(huì)導(dǎo)致最終形成的解質(zhì)量更高.

由表3所示的IMGR和IMGR+HLNA的求解總時(shí)間可知，IMGR遠(yuǎn)遠(yuǎn)少于IMGR+HLNA的求解時(shí)間.這是因?yàn)镮MGR+HLNA為了在動(dòng)態(tài)事件未出現(xiàn)時(shí)，充分利用HLNA不斷優(yōu)化當(dāng)前未執(zhí)行的計(jì)劃配送路線，使HLNA在整個(gè)配送周期T=10 h=36 000 s中一直處于運(yùn)行狀態(tài).

總體來(lái)說(shuō)，IMGR能夠快速地應(yīng)對(duì)動(dòng)態(tài)事件，生成新的方案，且當(dāng)動(dòng)態(tài)事件出現(xiàn)非常頻繁時(shí)IMGR與IMGR+HLNA有類似求解質(zhì)量，但當(dāng)動(dòng)態(tài)事件出現(xiàn)時(shí)間間隔超過(guò)1 m in時(shí)，IMGR+HLNA求解質(zhì)量明顯優(yōu)于IMGR.

5 研究結(jié)論

本文分析了DVRP問(wèn)題中4種主要不同類型動(dòng)態(tài)事件對(duì)優(yōu)化問(wèn)題本質(zhì)的影響，通過(guò)分析得到DVRP問(wèn)題可以轉(zhuǎn)化為多個(gè)FSMOVRP問(wèn)題，并進(jìn)一步轉(zhuǎn)化為CVRP問(wèn)題，基于分析結(jié)論建立了DVRP模型.基于先完成后完善的思想，提出了一個(gè)由復(fù)雜度僅為O(n log n)的IMGR和HLNA構(gòu)成的兩階段算法.為了驗(yàn)證本文提出的模型和算法的有效性，基于12個(gè)當(dāng)前世界上最大的CVRP問(wèn)題的標(biāo)準(zhǔn)算例，設(shè)計(jì)了36個(gè)DVRP算例，通過(guò)求解發(fā)現(xiàn)，本文提出的兩階段算法能夠在合理時(shí)間內(nèi)，求解動(dòng)態(tài)程度較高的大規(guī)模的DVRP問(wèn)題.

[1]Dantzig G B,Ramser J H.The truck dispatching problem[J].Management Science,1959,6(1):80-91.

[2]Psaraftis H N.Dynamic vehicle routing problems[M]. North-Holland:Elsevier,1988.

[3]Psaraftis H N.Dynamic vehicle routing:Status and prospects[J].Annal of Operations Research,1995,61 (1):143-164.

[4]Pillac V,Gendreau M,Guéret C,et al.A review of dynamic vehicle routing problems[J].European Journal of Operational Research,2013,225(1):1-11.

[5]Larsen A.The dynamic vehicle routing problem[D]. Technical University of Denmark,2001.

[6]Brotcorne L,Laporte G,Semet F.Ambulance location and relocation models[J].European Journal of Operational Research,2003,147(3):451-463.

[7]Taniguchi E,Shimamoto H.Intelligent transportation system based dynamic vehicle routing and scheduling with variable travel times[J].Transportation Research Part C:Emerging Technologies,2004,12(3-4):235-250.

[8]Fleischmann B,Gnutzmann S,Sandvoss E.Dynamic vehicle routing based on online traffic information[J]. Transportation Science,2004,38(4):420-433.

[9]Melachrinoudis E,Ilhan A B,Min H.A dial-a-ride problem for client transportation in a health-care organization[J].Computers& Operations Research, 2007,34(3):742-759.

[10]Khouadjia M R,Sarasola B,Alba E,et al.A comparative study between dynamic adapted PSO and VNS for the vehicle routing problem with dynamic requests[J]. Applied Soft Computing,2012,12(4):1426-1439.

[11]Ferrucci F,Bock S,Gendreau M.A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods[J].European Journal of Operational Research,2013,225(1):130-141.

[12]Albareda-Sambola M,Fernández E,Laporte G.The dynamic multiperiod vehicle routing problem with probabilistic information[J].Computers&Operations Research,2014,48(2):31-39.

[13]Ghannadpour S F,Noori S,Tavakkoli-Moghaddam R, et al.A multi-objective dynamic vehicle routing problem with fuzzy time windows:Model,solution and application[J].Applied Soft Computing,2014,14 (1):504-527.

[14]謝秉磊,郭耀煌,郭強(qiáng).動(dòng)態(tài)車輛路徑問(wèn)題:現(xiàn)狀與展望[J].系統(tǒng)工程理論方法應(yīng)用,2002,11(2):116-120. [XIE B L,GUO Y H,GUO Q.Dynamic vehicle routing problems:status and prospect[J].Systems Engineering Theory Methodology Applications,2002,11(2):116-120.]

[15]郭耀煌,謝秉磊.一類隨機(jī)動(dòng)態(tài)車輛路徑問(wèn)題的策略分析[J].管理工程學(xué)報(bào),2003,17(4):114-115.[GUO Y H,XIE B L.Policy analysis on a stochastic dynamic vehicle routing problem[J].Journal of Industrial Engineering Engineering Management,2003,17(4): 114-115.]

[16]郭耀煌,鐘小鵬.動(dòng)態(tài)車輛路徑問(wèn)題排隊(duì)模型分析[J].管理科學(xué)學(xué)報(bào),2006,9(1):33-37.[GUO Y H,ZHONG X P.Analysis of the queuing model of dynamic vehicle routing problem[J].Journal of Management Sciences in China,2006,9(1):33-37.]

[17]劉霞,齊歡.帶時(shí)間窗的動(dòng)態(tài)車輛路徑問(wèn)題的局部搜索算法[J].交通運(yùn)輸工程學(xué)報(bào),2008,8(5):114-120. [LIU X,QI H.Local search algorithm of dynamic vehicle routing problem with time window[J].Journal of Traffic and Transportation Engineering,2008,8(5):114-120.]

[18]Hong L X.An improved LNS algorithm for real-time vehicle routing problem with time windows[J]. Computers&Operations Research,2012,39(2):151-163.

[19]陳久梅,張旭梅,肖劍,等.隨機(jī)動(dòng)態(tài)裝卸混合問(wèn)題的分區(qū)求解策略[J].管理科學(xué)學(xué)報(bào),2012,15(1):43-53. [CHEN J M,ZHANG X M,XIAO J，et al.Region partitioning policy for stochastic dynamic pick-up and delivery problem[J].Journal of Management Sciences in China,2012,15(1):43-53.]

[20]葛顯龍,王旭,鄧?yán)?基于聯(lián)合配送的開(kāi)放式動(dòng)態(tài)車輛路徑問(wèn)題及算法研究[J].管理工程學(xué)報(bào),2013,27 (03):60-68.[GE X L,WANG X,DENG L.Research on open and dynamic vehicle routing problems based on joint distribution[J].Journal of Industrial Engineering Management,2013,27(03):60-68.]

[21]Bentley J L.K-d trees for semidynamic point sets[C]// Proc.6th Ann.ACM Symp on Computational Geometry,1990:187-197.

[22]饒衛(wèi)振,金淳.求解大規(guī)模CVRP問(wèn)題的快速貪婪算法[J].管理工程學(xué)報(bào),2014,28(02):45-54.[RAO W Z, JIN C.An efficient greedy heuristic for solving largescale capacitated vehicle routing problem[J].Journal of Industrial Engineering Management,2014,28(02):45-54.]

[23]Rao W Z,Jin C.A method for analyzing solution space of traveling salesman problem based on complex network[J].International Journal of Innovative Computing Information and Control,2013,9(9):3685-3700.

[24]Costa L D,Oliveira O N,Travieso G,et al.Analyzing and modeling real-world phenomena with complex networks:A survey of applications[J].Advances in Physics,2011,60(3):329-412.

[25]Li F Y,Golden B,Wasil E.Very large-scale vehicle routing:New test problems,algorithms,and results[J]. Computers&Operations Research,2005,32(5):1165-1179.

Model and Two-stage Algorithm on Dynamic Vehicle Routing Problem

RAO Wei-zhen1，JIN Chun2，LIU Feng3，YANG Lei1
(1.College of Economics and Management,Shandong University of Science and Technology,Qingdao 266590,Shandong, China;2.Institute of Systems and Engineering,Dalian University of Technology,Dalian 116024,Liaoning,China;3.College of Management Science and Engineering,Dongbei University of Finance and Economics,Dalian 116025,Liaoning,China)

In order to effectively solve dynamic vehicle routing problem(DVRP),this paper analyzes the substantial effect of four main categories of dynamic information on classical vehicle routing problem,and transform DVRP into multiple static fleet size and mixed open vehicle routing problems(FSMOVRP).And FSMOVRP could be further converted to multiple capacitated vehicle routing problems(CVRP).The model based on CVRP is built up for DVRP.After that a two-stage algorithm is proposed to solve DVRP model according to the analysis of DVRP characteristics.In the first stage,a fast construction algorithm with merely O(nlogn)complexity is proposed on the basis of delivery region cutting strategy by K-d trees method.In the second stage,a hybrid local search algorithm is designed by analysis of structural principal of algorithm’s solution searching space.Finally for the purpose of algorithm verification,we design and solve 36 DVRP instances generated from 12 large scale CVRP benchmark instances.The results demonstrate the effectiveness of the model and two-stage solving algorithm.

logistics engineering;two-stage algorithm;DVRP;K-d trees;algorithm searching solution space

1009-6744（2015）01-0159-08

：U491

：A

2014-08-08

：2014-09-23錄用日期：2014-10-09

國(guó)家自然科學(xué)基金（71271041）；山東省優(yōu)秀中青年科學(xué)家科研獎(jiǎng)勵(lì)基金（BS2014SF001）；山東科技大學(xué)人才引進(jìn)基金（RCJJ2013020）；山東省軟科學(xué)研究計(jì)劃項(xiàng)目（2014RKB01506）.

饒衛(wèi)振（1981-），男，江西豐城人，講師. ＊

：raoweizhen@163.com