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

馬 俊，張紀(jì)會，郭乙運(yùn)

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

馬 俊1, 2，張紀(jì)會1, 2，郭乙運(yùn)3

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

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

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

0 引 言

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

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

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

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

1 模型及混合修正策略

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

VRPSTSTW的SPR模型為：

1.2 混合修正策略

(1)混合修正策略A

(2)混合修正策略B

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

2 求解算法

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

2.1 改進(jìn)遺傳算法

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

Step1 編碼

Step2 計算個體適應(yīng)度

Step3 正比選擇策略

正比選擇策略，即每個個體被選中進(jìn)行遺傳運(yùn)算的概率為該個體的適應(yīng)度值和所有被選擇個體適應(yīng)度值總和的比值。

Step4 順序交叉策略

順序交叉策略可以較好地保持顧客間的相鄰關(guān)系，適用于VRP的求解[13]。該策略隨機(jī)生成兩個交叉點(diǎn)，對交叉點(diǎn)間配對個體的部分基因進(jìn)行交換并恢復(fù)個體合法性，交叉過程如圖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 交叉點(diǎn)交叉點(diǎn)

Step5 變異操作

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

倒位點(diǎn)1倒位點(diǎn)2 變異 父代P= 1 3 4 2 5 6 子代 P’= 1 3 2 4 5 6

Step6 局部搜索操作

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

(1)破壞與修復(fù)算子

(2)交換算子

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

(3)插入算子

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

Step7 篩選新種群

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

Step8 停止準(zhǔn)則

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

2.2 隨機(jī)模擬實(shí)驗(yàn)

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

(1)混合修正策略A

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

(2)混合修正策略B

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

Step6 置=+1，轉(zhuǎn)Step2。

(3)選擇修正策略的隨機(jī)模擬實(shí)驗(yàn)

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

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

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

3.1 案例選擇

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

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

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

表2 實(shí)驗(yàn)結(jié)果(25個顧客)

表3 實(shí)驗(yàn)結(jié)果(100個顧客)

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

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

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

4 總結(jié)與展望

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

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

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

[2] 趙紅霞, 劉高森, 李愈. 基于隨機(jī)游走的分類垃圾回收最優(yōu)路徑規(guī)劃[J]. 交通運(yùn)輸工程與信息學(xué)報, 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)車輛路徑問題的研究進(jìn)展及發(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] 李凱文, 張濤, 王銳, 等. 基于深度強(qiáng)化學(xué)習(xí)的組合優(yōu)化研究進(jìn)展[J/OL]. 自動化學(xué)報: 1-22[2020-12-09]. https: //kns. cnki. net/kcms/detail/11. 2109. tp. 20201207. 1738. 001. html.

[22] 徐翔斌, 李志鵬. 強(qiáng)化學(xué)習(xí)在運(yùn)籌學(xué)的應(yīng)用: 研究進(jìn)展與展望[J]. 運(yùn)籌與管理, 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]. 交通運(yùn)輸工程與信息學(xué)報, 2020, 18(2): 18-29.

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

[27] 林清國. 基于混合遺傳算法的有時間窗車輛路徑問題研究[D]. 濟(jì)南: 山東大學(xué), 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

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

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

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

馬俊，張紀(jì)會，郭乙運(yùn). 基于混合修正策略的隨機(jī)時間車輛路徑優(yōu)化方法[J]. 交通運(yùn)輸工程與信息學(xué)報，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.

(責(zé)任編輯：李愈)