基于混合修正策略的隨機時間車輛路徑優(yōu)化方法

馬 俊，張紀會，郭乙運

基于混合修正策略的隨機時間車輛路徑優(yōu)化方法

馬 俊1, 2，張紀會1, 2，郭乙運3

(1. 青島大學，復雜性科學研究所，青島 266071；2. 山東省工業(yè)控制技術重點實驗室，青島 266071；3. 青島港國際股份有限公司，青島 266071)

針對帶有隨機旅行時間、隨機服務時間及時間窗約束的車輛路徑問題，建立了帶修正策略的隨機規(guī)劃模型，并給出了兩階段求解方法。第一階段運用改進遺傳算法獲取先驗路徑，第二階段采用兩種混合修正策略(分別記為A、B)調整“失敗”的先驗路徑。混合修正策略A(B)通過隨機模擬實驗判斷對當前顧客的延遲服務(對下一顧客的服務)是否會對該路徑后續(xù)顧客造成大規(guī)模延遲服務，并采取相應的調整措施。基于Solomon算例進行了仿真實驗，對小規(guī)模算例將仿真結果同CPLEX求解結果作對比；對大規(guī)模算例將仿真結果同已知最優(yōu)解作對比。結果表明：所給算法可獲得小規(guī)模算例的精確解，大規(guī)模算例的近似最優(yōu)解。同時，對比不同策略下的仿真結果表明兩種混合修正策略具有優(yōu)越性，研究結果對隨機車輛路徑問題的求解具有一定的參考意義。

物流工程；車輛路徑；隨機旅行及服務時間；隨機規(guī)劃；混合修正策略；改進遺傳算法

0 引 言

車輛路徑問題(Vehicle Routing Problem，VRP)是Dantzig和Ramser[1]提出的一類經典組合優(yōu)化問題。自提出至今，已應用于眾多領域，如物流配送、垃圾回收[2]、上門維修及醫(yī)療服務等，并演化出許多不同問題，如帶容量或時間窗約束的VRP等，有關VRP的最新研究綜述參見文獻[3]。傳統(tǒng)VRP一般假設所涉及的參數(shù)信息是已知的，然而在現(xiàn)實世界中某些信息是無法提前獲知的，如車輛在某一路段的實際運行時間、車輛在某一顧客點的實際服務時間、顧客的實際需求等，為此衍生出許多不確定VRP問題。不確定性可進一步分為主觀不確定性和客觀不確定性，常用模糊變量或隨機變量表示。由于主觀不確定性可隨研究的深入而逐漸清晰，故客觀不確定性VRP的研究更為廣泛和深入[4-6]。從客觀不確定性角度出發(fā)，本文研究帶有隨機旅行時間、隨機服務時間及時間窗約束的車輛路徑問題(Vehicle Routing Problem with Stochastic Travel and Service Time and Time Windows，VRPSTSTW)。

