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

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

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

【部分圖文】：

車輛路徑偏離情況

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

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

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



本文編號：3250402