改進(jìn)的蟻群算法解決車輛路徑問(wèn)題及其web GIS實(shí)現(xiàn).pdf

1、隨著問(wèn)題規(guī)模的擴(kuò)大，組合優(yōu)化問(wèn)題常常會(huì)呈現(xiàn)組合爆炸特征，此類問(wèn)題無(wú)法使用常規(guī)方法來(lái)求解，屬于NP-Hard問(wèn)題,車輛路徑問(wèn)題就是典型的組合優(yōu)化問(wèn)題。蟻群算法(ACO)是受自然界中螞蟻搜索食物行為啟發(fā)而提出的一種智能優(yōu)化算法。研究發(fā)現(xiàn)，蟻群算法可以較好地求解VRP(Vehicle Routing Problem，車輛路徑優(yōu)化)等組合優(yōu)化問(wèn)題。蟻群算法發(fā)現(xiàn)較好解的能力很強(qiáng)，具有分布式計(jì)算、魯棒性強(qiáng)、易于與其他方法結(jié)合等優(yōu)點(diǎn)，具有十分廣闊的應(yīng)

2、用前景。然而，蟻群算法存在求解速度慢，在規(guī)模擴(kuò)大后帶來(lái)收斂慢等問(wèn)題。對(duì)車輛路徑問(wèn)題解決上，現(xiàn)有的蟻群算法存在難以回歸原點(diǎn)等問(wèn)題。此外在如何將蟻群算法建模到物流軟件系統(tǒng)中，使之成為一種web應(yīng)用而投入到實(shí)際應(yīng)用也成為當(dāng)前急需解決的問(wèn)題。這些問(wèn)題也是我們面臨的巨大挑戰(zhàn)。 本文主要依據(jù)蟻群算法解決配送路線的優(yōu)化問(wèn)題，文章從以下幾個(gè)方面展開(kāi)：首先充分概括了當(dāng)前的蟻群算法在車輛路徑問(wèn)題上的研究。詳細(xì)分析了基本蟻群算法的原理，然后詳細(xì)闡述了

3、VRP問(wèn)題并引用了其數(shù)學(xué)模型，并介紹了蟻群算法解決VRP問(wèn)題的方法以及現(xiàn)狀面臨的挑戰(zhàn)。在創(chuàng)新方面，本文提出節(jié)點(diǎn)之間的路線實(shí)際上存在大量冗余信息，這是因?yàn)楣?jié)點(diǎn)間的距離太大或太小時(shí)可以簡(jiǎn)化蟻群算法輸入，具體做法是通過(guò)對(duì)距離較長(zhǎng)的路線進(jìn)行屏蔽、對(duì)距離較短的路線進(jìn)行合并處理，這樣的產(chǎn)生聚合組來(lái)優(yōu)化網(wǎng)絡(luò)，以便于蟻群算法的快速收斂，聚合后的組在算法完畢后需進(jìn)行類TSP處理使得最終形成一條完整路徑。然后，針對(duì)車輛路徑問(wèn)題，傳統(tǒng)的蟻群算法公式中沒(méi)有涉及

4、到回配送中心問(wèn)題，隨后學(xué)者所改進(jìn)的算法公式雖然可以使車輛在適當(dāng)?shù)臅r(shí)刻回到配送中心，但代價(jià)是破壞了經(jīng)典蟻群算法公式，而使得算法中參數(shù)大小無(wú)法確定，對(duì)此情況，本文改進(jìn)了算法公式，提出了一個(gè)新的概率，這個(gè)概率的由車載重和車與配送中心的距離決定，車輛根據(jù)此概率來(lái)決定是否返回配送中心，通過(guò)對(duì)公式的證明和最終實(shí)驗(yàn)我們確定新的概率公式的正確性。最后，文章通過(guò)使用web GIS（地理信息系統(tǒng)），將算法融合到可視化地圖中，通過(guò)web服務(wù)發(fā)布出去，方便了客

5、戶的瀏覽與使用。再將帶有蟻群算法的地理信息系統(tǒng)作為智能物流配送管理系統(tǒng)的一個(gè)模塊，使得其支持多個(gè)用戶的進(jìn)行計(jì)劃、計(jì)算、查看、修改配送路線等操作。 本文第一章是緒論部分，概述了研究背景與現(xiàn)狀以及本文結(jié)構(gòu)。第二章首先講述了一些基本理論概念，包括介紹了蟻群算法的基本原理以及車輛路徑問(wèn)題的定義和數(shù)學(xué)建模。然后綜述了利用蟻群算法解決車輛路徑問(wèn)題的一些思路，并總結(jié)了已有的改進(jìn)蟻群算法對(duì)車輛路徑問(wèn)題的解決。接著本文介紹了地理信息系統(tǒng)的一些概念