不確定VRP的建模方法主要有三種：機會約束規(guī)劃(Chance-Constrained Programming, CCP)、帶修正策略的隨機規(guī)劃(Stochastic Programming with Recourse, SPR)及魯棒優(yōu)化(Robust Optimization, RO)。CCP將隨機VRP描述為求解一個或多個約束條件需滿足一定置信水平的最優(yōu)化問題，求解該問題的難點在于機會約束檢查，兩種常見的方法為離散化方法和隨機模擬方法。離散化方法將隨機變量(如旅行時間及服務時間)分布函數(shù)離散為有限個數(shù)值()-累計概率(())對，求解待檢查隨機變量(如到達時間)分布函數(shù)并檢查機會約束；隨機模擬方法通過大量模擬實驗獲得給定路徑上待求變量樣本均值等統(tǒng)計信息，以樣本均值近似估計期望值并檢查機會約束。基于離散化方法，Miranda和Conceicao[7]、Zhang等[8]求解了單目標VRPSTSTW, Miranda等[9]求解了多目標VRPSTSTW。基于隨機模擬方法，Li等[10]檢查了車輛到達時間及司機工作時長機會約束。CCP模型下的最優(yōu)路徑是在一定置信水平下求得的，實際運行中存在“失敗”的可能性。SPR運用修正策略對車輛實際運行中發(fā)生“失敗”的先驗路徑給予修正。這里“失敗”路徑是指車輛沿先驗路徑行駛過程中，由于隨機因素的存在，使得車輛無法按照顧客要求提供服務。隨機VRP修正策略多圍繞不確定顧客需求展開，常見的修正策略有返回車場補貨、預防性補貨等。返回車場補貨策略指的是如果車輛在某一顧客處的現(xiàn)有存貨不足以完全滿足當前顧客實際需求，車輛需先返回車場補貨，然后完成對該顧客的服務，參見文獻[11]。預防性補貨指的是車輛在完成某一顧客服務后，判斷現(xiàn)有存貨滿足下一顧客需求的概率大小，若該概率值小于某一設定閾值，車輛立即返回車場補貨，然后行駛至未服務顧客處，參見文獻[12]。此外，Salavati- Khoshghalb等[13]針對不確定需求VRP，提出了一種混合預防性補貨、風險評估及距離評估的修正策略。針對VRPSTSTW，常見的修正策略有兩種，分別稱之為TWVC(Time Windows Violation Cost, TWVC)及跳過策略。TWVC允許顧客接受車輛提供的延遲服務；跳過策略指的是，當車輛到達某一顧客的時間晚于該顧客要求的右時間窗時，為保證對下一顧客的準時服務，車輛跳過當前顧客。Li等[10]將VRPSTSTW分別建模為CCP和SPR，其修正策略是對違反時間窗及司機工作時長約束的車輛按照違反程度添加一定的線性懲罰成本。Andres等[14]提出了結合機會約束及修正策略的混合隨機規(guī)劃模型，其修正策略為跳過策略。與CCP和SPR不同的是，RO以不確定集的形式體現(xiàn)不確定性，目標是尋找不確定集中最糟糕情形下對應的最優(yōu)解。基于該思想，Shi等[15]在上門醫(yī)療服務路徑規(guī)劃中考慮不確定旅行及服務時間，運用Gurobi、模擬退火算法、禁忌搜索算法、變鄰域局部搜索算法分別求解該RO模型，并通過一系列實驗驗證了模型和算法的有效性。此外，該文進一步分析了實例中時間窗寬度、顧客分布位置等因素對結果的影響。針對帶有不確定服務時間道路網(wǎng)絡日常維護中的弧路由問題(Arc Routing Problem, ARP)，Chen等[16]將該問題建模為RO，并設計了分支定界算法，同時將RO與經典的CCP進行比較，驗證了運用RO所得路徑的優(yōu)越性。近年來，有關隨機VRP問題的研究多圍繞在線決策展開，如采用動態(tài)規(guī)劃[17]、馬爾科夫過程[18]、滾動算法[19]等，有關隨機動態(tài)VRP的最新研究綜述參見文獻[20]。實時決策要求決策者在極短時間內給出有效決策，對許多算法帶來了巨大挑戰(zhàn)。強化學習可快速實現(xiàn)端到端的輸出，將其同隨機動態(tài)VRP結合，可進一步推動該領域相關研究進展，有關強化學習在組合優(yōu)化領域的研究綜述，參見文獻[21, 22]。

對于VRPSTSTW，車輛沿先驗路徑行駛過程中，存在到達時間晚于顧客右時間窗的可能。若車輛在某一顧客處的到達時間大于規(guī)定的右時間窗，此時存在兩種選擇，延遲服務或跳過，分別對應TWVC跳過策略。無論TWVC還是跳過策略均存在不足，TWVC下顧客接受車輛提供的延遲服務，存在對某一顧客的延遲服務造成該路徑后續(xù)多個顧客延遲服務的可能；相反，采用跳過策略時，顧客不接受晚到車輛提供的延遲服務，很大程度上保證了該路徑后續(xù)顧客的準時服務，但此舉可能大幅增加企業(yè)運營成本。實際上，車輛在任一顧客處的遲到時間有長有短，遲到程度的大小(如遲到1s與遲到1h)對后續(xù)顧客服務過程造成的影響不同，應當依據(jù)影響程度大小采取不同的應對措施。基于這個動機，本文提出了兩種混合修正策略，根據(jù)對顧客不同程度的延遲采取不同的應對措施，這一點符合常識。

