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

來源：互聯(lián)網(wǎng)   發(fā)布日期：2011-09-29 16:46:38   瀏覽：102752次  

隨著問題規(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)用前景。然而，蟻群算法存在求解速度慢，在規(guī)模擴大后帶來收斂慢等問題。對車輛路徑問題解決上，現(xiàn)有的蟻群算法存在難以回歸原點等問題。此外在如何將蟻群算法建模到物流軟件系統(tǒng)中，使之成為一種web應(yīng)用而投入到實際應(yīng)用也成為當前急需解決的問題。這些問題也是我們面臨的巨大挑戰(zhàn)。 本文主要依據(jù)蟻群算法解決配送路線的優(yōu)化問題，文章從以下幾個方面展開：首先充分概括了當前的蟻群算法在車輛路徑問題上的研究。詳細分析了基本蟻群算法的原理，然后詳細闡述了vrp問題并引用了其數(shù)學模型，并介紹了蟻群算法解決vrp問題的方法以及現(xiàn)狀面臨的挑戰(zhàn)。在創(chuàng)新方面，本文提出節(jié)點之間的路線實際上存在大量冗余信息，這是因為節(jié)點間的距離太大或太小時可以簡化蟻群算法輸入，具體做法是通過對距離較長的路線進行屏蔽、對距離較短的路線進行合并處理，這樣的產(chǎn)生聚合組來優(yōu)化網(wǎng)絡(luò)，以便于蟻群算法的快速收斂，聚合后的組在算法完畢后需進行類tsp處理使得最終形成一條完整路徑。然后，針對車輛路徑問題，傳統(tǒng)的蟻群算法公式中沒有涉及到回配送中心問題，隨后學者所改進的算法公式雖然可以使車輛在適當?shù)臅r刻回到配送中心，但代價是破壞了經(jīng)典蟻群算法公式，而使得算法中參數(shù)大小無法確定，對此情況，本文改進了算法公式，提出了一個新的概率，這個概率的由車載重和車與配送中心的距離決定，車輛根據(jù)此概率來決定是否返回配送中心，通過對公式的證明和最終實驗我們確定新的概率公式的正確性。最后，文章通過使用web gis（地理信息系統(tǒng)），將算法融合到可視化地圖中，通過web服務(wù)發(fā)布出去，方便了客戶的瀏覽與使用。再將帶有蟻群算法的地理信息系統(tǒng)作為智能物流配送管理系統(tǒng)的一個模塊，使得其支持多個用戶的進行計劃、計算、查看、修改配送路線等操作。 本文第一章是緒論部分，概述了研究背景與現(xiàn)狀以及本文結(jié)構(gòu)。第二章首先講述了一些基本理論概念，包括介紹了蟻群算法的基本原理以及車輛路徑問題的定義和數(shù)學建模。然后綜述了利用蟻群算法解決車輛路徑問題的一些思路，并總結(jié)了已有的改進蟻群算法對車輛路徑問題的解決。接著本文介紹了地理信息系統(tǒng)的一些概念。第三章開始是本文的核心部分，提出了一系列改進方法，如何分組，分組后如何計算等等，提出了一套切實可行的方案，并提出了對算法的改進。第四章是智能物流配送管理系統(tǒng)的實現(xiàn)部分，通過jsp / servlet、gis等技術(shù)發(fā)布服務(wù)，提高了用戶的可視化與可操作性。第五部分是總結(jié)與展望，提出了未來的一些研究方向。

贊助本站