針對客戶請求頻繁變動對同時送取貨車輛路徑方案造成的干擾問題,從配送成本和服務時間兩方面,對干擾事件造成的車輛路徑方案影響進行干擾辨識.結合客戶請求變動頻繁程度及其特征,以前期短、后期長不等份原則將配送任務期合理劃分為若干個時段,以廣義總費用偏離最小為目標,構建同時送取貨車輛路徑問題的分時段干擾管理模型,設計基于改進遺傳和禁忌搜索的求解算法,并選用Solomon標準問題庫中的數(shù)據(jù)進行算例驗證分析.結果顯示:該方案在優(yōu)化廣義總費用偏離方面較之實時干擾管理、增派車輛和全局重調(diào)度等方案均有明顯降低. 

【文章來源】：大連海事大學學報. 2020,46(04)北大核心CSCD

【文章頁數(shù)】：9 頁

【部分圖文】：

車輛路徑偏離情況

在配送時間上,客戶對時間窗的要求通常有兩種情況:一種是硬時間窗,指在客戶要求的時間范圍內(nèi)配送車輛必須完成配送,否則客戶將終止服務請求;另一種是軟時間窗,指在客戶要求的時間范圍內(nèi)配送車輛無法完成配送時,客戶不會直接終止配送服務請求,轉(zhuǎn)而給予一定的懲罰. 由于客戶往往要求配送時間同時滿足硬時間窗和軟時間窗約束,因此,本文將時間偏離成本轉(zhuǎn)換成廣義時間成本,即時間偏離懲罰函數(shù)Pjn(tjn),如圖2所示.在圖2中,tjn表示在第n時段結束時刻制訂的新干擾方案中,配送車輛到達未服務客戶點j的時間.[ETj,LTj]為客戶j的軟時間窗,其中,ETj為客戶j最早可以接受服務的時刻,LTj為客戶j滿意接受服務的最遲時刻. 當配送車輛在該范圍內(nèi)到達時,Pjn(tjn)等于0. [T0,LRj]為客戶j的硬時間窗,其中,T0為配送車輛最早可能到達時刻,LRj為客戶停止接受服務的時刻. 若配送車輛在客戶要求的軟時間窗前到達,即在[T0,ETj)內(nèi)到達,則車輛因等待產(chǎn)生了機會損失成本;若配送車輛在客戶要求的軟時間窗后、硬時間窗前到達,即在(LTj,LRj]內(nèi)到達,則服務延遲,產(chǎn)生時間偏離懲罰;若配送車輛在客戶要求的硬時間窗后到達,即在tjn>LRj時到達,客戶j停止接受服務[16]. 由上可知,Pjn(tjn)可表示為:

由于VRPSPD為NP難題[17],故本文構建的客戶請求變動VRPSPD分時段干擾管理模型需要采用啟發(fā)式算法求解. 考慮到不同啟發(fā)式算法的優(yōu)缺點,本文設計改進遺傳算法和禁忌搜索相結合的兩階段啟發(fā)式算法進行求解,算法設計整體框架如圖3所示.由圖3可見,本文算法設計的總體流程為:首先,通過two-opt操作選出最好的解碼結果,將遺傳算法與局部搜索算法相結合,對遺傳算法加以改進,提高其局部搜索能力,快速得到初始車輛最優(yōu)路徑解(即原始車輛配送路徑方案); 然后,在第tn時刻設計干擾管理新方案時,由于遺傳算法需要迭代較長,且運行結果的好壞對于編碼者水平具有很高的關聯(lián)性. 為此,本文選用能更好地跳出局部最優(yōu)困境且搜索速度快的禁忌搜索算法[18],對原方案進行全局逐步尋優(yōu)調(diào)整,最終獲得分時段VRPSDP問題干擾管理的滿意解.

【參考文獻】：
期刊論文
[1]帶回程取貨車輛路徑問題的干擾恢復模型[J]. 王旭坪,阮俊虎,孫自來,曹海艷.  系統(tǒng)工程學報. 2013(05)
[2]基于聯(lián)合配送的開放式動態(tài)車輛路徑問題及算法研究[J]. 葛顯龍,王旭,鄧蕾.  管理工程學報. 2013(03)



本文編號：3250402