本文的貢獻與創(chuàng)新：(1)指出影響程度大小可由后續(xù)顧客延遲服務數(shù)量反映；(2)定義顧客服務水平為準時服務顧客數(shù)量與該路徑總的顧客數(shù)量的比值，即時間窗內獲得服務顧客的比例；(3)提出兩種混合修正策略(分別記為A、B)，兩種混合修正策略均通過隨機模擬實驗近似量化當前決策(延遲服務或跳過)對后續(xù)顧客服務過程的影響，根據(jù)量化結果采取不同的調整措施，以實現(xiàn)提升顧客服務水平和降低運營成本的目的。

1 模型及混合修正策略

1.1 帶修正策略的隨機規(guī)劃模型

VRPSTSTW的SPR模型為：

1.2 混合修正策略

(1)混合修正策略A

(2)混合修正策略B

混合修正策略A與B的區(qū)別如下：混合修正策略A給出是否為當前顧客提供延遲服務的決策，而混合修正策略B給出是否服務下一顧客的決策。相對于混合修正策略A，混合修正策略B預先判斷是否服務下一顧客，若是，車輛繼續(xù)行駛至下一顧客，此時車輛能否在下一顧客要求的時間窗內到達是不確定的；反之，車輛跳過對下一顧客的服務，從車場在當前時刻立即派出空閑車輛為該顧客提供服務，故空閑車輛有可能在該顧客要求的時間窗內提供服務。

2 求解算法

SPR分兩個階段求解VRPSTSTW：第一階段，根據(jù)先驗知識確定先驗路徑；第二階段，對車輛按照既定路徑實際行駛過程出現(xiàn)的“失敗”給予修正，其目標函數(shù)為最小化第一階段路徑總成本及第二階段“失敗”條件下的路徑修正成本。基于旅行時間和服務時間的均值，運用改進遺傳算法獲取先驗路徑，后采用隨機模擬方法求解混合修正策略下給定先驗路徑的平均修正成本及顧客服務水平。

2.1 改進遺傳算法

遺傳算法是應用最為廣泛、最為成功的元啟發(fā)式算法之一，其核心思想源于生物進化理論“物競天擇，適者生存”。對一個種群而言，種群中個體對應的適應度值不同，個體獲得繁衍后代的機會不同，適應度值高的個體在遺傳運算中被選擇的概率較大，適應度值低的個體則以很大概率被淘汰，因此，對某一種群而言，經過一定的進化次數(shù)后，可以得到一個適應度值普遍較高的種群。遺傳算法常用于求解VRP及其變形問題[25, 26]，本文在傳統(tǒng)遺傳算法的基礎上，對種群中的個體添加局部搜索策略，具體的算法步驟如下：

Step1 編碼

Step2 計算個體適應度

Step3 正比選擇策略

正比選擇策略，即每個個體被選中進行遺傳運算的概率為該個體的適應度值和所有被選擇個體適應度值總和的比值。

Step4 順序交叉策略

順序交叉策略可以較好地保持顧客間的相鄰關系，適用于VRP的求解[13]。該策略隨機生成兩個交叉點，對交叉點間配對個體的部分基因進行交換并恢復個體合法性，交叉過程如圖1所示。

父代P1= 1 23 4 5 6交叉子代 P1’= 2 3 4 1 5 6 父代P2= 3 24 16 5子代 P2’= 2 1 3 4 6 5 交叉點交叉點

Step5 變異操作

采用倒位變異方法，即隨機地在染色體上選取兩個倒位點并順序翻轉倒位點間的顧客位置，變異過程如圖2所示。

倒位點1倒位點2 變異 父代P= 1 3 4 2 5 6 子代 P’= 1 3 2 4 5 6

Step6 局部搜索操作

對完成遺傳運算后的個體添加局部搜索策略，該局部搜索策略由破壞和修復算子、交換算子及插入算子組成(以不同概率選擇不同局部搜索算子)，各算子說明如下：

