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

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

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

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

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