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

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

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

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