(1)破壞與修復算子

(2)交換算子

交換算子，即隨機地在染色體上選取兩個顧客并交換其位置。

(3)插入算子

插入算子，即隨機地在染色體上選取兩個顧客，并將第一個顧客插入到第二個顧客位置之后。

Step7 篩選新種群

將經過遺傳運算后得到的子代種群混入父代種群中，并按照個體的適應度值大小進行降序排列，保留前個個體，其中為種群規(guī)模。

Step8 停止準則

雙重停止準則：以最大迭代次數(shù)或連續(xù)次種群最優(yōu)解不發(fā)生變化為算法停止準則。

2.2 隨機模擬實驗

運用文獻[10，14]中判斷路徑可行性及計算“失敗”條件下期望路徑修正成本的隨機模擬方法，分別求解兩種混合修正策略下某一給定路徑的平均修正成本及顧客服務水平。求解算法中所涉及的變量符號及表示含義同上文一致。整個算法分為三個部分：第一部分計算混合修正策略A下給定路徑的平均修正成本及顧客服務水平；第二部分計算混合修正策略B下給定路徑的平均修正成本及顧客服務水平；第三部分判斷車輛在顧客處應執(zhí)行何種修正策略。算法流程如下：

(1)混合修正策略A

Step1 令=1，1=0，2=0，為隨機模擬執(zhí)行的次數(shù)。

(2)混合修正策略B

Step1 令=1，1=0，2=0，為隨機模擬執(zhí)行的次數(shù)。

Step6 置=+1，轉Step2。

(3)選擇修正策略的隨機模擬實驗

Step1 令=1，=0，為隨機模擬執(zhí)行的次數(shù)。

第3部分涉及混合修正策略A、B與跳過策略、TWVC之間的相互比較，由于跳過策略與TWVC的隨機模擬實驗與上述算法相似，故此處不再一一給出。

3 仿真試驗及結果分析

3.1 案例選擇

表1 改進遺傳算法及隨機模擬參數(shù)設置

3.2 實驗結果及分析

運用改進遺傳算法、CPLEX求解器以及混合修正策略，對部分Solomon算例進行實驗，實驗結果如表2(25個顧客)、表3(100個顧客)所示。相關說明如下：表2中每一算例下的結果為10次實驗中的平均值；表3中每一算例下的結果為10次實驗中的最優(yōu)值；DC為先驗路徑對應的車輛運輸距離、VEH為先驗路徑使用的車輛數(shù)；SC_COST、HA_COST、HB_COST及TWVC_COST分別為跳過策略、混合修正策略A、混合修正策略B及TWVC下的平均路徑修正成本；SC_SL、HA_SL、HB_SL及TWVC_SL分別為跳過策略、混合修正策略A、混合修正策略B及TWVC下的平均顧客服務水平。

表2 實驗結果(25個顧客)

表3 實驗結果(100個顧客)

由表2中第2列～第5列可知，文中給出的改進遺傳算法能夠找到小規(guī)模算例的精確解。由第6列～第13列知，四種修正策略對應的平均路徑修正成本大小關系為SC_COST > HA_COST > HB_COST >TWVC_COST，平均顧客服務水平對應的大小關系為HB_SL > SC_SL > HA_SL > TWVC_SL。相對于TWVC，跳過策略對應的顧客服務水平增加了2.42%，其相應的路徑修正成本增加了1 275.09。混合修正策略A對應的顧客服務水平增加了2.23%，其路徑修正成本同樣增加了667.14。由這四個數(shù)據(jù)可知，混合修正策略A相對跳過策略以7.98%(服務水平降低了0.19%)的顧客服務水平損失換取47.68%(成本減少了607.95)的路徑修正成本節(jié)省，兩者比值為5.97。因此，混合修正策略A可以在保持同跳過策略近似顧客服務水平的同時大幅降低路徑修正成本。相對于跳過策略，混合修正策略B對應的顧客服務水平增加了0.47%，其對應的路徑修正成本減少了709.75(占跳過策略修正成本的54.69%)，即混合修正策略B在顧客服務水平、路徑修正成本兩個層面均優(yōu)于跳過策略。相對于混合修正策略A，混合修正策略B對應的路徑修正成本降低了101.80、顧客服務水平增加了0.67%，即混合修正策略B在路徑修正成本、顧客服務水平兩個層面均優(yōu)于混合修正策略A。

