帶有時間窗的車輛路徑問題的混合蟻群算法研究.pdf

1、車輛路徑問題(VehicleRoutingProblem，VRP)是近幾十年來運籌學、應用數(shù)學、網(wǎng)絡分析、圖論、計算機應用及交通運輸?shù)葘W科研究的一個熱點問題，其產生于現(xiàn)實的公路交通運輸領域，并在通訊、生產、國防、生物、計算機應用等領域得到了廣泛的應用。本文著重研究有時間窗的車輛路徑問題(VehicleRoutingProblemwithTimeWindows，VRPTW)，VRPTW現(xiàn)已被證明為NP-hard問題，當問題規(guī)模較大時，將很

2、難得到問題的精確解。探討如何經過少量的計算，得到一個相對滿意的解，已成為現(xiàn)階段學者研究的重點。 蟻群算法是受自然界中真實蟻群覓食行為的啟發(fā)而提出的一種模擬進化算法，在求解VRPTW等組合優(yōu)化問題上取得了很好的效果，自蟻群算法提出后，人們又提出了大量蟻群算法的改進算法，其性能和原算法相比，有了明顯的改進。 本文研究的主題，就在于提出更好的蟻群算法的改進算法，使求解問題的速度更快、結果更好。主要研究工作如下： (1)

3、以第三方物流配送中心的角度，通過對VRPTW模型的復雜性分析，構建合理的VRPTW數(shù)學模型。 (2)通過對目前蟻群算法的分析及實驗的測試，概括總結出各種算法的優(yōu)劣，提出蟻群算法的改進算法-混合蟻群算法，為快速、有效地求解VRPTW開辟了途徑，這是本文的核心部分。 (3)通過對混合蟻群算法的分析，利用面向對象的思想實現(xiàn)該算法，采用一系列BenchmarkProblems對算法進行測試，實驗結果表明混合蟻群算法在求解VRPT