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

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

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

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

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

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