由表3中第2列～第5列可知，文中給出的改進遺傳算法能夠找到大規(guī)模算例的近似最優(yōu)解。表3可得出與表2一致的結論，唯一區(qū)別是混合修正策略B下的平均路徑修正成本略大于混合修正策略A，原因在于混合修正策略B在判斷下一顧客是否服務時存在誤判的可能性，該誤判使得本可以按照TWVC修正的顧客改用跳過策略修正，進而造成對應路徑的修正成本略大于混合修正策略A的情況。誤判多發(fā)生在C1系列，原因在于C1系列為聚類型案例，其發(fā)生“失敗”的可能性較大，故誤判的比例也相對較高。此外，當文中TWVC的懲罰系數(shù)較大時，混合修正策略A、B均在顧客服務水平、路徑修正成本兩個層面上優(yōu)于TWVC。

由實驗結果分析可知：改進遺傳算法能夠找到小規(guī)模算例的精確解，大規(guī)模算例的近似最優(yōu)解；混合修正策略B在顧客服務水平、路徑修正成本兩個層面上均優(yōu)于跳過策略、混合修正策略A；混合修正策略A可以在近似保持跳過策略高服務水平的同時大幅降低其路徑修正成本。跳過策略、混合修正策略A和B相對于TWVC均可大幅提升顧客服務水平，當TWVC下懲罰系數(shù)較小時，三種策略對應的路徑修正成本均會增加，此時需要決策者權衡顧客服務水平與運營成本之間的權重。

4 總結與展望

針對VRPSTSTW，構建了SPR模型，同時給出了求解該模型的改進遺傳算法以及兩種混合修正策略。基于標準Solomon算例進行仿真實驗，結果表明：改進遺傳算法能夠找到小規(guī)模算例的精確解，大規(guī)模算例的近似最優(yōu)解；混合修正策略A、B均可顯著降低跳過策略下的高路徑修正成本，同時提高TWVC下的低顧客服務水平。此外，該實驗結果也進一步表明當車輛在某一顧客處的到達時間略大于右時間窗時，即對該顧客的延遲服務并不會對該路徑后續(xù)顧客服務過程造成較大影響時，采用延遲服務的決策可獲得較優(yōu)結果。

本文構建的隨機VRP模型與實際VRP仍存在一定差距，進一步的研究方向包括：(1)時變網(wǎng)絡可有效反映路網(wǎng)動態(tài)性，故可進一步研究時變網(wǎng)絡下的隨機VRP，或隨機變量分布函數(shù)隨時間發(fā)生變化的VRP，該類問題更具實際意義； (2)現(xiàn)有的適用于求解時間窗約束下隨機時間VRP的修正策略較少，提出更具實用性及可操作性的修正策略是值得關注的重點；(3)利用運輸過程中實時更新的有關數(shù)據(jù)，及時調整車輛運行路徑并不斷促進車輛間的相互合作，以豐富現(xiàn)有修正策略；(4)借助信息通信技術收集的關于整個運輸過程的數(shù)據(jù)，搭建不確定環(huán)境下基于閉環(huán)數(shù)據(jù)驅動模式的、具備反饋機制的、可實時在線學習的車輛路徑優(yōu)化系統(tǒng)。

[1] DANTZIG G, RAMSER J. The truck dispatching problem[J]. Management Science, 1959, 6(1): 80-91.

[2] 趙紅霞, 劉高森, 李愈. 基于隨機游走的分類垃圾回收最優(yōu)路徑規(guī)劃[J]. 交通運輸工程與信息學報, 2018, 16(3): 103-108.

[3] BRAEKERS K, RAMAEKERS K, NIEUWENHUYSE I V. The vehicle routing problem: state of the art classification and review[J]. Computers & Industrial Engineering, 2016, 99: 300-313.

