基于改進蟻群算法的車輛路徑優(yōu)化

宋志飛 張俊峰

摘要：對基本蟻群算法做了分析的基礎(chǔ)上，針對車輛交通路徑的特點，本文提出適用于求解車輛路徑規(guī)劃問題的改進算法。在基本蟻群算法的基礎(chǔ)上引入啟發(fā)式因子，提高了算法前期的收斂速度.分析了參數(shù)對算法結(jié)果準確性與蟻群算法求解速度的影響，提出了自適應(yīng)調(diào)整參數(shù)的策略，以提高解的質(zhì)量.結(jié)合仿真實驗的數(shù)據(jù)，將改進蟻群算法與基本蟻群算法進行了比較，實驗驗證了改進算法的可行性.

關(guān)鍵詞：蟻群算法；車輛路徑優(yōu)化；最優(yōu)路徑

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2018）23-0225-02

隨著相關(guān)學者及專家對車輛路徑在優(yōu)化問題的分析中，提出了許多算法，如啟發(fā)式算法、遺傳算法和禁忌搜索算法[1].隨著經(jīng)濟與社會的發(fā)展，交通擁擠已成為制約城市和區(qū)域發(fā)展的瓶頸之一.尋找高效、合理的車輛交通路線已成為交通網(wǎng)絡(luò)系統(tǒng)急需解決的難題.城市交通網(wǎng)絡(luò)誘導(dǎo)系統(tǒng)采用定位系統(tǒng)、電子地圖、通信技術(shù)和當前交通狀況給駕駛者提供最優(yōu)的路線[2].

1 基本蟻群算法

基本蟻群算法是從自然界中真實螞蟻集體覓食行為提出的，螞蟻群體在尋找食物時將一種叫作信息素的物質(zhì)會從它們走過的路徑中散發(fā)出來，其他通過該路徑的螞蟻會根據(jù)留在該段路徑的信息素的多少來判別要不要走該段路徑，最終會找到一段從最短路徑.

2 改進的蟻群算法

2.1 TSP與車輛路徑優(yōu)化的區(qū)別

（1） 在TSP問題中，開始點與目的點是隨機的，開始點與目的點一般是同一點的，螞蟻可以隨機出現(xiàn)在任何城市.在路徑優(yōu)化問題中，起點和終點是確定好的[4].在TSP問題中，起始點一般與目標點相同.而一般在交通問題中，開始點與目的點不是同一點；

（2） 城市車輛交通網(wǎng)絡(luò)中，節(jié)點較大，計算城市之間的距離需要花費大量時間，并且由于城市交通網(wǎng)絡(luò)的復(fù)雜性和不穩(wěn)定性，距離矩陣通常是稀疏矩陣 [5]；

（3） 而在TSP問題中，城市間的構(gòu)成的距離矩陣一般都是對稱矩陣，即[dij=dji]，而在交通網(wǎng)絡(luò)中，則不一定就是，即[dij≠dji]；

（4） 城市交通網(wǎng)絡(luò)中仍然存在一個節(jié)點只發(fā)散一個邊，相當于設(shè)置了一個陷阱，這使得搜索螞蟻失去了前進的能力，但是在TSP問題中沒有這樣的問題.

2.2 交通網(wǎng)絡(luò)蟻群算法

當基本蟻群算法用于解決交通問題時，很容易陷入局部最優(yōu)解.基本蟻群算法一開始就沒有有效的啟發(fā)因素，搜索的盲目性.提出了以下改進方法.

2.2.1 啟發(fā)式因子

通過一開始就增加對目標節(jié)點的引導(dǎo)，改進算法在開始時獲得較好的起始值，提高蟻群在目標節(jié)點附近的速度，加快收斂速度，在短時間內(nèi)找到最優(yōu)值，并減少資源消費。

4 結(jié)束語

仿真結(jié)果表明，改進蟻群算法的收斂速度明顯提高.同時，為了減少算法進入局部最優(yōu)解的可能性，提高了算法的自適應(yīng)能力.仿真實驗結(jié)果表明，改進后的算法與基本蟻群算法相比，可以加快算法的速度.收斂速度進一步提高了蟻群算法的有效性，為車輛路徑優(yōu)化問題提供了一種優(yōu)化的途徑.

參考文獻：

[1] MitsuoGen，Run Wei Cheng，Ding Wei Wang.Genetic Algorithms for Solving Shortest Path Problems[J].IEEE.2002，10（1）：121-135.

[2] 趙家俊，于寶琴.現(xiàn)代物流配送管理[M].北京：北京大學出版社，2004.

[3] 胡小兵，黃席樾.蟻群優(yōu)化算法及其應(yīng)用[J].計算機仿真，2004，21（5）：81-85.

[4] 溫惠英，徐建閩.基于改進型蟻群算法的車輛導(dǎo)航路徑規(guī)劃研究[J].公路交通科技，2009，1（26）：125-129.

[5] 雷登云，趙煒.基于改進蟻群算法的車輛路徑優(yōu)化模型[J].電子科技，2010，23（1）：8-14.

[6] 靳凱文，李春葆，秦前清.基于蟻群算法的最短路徑搜索方法研究[J].公路交通科技，2006，23（3）：128-134.

[7] 范紅平，陳麗娟，楊國軍，等.GAAA算法在直線步進電機控制中的應(yīng)用[J].電子科技，2006（10）：51-54.58.

【通聯(lián)編輯：唐一東】