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

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

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

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

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

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

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