[4] OYOLA J, ARNTZEN H, WOODRUFF D L. The stochastic vehicle routing problem, a literature review, part I: models[J]. Euro Journal on Transportation & Logistics, 2018, 7(3): 193-221.

[5] OYOLA J, ARNTZEN H, WOODRUFF D L. The stochastic vehicle routing problem, a literature review, part Ⅱ: solution methods[J]. Euro Journal on Transportation & Logistics, 2017, 6(4): 349-388.

[6] GENDREAU M, JABALI O, REI W. Future research directions in stochastic vehicle routing[J]. Transportation science, 2016, 50(4): 1163-1173.

[7] MIRANDA D M, CONCEICAO S V. The vehicle routing problem with hard time windows and stochastic travel and service time[J]. Expert Systems with Applications, 2016, 64: 104-116.

[8] ZHANG J L, LAM W H, CHEN B. A stochastic vehicle routing problem with travel time uncertainty: trade-off between cost and customer service[J]. Networks & Spatial Economics, 2013, 13(4): 471-496.

[9] MIRANDA D M, BRANKE J, CONCEICAO S V. Algorithms for the multi-objective vehicle routing problem with hard time windows and stochastic travel time and service time[J]. Applied Soft Computing, 2018, 70: 66-79.

[10] LI X Y, TIAN P, LEUNG S. Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm[J]. International Journal of Production Economics, 2010, 125(1): 137-145.

[11] ZHANG J L, LAM W H, CHEN B. On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows[J]. European Journal of Operational Research, 2016, 249(1): 144-154.

[12] SALAVATI-KHOSHGHALD M, GENDREAU M, JABALI O, et al. An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy[J]. European Journal of Operational Research, 2018, 273(1): 175-189.

[13] SALAVATI-KHOSHGHALD M, GENDREAU M, JABALI O, et al. A hybrid recourse policy for the vehicle routing problem with stochastic demands[J]. Euro Journal on Transportation & Logistics, 2019, 8(3): 269-298.

[14] ANDRES G, LAURENCE D, NACIMA L, et al. A multi-population algorithm to solve the vrp with stochastic service and travel times[J]. Computers & Industrial Engineering, 2018, 125: 144-156.

[15] SHI Y, BOUDOUH T, GRUNDER O. A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times[J]. Transportation Research Part E Logistics and Transportation Review, 2019, 128: 52-95.

[16] CHEN L, GENDREAU M, HA M H, et al. A robust optimization approach for the road network daily maintenance routing problem with uncertain service time[J]. Transportation research Part E Logistics and transportation review, 2016, 85: 40-51.

[17] 周鮮成, 王莉, 周開軍, 等. 動態(tài)車輛路徑問題的研究進展及發(fā)展趨勢[J]. 控制與決策, 2019, 34(3): 449-458.

[18] ULMER M W, GOODSON J C, MATTFELD D C, et al. On modeling stochastic dynamic vehicle routing problems[J]. Euro Journal on Transportation and Logistics, 2020, 9(2): 100008.

[19] GOODSON J C, THOMAS B W, OHLMANN J W. A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs[J]. European Journal of Operational Research, 2017, 258(1): 216-229.

[20] RITZINGER U, PUCHINGER J, HARTL R F. A survey on dynamic and stochastic vehicle routing problems[J]. International Journal of Production Research, 2016, 54(1): 215-231.

[21] 李凱文, 張濤, 王銳, 等. 基于深度強化學習的組合優(yōu)化研究進展[J/OL]. 自動化學報: 1-22[2020-12-09]. https: //kns. cnki. net/kcms/detail/11. 2109. tp. 20201207. 1738. 001. html.

[22] 徐翔斌, 李志鵬. 強化學習在運籌學的應用: 研究進展與展望[J]. 運籌與管理, 2020, 29(5): 227-239.

[23] ULMER M W, STRENG S. Same-Day delivery with pickup stations and autonomous vehicles[J]. Computers & Operations Research, 2019, 108: 1-19.

[24] GOEL R, MAINI R, BANSAL S. Vehicle routing problem with time windows having stochastic customers demands and stochastic service times: Modelling and solution[J]. Journal of Computational Science, 2019, 3: 1-10.

