蟻群算法在有時間窗的VRP問題中的應(yīng)用研究.pdf

1、隨著市場競爭的日益加劇，世界經(jīng)濟(jì)一體化的加強，物流運輸已經(jīng)成為企業(yè)提高市場競爭力和核心競爭力的重要手段。其中物流配送的車輛路徑優(yōu)化問題(VRP)涉及面較廣，需要考慮的因素較多，對企業(yè)提高服務(wù)質(zhì)量、降低物流成本、增加經(jīng)濟(jì)效益的影響較大，因而是一個亟待解決的重要問題。特別是隨著Internet的普及和電子商務(wù)的發(fā)展，傳統(tǒng)VRP算法已無法應(yīng)付快速回應(yīng)(Quick Response)顧客需求對物流配送提出的要求，于是時間窗的概念應(yīng)運而生。帶有時

2、間窗的車輛調(diào)度問題是比VRP復(fù)雜程度更高的NP難題，以往的求解方法可以分為精確算法和啟發(fā)式方法。精確算法由于引入嚴(yán)格的數(shù)學(xué)方法，無法避開指數(shù)爆炸問題，只能有效求解小規(guī)模的VRPTW問題。由于VRPTW問題是強NP難題，只能尋找近似算法。為此，人們把主要精力花在構(gòu)造高質(zhì)量的啟發(fā)式算法上。
　　 在這些啟發(fā)式算法中，蟻群算法因其很強的魯棒性、分布式計算和比較容易與其他算法工具相結(jié)合的優(yōu)點越來越受到人們的關(guān)注。然而，蟻群算法在求解大規(guī)

3、模問題時，存在搜索空間和時間性能上的矛盾，易出現(xiàn)過早收斂于非全局最優(yōu)解以及計算時間過長的弱點。另外，算法參數(shù)的選擇多憑借經(jīng)驗。針對這些弱點，本文在前人工作的基礎(chǔ)上，開展了關(guān)于改進(jìn)型蟻群算法在VRPTW中的研究，經(jīng)仿真實驗證明改進(jìn)后的算法較原算法更合理有效。并針對國內(nèi)運輸調(diào)度系統(tǒng)的空白，設(shè)計和分析了基于多種業(yè)務(wù)模型的運輸調(diào)度優(yōu)化系統(tǒng)。
　　 主要研究工作如下：
　　 1、通過一系列的仿真實驗，對蟻群算法參數(shù)的合理選取進(jìn)行了

4、較為深入的研究，提出了最優(yōu)算法參數(shù)組合。較于以前完全憑經(jīng)驗和試探來選取參數(shù)，大大提高了效率。
　　 2、將蟻群算法應(yīng)用于VRPTW問題的求解，通過引入勻稱度、啟發(fā)路徑數(shù)以及吸引力等概念對算法的轉(zhuǎn)移策略和更新策略進(jìn)行改進(jìn)，構(gòu)造了具有動態(tài)調(diào)整功能的蟻群算法。實驗仿真結(jié)果表明所設(shè)計的算法具有較強的搜索能力，計算效率較高，能夠有效地解決加速收斂與停滯現(xiàn)象之間的矛盾。
　　 3、在分析多種物流配送運輸調(diào)度業(yè)務(wù)的基礎(chǔ)上，分析和設(shè)計了