基于蟻群算法車輛導航系統路由選擇問題的研究

車高峰 陸月然 譚 軍

（百色學院信息工程學院，廣西 百色 533000）

基于蟻群算法車輛導航系統路由選擇問題的研究

車高峰 陸月然★譚 軍

（百色學院信息工程學院，廣西 百色 533000）

利用蟻群運動的遍歷性、隨機性和規律性特點，分析了車輛導航系統路由選擇問題的蟻群優化算法，仿真結果表明該方法是一種簡單有效的算法。

蟻群優化算法；車輛導航系統；路由選擇問題

1 引言

在智能交通系統中車輛導航系統占據重要地位，通過地圖查詢、路線規劃、自動導航來確定車輛最優行駛路線，為出行旅游者提供最優路線。車輛導航技術是多學科交叉的結晶，結合了導航衛星以及目標定位技術等。為了解決動態路由問題，學者提出了很多算法，如Dijkstra算法、A*算法等。上世紀90年代蟻群優化（Ant Colony Optimization）算法由意大利學者M.Dorigo等人最早提出。由于蟻群算法有較強的自適應性、魯棒性，在尋優路徑中取得了一系列較好的實驗結果。本文基于蟻群算法對路由選擇進行研究，同時避免在路由選擇過程中陷入局部極值。

2 路由選擇問題的蟻群優化算法

路由選擇問題是運籌學、組合優化等領域中一個著名的難題，由于其NP難題性質，迄今尚未能徹底解決。目前求解這類問題的主要方法有模擬退火算法[1-2]、遺傳算法[3]、啟發式搜索法、Hopfield神經網絡算法[4]等。下面簡單介紹蟻群基本算法。

設某交通網絡中有m輛車，每輛車有以下特征：車輛根據以地點距離和路段上外激素的數量為變量的概率函數選擇下一個地點（設τ(t)為t時刻路段e(i，j)上外激素的強度）。規定車輛不允許轉到剛剛到過的地點，有禁忌表控制（設tabus表示第s輛車的禁忌表，tabus(k)表示禁忌表中第k個元素）。它完成周游后，車輛在它每一條訪問的路段留下外激素。

2.1 導航系統選擇下一路段規則

初始時刻，各條路段上的信息激素相等，設τij(0)=C（C為常數）。車輛s(s=1,2,…,m)在運動過程中，根據各條路段上信息量決定轉移方向，表示在車輛s由點i轉移到地點j的概率。

其中alloweds={0，1…，n-1}-tabus表示車輛s下一步允許選擇的交通地點，tabus(s=1，2，…，m)用于記錄車輛s當前所走過的地點，集合tabus隨著進化過程做動態調整。ηij表示路段(i，j)的能見度，利用啟發式算法算出，一般取dij表示地點i與地點j之間的距離。α表示軌跡的相對重要性，β表示能見度的相對重要性。

2.2 信息更新規則

設ρ表示信息的持久性。1-ρ理解為信息衰減度。隨著時間的推移，以前留下的信息逐漸消失，用參數1-ρ表示軌跡信息消逝度，經過n個時刻，車輛完成一次循環，各路徑上信息量要根據以下公式調整：

2.3 車輛導航系統路由蟻群算法的基本步驟

（1）初始化迭代步數nc←0以及τij和?τij的值,將m輛車隨機置于n個地點上；

（2）將各輛車的初始出發點置于當前解集中,對每輛車s (s=1,2,...,m),按概率p移至下一地點j,將地點j置于當前解集；

（3）計算各車輛行駛的路徑長度Ls(s=1,2,...,m），記錄當前的最好解；

（4）按更新方程修改軌跡強度；

（5）nc←nc+1；

（6）nc〈預定的迭代次數且無退化行為(即找到的都是相同解)則轉（2）；

（7）目前最好解。

3 實驗仿真

參數設置：迭代步數nc≤200；

假設從出發地到目的地途經31座城市，這31座城市加上出發地和目的地都是相互連通的，這31座城市分別編號1，2,3，......,31,它們坐標依次定義如下：

B=[1300 2300；3630 1310；4170 2240；3712 1399；3488 1535；3326 1556；3238 1229；4196 1004；4312 790；4386 570；3007 1970；2562 1756；2788 1491；2381 1676；1332 695；3715 1678；3918 2179；4061 2370；3780 2212；3676 2578；4029 2838；4263 2931；3429 1908；3507 2367；3394 2643；3439 3201；2935 3240；3140 3550；2545 2357；2778 2826；2370 2975]；

利用Matlab對以上述蟻群算法進行仿真結果如圖1。

通過算法求得途中這31座城市最優路徑為：1，15，14， 12，13，11，23，16，5，6，7，2，4，8，9，10，3，18，17，19，24，25，20，21，22，26，28，27，30，31，29。從上圖可以看出當算法迭代次數超過75次后，最優路徑長度已經基本保持不變了，求得為1.5590e+004。

圖1 最優路徑和迭代次數圖

[1]王凌．智能優化算法及其應用[M]．北京：清華大學出版社，2001：195-211．

[2]高國華，沈林成，常文森．求解TSP問題的空間銳化模擬退火算法[J]．自動化學報，1999，25(3)：425-428．

[3]謝勝利，唐敏，董金祥．求解TSP問題的一種改進的遺傳算法[J]．計算機工程與應用，2002，38(8)：58-60．

[4]張立明．人工神經網絡的模型及其應用[M]．上海：復旦大學出版社，1994：97-98．

Solving Routing Problem of Vehicle Navigation System byAnt Colony Optimization Algorithm

Che Gaofeng Lu Yueran Tan Jun
（College of Information Engineering,Baise University,Baise 533000,Guangxi）

Using the properties of ergodicity,randomicity and regularity of ant colony algorithm,ant colony optimization (ACO)algorithm is analyzed to solve routing problem of vehicle navigation system.Simulation results show that chaos ant colony optimization is a simple and effective algorithm.

ant colony optimization algorithm;vehicle navigation system;routing problem

TP301

A

1008-6609(2015)11-0046-02

車高峰，男，山東煙臺人，碩士，講師，研究方向：現場總線技術、蟻群算法；

*通訊作者：陸月然，男，廣西天等人，碩士，副教授，研究方向：物聯網。

百色學院一般科研項目，項目編號：2014KB06；廣西高校科學技術研究項目，項目編號：KY2015LX388；三亞市院地科技合作項目，項目編號：2013YD56。