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

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

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

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

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