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

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

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

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

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