車輛調(diào)度問題啟發(fā)式算法研究.pdf

1、車輛優(yōu)化調(diào)度問題是現(xiàn)代物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)，也是開展電子商務(wù)活動(dòng)中不可缺少的內(nèi)容。對(duì)車輛優(yōu)化調(diào)度理論與方法進(jìn)行系統(tǒng)研究是構(gòu)建綜合物流系統(tǒng)、建立現(xiàn)代調(diào)度指揮系統(tǒng)、發(fā)展智能交通運(yùn)輸系統(tǒng)和開展電子商務(wù)的基礎(chǔ)。 本文主要研究了一類車輛優(yōu)化調(diào)度問題：PDPTW問題（Pickup and Delivery Problem with Time Windows，帶時(shí)間窗口的裝卸貨問題）及其擴(kuò)展問題的優(yōu)化調(diào)度算法。有時(shí)間窗口的裝卸貨問題（PD

2、PTW）是個(gè)運(yùn)籌學(xué)問題，同時(shí)它又是組合優(yōu)化問題中一個(gè)典型的NP-hard問題，因此成為運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的研究的難點(diǎn)與熱點(diǎn)問題。 在已有研究工作的基礎(chǔ)上，本文分析了該問題及其擴(kuò)展問題的性質(zhì)，并提出了一種新的啟發(fā)式調(diào)度方法，并設(shè)計(jì)開發(fā)了輔助車輛調(diào)度的軟件決策平臺(tái)。本文的主要研究成果如下: 1. 分析研究有關(guān)PDPTW問題的標(biāo)準(zhǔn)算例庫(kù)，為算法的測(cè)試分析奠定了堅(jiān)實(shí)的基礎(chǔ)。調(diào)試原有的禁忌搜索算法，用標(biāo)準(zhǔn)算例庫(kù)進(jìn)行了測(cè)試分析，并

3、根據(jù)得到的結(jié)果，對(duì)禁忌搜索算法進(jìn)行進(jìn)一步分析和驗(yàn)證。 2．提出線性化1-PDPTW問題模型的方法，并運(yùn)用GLPK軟件包編寫程序分析單條路徑的優(yōu)化程度，輔助對(duì)算法性能的分析。 3．在對(duì)禁忌搜索算法測(cè)試分析的基礎(chǔ)上，以快速減少車輛數(shù)目為目標(biāo)，提出了一種獨(dú)特的啟發(fā)式算法。這是一種基于局域搜索和隨機(jī)擾動(dòng)思想的啟發(fā)式算法。先強(qiáng)制將短路徑的客戶插入到長(zhǎng)路徑，使得快速搜索到局部最小點(diǎn)，再用隨機(jī)擾動(dòng)跳到另一個(gè)區(qū)域重新開始搜索。用此算法對(duì)

4、插入算法得到的可行解進(jìn)行迭代改進(jìn)，可以迅速并且極大地提高解的質(zhì)量。 4．在上述算法的基礎(chǔ)上，進(jìn)行了改進(jìn)和擴(kuò)展研究，使其性能更好、能夠處理更復(fù)雜的PDPTW問題：在插入算法構(gòu)造初始解的階段，對(duì)于不同特性的算例采用不同的初始解構(gòu)造方法，使得構(gòu)造的初始解更加有效，更加穩(wěn)定；隨后提出處理多貨物類型及多車庫(kù)問題的方法，在對(duì)快速算法做很小改變的情況下，使其可以適應(yīng)多車庫(kù)問題的求解要求。 5．在對(duì)PDPTW問題有深刻理解的基礎(chǔ)上，本文