基于大規(guī)模鄰域搜索的車輛調(diào)度快速算法研究.pdf

1、現(xiàn)代，企業(yè)為了提高競爭力，對供應(yīng)鏈管理提出了更高的要求，如何高效率地完成從原材料采購，產(chǎn)品生產(chǎn)到產(chǎn)品配送，已成為各公司研究的重點?，F(xiàn)代物流系統(tǒng)作為供應(yīng)鏈的重要環(huán)節(jié)，主要包括運輸、存儲、包裝、裝卸和搬運等若干相互依賴、相互制約的子系統(tǒng)，其中物流配送是一個與消費者相連的重要環(huán)節(jié)。 本文主要研究了一類車輛優(yōu)化調(diào)度問題――PDPTW問題（Pickup and Delivery Problem with Time Windows，帶時間窗

2、口的裝卸貨問題）及其擴展問題的優(yōu)化調(diào)度算法。有時間窗口的裝卸貨問題（PDPTW）是一個典型的NP-hard問題，因此成為運籌學(xué)與組合優(yōu)化領(lǐng)域的研究的難點與熱點。 本文主要在兩方面對PDPTW問題開展研究，首先，針對靜態(tài)的PDPTW問題，相關(guān)文獻中介紹的一些優(yōu)化算法在計算時間和解的質(zhì)量方面缺乏良好的平衡，如文獻[15]提到的自適應(yīng)方法，雖然能得到很好的解，但計算時間過長，難以滿足實時性要求。本文通過合理平衡計算時間和解質(zhì)量，提出了

3、一種快速LNS（Large Neighborhood Search,大規(guī)模鄰域搜索）算法，這種方法具有求解速度快、求解質(zhì)量好、對初始解的依賴性小的特點。在保持快速求解的前提下，利用模擬退火在全局尋優(yōu)中的優(yōu)勢，進一步提出了類模擬的快速LNS算法，改進了單一采用LNS算法的不足。其次，本文結(jié)合實際應(yīng)用時車輛在行駛過程中可能損壞的情況研究了動態(tài)PDPTW問題，給出了求解策略。 本文的研究工作和成果如下： 1．分析了PDPTW問

4、題的標準算例，對已有的相關(guān)算法進行了測試，理解其優(yōu)缺點，為尋求和改進算法打下基礎(chǔ)。 2．提出了改進的LNS算法，在保持解質(zhì)量的情況下，縮短了求解過程。求解過程主要以減少車輛為目標，通過優(yōu)先選出短路徑中的客戶和與之有較大相關(guān)性的客戶，來調(diào)整鄰域搜索方向，使之能快速收斂到一個較優(yōu)的解上，然后加入隨機擾動，充分利用LNS算法本身鄰域空間較大的優(yōu)勢，尋找在其它空間內(nèi)更優(yōu)的解。 3．對比了采用上述改進LNS算法所得到的解與其他相關(guān)

5、文獻所得到的解的質(zhì)量，分析了影響解質(zhì)量的因素，提出了類模擬退火的LNS算法，該算法在保持了改進LNS算法快速性的前提下，利用模擬退火在全局尋優(yōu)能力上的優(yōu)點，進一步改進原有解的質(zhì)量，對不同算例的仿真結(jié)果表明，該算法對提高隨機分布算例的解的質(zhì)量，具有極大的優(yōu)勢，并且減小了對于初始解的依賴性。 4．參考當(dāng)前車輛調(diào)度領(lǐng)域文獻中對動態(tài)車輛調(diào)度問題的研究，對動態(tài)PDPTW問題進行討論，結(jié)合實際執(zhí)行調(diào)度過程中車輛可能損壞的情況，給出解決此類問

6、題的策略，在盡量不新增車輛（即使新增車輛，可能到達事故點取貨后，仍然會延期交貨）的前提下，依靠剩下的車輛來完成所有客戶需求，問題的目標定義為最小化客戶不滿意度，其中客戶不滿意度包括延遲客戶的總數(shù)目和所有客戶的延遲時間和。 5．通過大量仿真測試，給出了靜態(tài)PDPTW的問題算法解質(zhì)量的分析，對比不同算法，不同初始解對問題求解的影響，并通過加入動態(tài)PDPTW的概念，分析各個算法的解結(jié)構(gòu)對抗突發(fā)事件的魯棒性。 本文的研究工作得到