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

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

隨著問(wèn)題規(guī)模的擴(kuò)大，組合優(yōu)化問(wèn)題常常會(huì)呈現(xiàn)組合爆炸特征，此類(lèi)問(wèn)題無(wú)法使用常規(guī)方法來(lái)求解，屬于np-hard問(wèn)題,車(chē)輛路徑問(wèn)題就是典型的組合優(yōu)化問(wèn)題。蟻群算法(aco)是受自然界中螞蟻搜索食物行為啟發(fā)而提出的一種智能優(yōu)化算法。研究發(fā)現(xiàn)，蟻群算法可以較好地求解vrp(vehicle routing problem，車(chē)輛路徑優(yōu)化)等組合優(yōu)化問(wèn)題。蟻群算法發(fā)現(xiàn)較好解的能力很強(qiáng)，具有分布式計(jì)算、魯棒性強(qiáng)、易于與其他方法結(jié)合等優(yōu)點(diǎn)，具有十分廣闊的應(yīng)用前景。然而，蟻群算法存在求解速度慢，在規(guī)模擴(kuò)大后帶來(lái)收斂慢等問(wèn)題。對(duì)車(chē)輛路徑問(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)前的蟻群算法在車(chē)輛路徑問(wèn)題上的研究。詳細(xì)分析了基本蟻群算法的原理，然后詳細(xì)闡述了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)行類(lèi)tsp處理使得最終形成一條完整路徑。然后，針對(duì)車(chē)輛路徑問(wèn)題，傳統(tǒng)的蟻群算法公式中沒(méi)有涉及到回配送中心問(wèn)題，隨后學(xué)者所改進(jìn)的算法公式雖然可以使車(chē)輛在適當(dāng)?shù)臅r(shí)刻回到配送中心，但代價(jià)是破壞了經(jīng)典蟻群算法公式，而使得算法中參數(shù)大小無(wú)法確定，對(duì)此情況，本文改進(jìn)了算法公式，提出了一個(gè)新的概率，這個(gè)概率的由車(chē)載重和車(chē)與配送中心的距離決定，車(chē)輛根據(jù)此概率來(lái)決定是否返回配送中心，通過(guò)對(duì)公式的證明和最終實(shí)驗(yàn)我們確定新的概率公式的正確性。最后，文章通過(guò)使用web gis（地理信息系統(tǒng)），將算法融合到可視化地圖中，通過(guò)web服務(wù)發(fā)布出去，方便了客戶(hù)的瀏覽與使用。再將帶有蟻群算法的地理信息系統(tǒng)作為智能物流配送管理系統(tǒng)的一個(gè)模塊，使得其支持多個(gè)用戶(hù)的進(jìn)行計(jì)劃、計(jì)算、查看、修改配送路線等操作。 本文第一章是緒論部分，概述了研究背景與現(xiàn)狀以及本文結(jié)構(gòu)。第二章首先講述了一些基本理論概念，包括介紹了蟻群算法的基本原理以及車(chē)輛路徑問(wèn)題的定義和數(shù)學(xué)建模。然后綜述了利用蟻群算法解決車(chē)輛路徑問(wèn)題的一些思路，并總結(jié)了已有的改進(jìn)蟻群算法對(duì)車(chē)輛路徑問(wèn)題的解決。接著本文介紹了地理信息系統(tǒng)的一些概念。第三章開(kāi)始是本文的核心部分，提出了一系列改進(jìn)方法，如何分組，分組后如何計(jì)算等等，提出了一套切實(shí)可行的方案，并提出了對(duì)算法的改進(jìn)。第四章是智能物流配送管理系統(tǒng)的實(shí)現(xiàn)部分，通過(guò)jsp / servlet、gis等技術(shù)發(fā)布服務(wù)，提高了用戶(hù)的可視化與可操作性。第五部分是總結(jié)與展望，提出了未來(lái)的一些研究方向。

贊助本站