車高峰 陸月然 譚 軍

（百色學(xué)院信息工程學(xué)院，廣西 百色 533000）

基于蟻群算法車輛導(dǎo)航系統(tǒng)路由選擇問題的研究

車高峰 陸月然★譚 軍

（百色學(xué)院信息工程學(xué)院，廣西 百色 533000）

利用蟻群運(yùn)動(dòng)的遍歷性、隨機(jī)性和規(guī)律性特點(diǎn)，分析了車輛導(dǎo)航系統(tǒng)路由選擇問題的蟻群優(yōu)化算法，仿真結(jié)果表明該方法是一種簡(jiǎn)單有效的算法。

蟻群優(yōu)化算法；車輛導(dǎo)航系統(tǒng)；路由選擇問題

1 引言

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

2 路由選擇問題的蟻群優(yōu)化算法

路由選擇問題是運(yùn)籌學(xué)、組合優(yōu)化等領(lǐng)域中一個(gè)著名的難題，由于其NP難題性質(zhì)，迄今尚未能徹底解決。目前求解這類問題的主要方法有模擬退火算法[1-2]、遺傳算法[3]、啟發(fā)式搜索法、Hopfield神經(jīng)網(wǎng)絡(luò)算法[4]等。下面簡(jiǎn)單介紹蟻群基本算法。

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

2.1 導(dǎo)航系統(tǒng)選擇下一路段規(guī)則

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

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

2.2 信息更新規(guī)則

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

2.3 車輛導(dǎo)航系統(tǒng)路由蟻群算法的基本步驟

（1）初始化迭代步數(shù)nc←0以及τij和?τij的值,將m輛車隨機(jī)置于n個(gè)地點(diǎn)上；

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

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

（4）按更新方程修改軌跡強(qiáng)度；

（5）nc←nc+1；

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

（7）目前最好解。

3 實(shí)驗(yàn)仿真

參數(shù)設(shè)置：迭代步數(shù)nc≤200；

假設(shè)從出發(fā)地到目的地途經(jīng)31座城市，這31座城市加上出發(fā)地和目的地都是相互連通的，這31座城市分別編號(hào)1，2,3，......,31,它們坐標(biāo)依次定義如下：

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對(duì)以上述蟻群算法進(jìn)行仿真結(jié)果如圖1。

通過算法求得途中這31座城市最優(yōu)路徑為：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。從上圖可以看出當(dāng)算法迭代次數(shù)超過75次后，最優(yōu)路徑長度已經(jīng)基本保持不變了，求得為1.5590e+004。

圖1 最優(yōu)路徑和迭代次數(shù)圖

[1]王凌．智能優(yōu)化算法及其應(yīng)用[M]．北京：清華大學(xué)出版社，2001：195-211．

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

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

[4]張立明．人工神經(jīng)網(wǎng)絡(luò)的模型及其應(yīng)用[M]．上海：復(fù)旦大學(xué)出版社，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

車高峰，男，山東煙臺(tái)人，碩士，講師，研究方向：現(xiàn)場(chǎng)總線技術(shù)、蟻群算法；

*通訊作者：陸月然，男，廣西天等人，碩士，副教授，研究方向：物聯(lián)網(wǎng)。

百色學(xué)院一般科研項(xiàng)目，項(xiàng)目編號(hào)：2014KB06；廣西高校科學(xué)技術(shù)研究項(xiàng)目，項(xiàng)目編號(hào)：KY2015LX388；三亞市院地科技合作項(xiàng)目，項(xiàng)目編號(hào)：2013YD56。