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

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

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

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

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