基于混合啟發(fā)式蟻群優(yōu)化算法在雙層車輛路徑問題的研究.pdf

1、NP問題是自然界中普遍存在的一類問題，由于其目標(biāo)解的搜索空間隨著規(guī)模的增加而呈現(xiàn)指數(shù)級的增長，所以該問題已經(jīng)成為當(dāng)今計算機科學(xué)，人工智能等領(lǐng)域的瓶頸問題和熱點問題。目前，傳統(tǒng)的基于最優(yōu)解的精確優(yōu)化方法在求解大規(guī)模的NP完全上表現(xiàn)的無能為力，而與在可接受的條件限制(如時間)內(nèi)找到問題的滿意解的啟發(fā)式算法成為解決該問題的一個有力工具，從而也成為科學(xué)界應(yīng)用界研究的熱點。
　　 蟻群優(yōu)化算法作為一種群智能啟發(fā)式算法，憑借其自身的正向反饋

2、(能保證快速找到好的解)，螞蟻間的耦合性小(適合分布式計算并可以逃避過早的收斂)和基于貪婪的啟發(fā)式搜索(幫助算法在早期階段找到可行解)等特性，在求解NP問題上得到了廣泛的應(yīng)用，并且有較為完善的理論基礎(chǔ)。另一方面，本文所重點研究的車輛路徑問題是一類典型的NP問題。實際生活中的很多問題都可以被抽象為車輛路徑問題，如快遞發(fā)貨問題，飛機、鐵路列車、水運船舶及公共汽車的調(diào)度問題，物流配送問題，工作排班等問題。因此，研究車輛路徑問題的啟發(fā)式算法有著

3、極為重要的理論意義和現(xiàn)實價值。經(jīng)過幾十年的發(fā)展，該問題也取得了喜人的成果，在理論和應(yīng)用上都表現(xiàn)了很大的可行性。
　　 本課題研究了混合啟發(fā)式蟻群優(yōu)化算法(結(jié)合改進(jìn)的蟻群優(yōu)化算法結(jié)合鄰域搜索算法)及其在車輛路徑問題中的應(yīng)用，結(jié)合啟發(fā)式算法善于發(fā)現(xiàn)可能存在最優(yōu)解的區(qū)域和局部搜索算法善于在某個區(qū)域中找到更好的解的各自優(yōu)勢，提出了混合啟發(fā)式算法，解決了帶容量約束的車輛路徑問題和在學(xué)術(shù)界提出不久的雙層車輛路徑問題，并且在公開測試樣例表現(xiàn)出

4、了一定的優(yōu)越性，說明了算法的有效性。
　　 本課題主要取得的成果主要有以下幾個方面：第一，在原有基礎(chǔ)蟻群優(yōu)化算法(ACO)基礎(chǔ)上，對該元啟發(fā)式算法根據(jù)車輛路徑問題的特點進(jìn)行了改進(jìn)，并在性能和效率上取得更好的結(jié)果；第二，在領(lǐng)域下降搜索算法的基礎(chǔ)上提出了一種局部搜索能力更強的多領(lǐng)域下降搜索法；第三，在大規(guī)模的雙層路徑問題中，提出了一種效率更高的局部搜索算法：基于閾值的領(lǐng)域搜索；第四，結(jié)合貪婪算法，蟻群優(yōu)化算法和各種領(lǐng)域搜索算法，本文