一類動態(tài)車輛路徑問題模型和兩階段算法

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

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

一類動態(tài)車輛路徑問題模型和兩階段算法

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

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

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

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

1 引 言

車輛路徑問題(Vehicle Routing Problem,VRP)自1959年Dantzig等[1]提出以來一直受到人們的廣泛關(guān)注，其研究意義毋庸置疑.隨著移動通訊(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)等實時信息.因此，基于傳統(tǒng)VRP問題考慮配送中實時信息的動態(tài)車輛路徑問題(Dynamic Vehicle Routing Problem,DVRP)成為熱點研究問題.

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

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

2 問題建模

2.1 問題分析

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

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

(2)老顧客改變需求；

(3)交通堵塞或中斷；

(4)配送車輛拋錨.

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

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

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

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

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

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

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

2.2 數(shù)學模型

符號表示：

t0——配送開始時刻；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

δ——動態(tài)程度，等于在配送過程中出現(xiàn)新顧客的數(shù)量占總顧客數(shù)量的比率[5].

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

目標函數(shù)：

約束條件：

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

3 兩階段算法

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

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

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

3.1 改進貪婪算法

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

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

3.2 混合大鄰域算法

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

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

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

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

4.1 算例設(shè)計

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

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

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

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

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

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

4.2 算例求解

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

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

表3 IMGR和IMGR+HLNA求解36個算例總耗時Table 3 The total running time of IMGR and IMGR+HLNA

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

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

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

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

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

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

5 研究結(jié)論

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

[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]謝秉磊,郭耀煌,郭強.動態(tài)車輛路徑問題:現(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]郭耀煌,謝秉磊.一類隨機動態(tài)車輛路徑問題的策略分析[J].管理工程學報,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]郭耀煌,鐘小鵬.動態(tài)車輛路徑問題排隊模型分析[J].管理科學學報,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]劉霞,齊歡.帶時間窗的動態(tài)車輛路徑問題的局部搜索算法[J].交通運輸工程學報,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]陳久梅,張旭梅,肖劍,等.隨機動態(tài)裝卸混合問題的分區(qū)求解策略[J].管理科學學報,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]葛顯龍,王旭,鄧蕾.基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究[J].管理工程學報,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問題的快速貪婪算法[J].管理工程學報,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

國家自然科學基金（71271041）；山東省優(yōu)秀中青年科學家科研獎勵基金（BS2014SF001）；山東科技大學人才引進基金（RCJJ2013020）；山東省軟科學研究計劃項目（2014RKB01506）.

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

：raoweizhen@163.com