[25] 徐菱, 胡小林, 胡小亮. 時間窗約束下需求可拆分的揀選與配送聯(lián)合優(yōu)化問題研究[J]. 交通運輸工程與信息學報, 2020, 18(2): 18-29.

[26] 張傳琪, 張楊. 動態(tài)路網(wǎng)下多車型車輛路徑問題研究[J]. 交通運輸工程與信息學報, 2017, 15(2): 112-118.

[27] 林清國. 基于混合遺傳算法的有時間窗車輛路徑問題研究[D]. 濟南: 山東大學, 2007.

[28] SHAW P. Using constraint programming and local search methods to solve vehicle routing problems[C]// In Proceedings of the 4th International Conference on Principles and Practice of Constraint Programming. Berlin: Springer, 1998, 1520: 417-431.

[29] CHEN L, HA M H, LANGEVIN A, et al. Optimizing road network daily maintenance operations with stochastic service and travel times[J]. Transportation Research Part E Logistics and Transportation Review, 2014, 64: 88-102.

[30] EMEC U, CATAY B, BOZKAYA B. An adaptive large neighborhood search for an e-grocery delivery routing problem[J]. Computers & Operations Research, 2016, 69: 109-125.

[31] TURNER S, EISELE W, BENZ R. Travel time data collection handbook[R]. Texas: Texas Transportation Institute and Federal Highway Administration, 1998.

[32] EHMKE J, CAMPBELL A, URBAN T. Ensuring service levels in routing problems with time windows and stochastic travel times[J]. European Journal of Operational Research, 2015, 240(2): 539-550.

Hybrid Recourse Policy for the Vehicle Routing Problem with Stochastic Time

MA Jun1, 2，ZHANG Ji-hui1, 2，GUO Yi-yun3

(1. Institute of Complexity Science, Qingdao University, Qingdao 266071, China; 2. Shandong Key Laboratory of Industrial Control Technology, Qingdao 266071, China; 3. Qingdao Port Int. Co. Ltd., Qingdao 266071, China)

For the vehicle routing problem with stochastic travel and service time, and time windows, this study provides a stochastic programming model with a recourse and two-stage solving method. In the first stage,a modified genetic algorithm is used to find a prior route;in the second stage,two hybrid recourse policies (denoted by A and B, respectively) are designed to recourse the failure route. Based on a stochastic simulation experiment, the hybrid recourse policy denoted as A (B) determines whether the delayed service to the current customer (the service to the next customer) will cause a large-scale delayed service to the subsequent customers in the prior route, and makes a corresponding decision. Based on the Solomon benchmarks, the superiority of the two hybrid recourse policies and effectiveness of the modified genetic algorithm are shown, respectively, by comparing the experimental simulation results with those of the common recourse policies and the CPLEX Optimizer.The results have an unequivocal significance as a reference for how to solve the stochastic vehicle routing problem.

logistics engineering;vehicle routing;stochastic travel and service time; stochastic programming; hybrid recourse policy; modifiedgenetic algorithm

U492.3+12

A

10.19961/j.cnki.1672-4747.2021.04.039

1672-4747(2021)04-0087-11

2021-04-29

2021-06-28

2021-07-01

2021-04-29～05-06; 06-26; 06-28

國家自然科學基金項目(61673228, 62072260); 青島市科技計劃項目(21-1-2-16-zhz)

馬俊(1995—)，男，碩士研究生，研究方向：物流系統(tǒng)工程，E-mail: qdumjun1001@163. com

張紀會(1969—), 男, 教授, 主要研究方向: 智能優(yōu)化理論與方法、物流系統(tǒng)工程, E-mail: zhangjihui@qdu. edu. cn

馬俊，張紀會，郭乙運. 基于混合修正策略的隨機時間車輛路徑優(yōu)化方法[J]. 交通運輸工程與信息學報，2021, 19(4):87-97.

MA Jun，ZHANG Ji-hui，GUO Yi-yun. Hybrid Recourse Policy for the Vehicle Routing Problem with Stochastic Time[J]. Journal of Transportation Engineering and Information, 2021, 19(4): 87-97.

(責任編輯：李愈)