張繼榮,袁曉潔

(西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710061)

?

基于改進(jìn)蟻群算法的交通最優(yōu)路徑方法研究

張繼榮,袁曉潔

(西安郵電大學(xué) 通信與信息工程學(xué)院，西安 710061)

針對日益復(fù)雜的交通網(wǎng)絡(luò)，提出了一種基于改進(jìn)蟻群算法的交通路徑最優(yōu)方法，首先根據(jù)圖論的思想構(gòu)建了城市交通網(wǎng)絡(luò)模型，結(jié)合層次分析法考慮了道路長度、交叉口停滯、交通擁擠、道路容量、天氣狀況等5個(gè)主要因素；然后在MATLAB平臺下，采用改進(jìn)的蟻群算法對靜態(tài)交通網(wǎng)絡(luò)和動(dòng)態(tài)交通網(wǎng)絡(luò)分別進(jìn)行最短路徑的求解，最后進(jìn)行了對比分析；研究結(jié)果表明，在綜合考慮以上5種因素的情況下，動(dòng)態(tài)交通網(wǎng)絡(luò)下的路徑最優(yōu)算法能為出行者找到更準(zhǔn)確更便捷的路線。

蟻群算法；動(dòng)態(tài)交通；路徑最優(yōu)

0 引言

隨著社會(huì)的發(fā)展、生活節(jié)奏的加快，小轎車的使用越來越普遍。這固然提高了人們的出行效率，但由此也引發(fā)了諸如交通擁堵、環(huán)境污染等一系列問題。作為一名駕駛員，希望選擇一條距離最短，用時(shí)最少的道路。但一條路徑的好壞不僅取決于道路長短，還取決于道路容量、天氣狀況、交通堵塞等動(dòng)態(tài)因素。因此，如何在復(fù)雜的交通網(wǎng)絡(luò)中找出一條實(shí)時(shí)、有效的路徑，是當(dāng)下人們極為關(guān)注的問題。

國內(nèi)外關(guān)于最短路徑選擇算法的研究成果有很多，目前常用的算法主要有：Dijkstra算法、Bellman-Ford算法和蟻群算法等[1]。蟻群算法是一種經(jīng)典的路徑優(yōu)化算法，由于具有較強(qiáng)的魯棒性和發(fā)現(xiàn)較好解的能力[2]，已經(jīng)先后應(yīng)用于調(diào)度問題、旅行商問題。Gambardella等[3]提出了雙蟻群系統(tǒng)求解車輛路徑問題，兩個(gè)蟻群依靠獨(dú)立的信息素分別優(yōu)化兩個(gè)目標(biāo)函數(shù)，并通過共享最優(yōu)路徑來交換信息。RongweiGan[4]和QingshunGuo[4]提出用改進(jìn)的蟻群算法來解決旅行商問題，將螞蟻分成兩組，并通過優(yōu)化搜索方式來達(dá)到路徑尋優(yōu)的目的。

但是，很多學(xué)者主要利用蟻群算法對如何尋得最優(yōu)路徑進(jìn)行了理論研究，卻很少有學(xué)者用它解決現(xiàn)實(shí)生活中的交通路徑選擇問題[5]。本文針對蟻群算法搜索效率低下、易陷入局部最優(yōu)解[6]等缺陷，采用改進(jìn)的蟻群算法，致力于找出一種最短路徑尋優(yōu)方法，在考慮諸多動(dòng)態(tài)因素的情況下，使出行者找到一條快速到達(dá)目的地的最優(yōu)路徑，不僅節(jié)約時(shí)間、降低交通壓力，而且減少污染。

1 構(gòu)建交通網(wǎng)絡(luò)模型

在實(shí)際情況下，交通網(wǎng)絡(luò)錯(cuò)綜復(fù)雜，要將交通路網(wǎng)抽象成圖的形式以便進(jìn)行研究，這個(gè)抽象的過程十分重要。

下面從西安市的地圖上截取一段平面圖，將交叉路口抽象為節(jié)點(diǎn)，將節(jié)點(diǎn)之間的路段抽象成邊，并對每個(gè)節(jié)點(diǎn)進(jìn)行編號，節(jié)點(diǎn)之間的距離取實(shí)際距離。則整個(gè)路網(wǎng)模型用賦值的有向圖T=(G,F,W,R)來描述，其中：G={ni|i=1,2,…,n}是節(jié)點(diǎn)集合，如圖1中節(jié)點(diǎn)1到節(jié)點(diǎn)19；F={f|i,j,k=1,2,…,n,且i≠j≠k}是路徑的點(diǎn)權(quán)集合，代表節(jié)點(diǎn)i經(jīng)節(jié)點(diǎn)j到節(jié)點(diǎn)k時(shí)在節(jié)點(diǎn)j的延誤；W={w|i,j=1,2,…,n}是節(jié)點(diǎn)ni和節(jié)點(diǎn)nj之間路徑權(quán)值的集合，與該路段的路徑長度、通行能力以及不同時(shí)段的交通狀況有關(guān)；R={r|i,j= 1,2,…,n,且i≠j}是網(wǎng)絡(luò)中所有路段的集合，它具有方向性，如r和r表示路段方向相反。構(gòu)建的交通網(wǎng)絡(luò)模型如圖1所示。

圖1 交通網(wǎng)絡(luò)模型

建立交通網(wǎng)絡(luò)模型以后，其最優(yōu)路徑求解問題就等價(jià)于從圖T=(G,R,W,F)中搜索兩個(gè)特定節(jié)點(diǎn)之間的權(quán)值最小路徑問題。

2 蟻群算法及改進(jìn)

2.1 傳統(tǒng)的蟻群算法

蟻群算法[2]是一種基于種群的啟發(fā)式仿生進(jìn)化算法，最初是用來解決TSP(Traveling Salesman Problem)問題的。其過程可以描述如下：首先，將m只螞蟻隨機(jī)的放到n個(gè)網(wǎng)絡(luò)模型節(jié)點(diǎn)上，并使用禁忌表(tabuk)來記錄螞蟻k訪問過的節(jié)點(diǎn)。設(shè)置每只螞蟻禁忌表的第一個(gè)元素為當(dāng)前所在節(jié)點(diǎn)，此時(shí)，各路徑上的信息素量相等；其次，每只螞蟻獨(dú)立選擇下一節(jié)點(diǎn)，且螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率[2]為：

(1)

式中，Jk(i)={1,2,…,n}-tabuk是螞蟻k下一步可選節(jié)點(diǎn)的集合；ηij(t)是啟發(fā)式因子，表示從節(jié)點(diǎn)i到節(jié)點(diǎn)j的期望強(qiáng)度，值為兩節(jié)點(diǎn)之間距離的倒數(shù)；α，β是權(quán)衡因子，決定了信息素和啟發(fā)式信息的相對影響力。

最后，當(dāng)節(jié)點(diǎn)上的所有螞蟻都完成一次周游后，各路徑上的信息素會(huì)按以下兩式[7]進(jìn)行實(shí)時(shí)更新：

(2)

(3)

(4)

式中，Lk表示第k只螞蟻遍歷所有節(jié)點(diǎn)所走的長度，Q表示一個(gè)正常數(shù)。

2.2 算法存在的問題及改進(jìn)

蟻群算法在尋找最優(yōu)路徑方面的優(yōu)勢毋庸置疑，但傳統(tǒng)的蟻群算法同時(shí)也存在一些缺陷，具體主要表現(xiàn)在兩個(gè)方面：

1)蟻群算法在最優(yōu)路徑搜索過程中缺少方向性的引導(dǎo)信息，這會(huì)直接降低搜索效率。

2)容易陷入局部最優(yōu)解。由于算法存在信息素的正反饋?zhàn)饔?，?dǎo)致經(jīng)過若干次的搜索循環(huán)以后，局部最優(yōu)解產(chǎn)生的信息素濃度增加，造成所有的螞蟻個(gè)體都趨向于這一個(gè)局部最優(yōu)解，從而陷入局部最優(yōu)。

針對以上兩個(gè)缺陷，本文做出了相應(yīng)的改進(jìn)。

1)啟發(fā)式因子ηij(t)的改進(jìn)。

(5)

式中，wij表示弧的權(quán)值系數(shù)；θijt是方位角，由節(jié)點(diǎn)ij和終點(diǎn)t所組成，是關(guān)鍵性的路徑方向引導(dǎo)信息?？梢钥闯?，啟發(fā)式因子與兩個(gè)參數(shù)是反比關(guān)系，wij和θijt的值越小，ηij(t)的值越大。提高ηij(t)的值，就能使路徑搜索方向優(yōu)先指向終點(diǎn)，從而提高算法的收斂速度。

2)給信息素設(shè)定門限。

在算法初始時(shí)刻，給每條路徑上的信息素都先設(shè)定兩個(gè)門限值τmax(較大常數(shù))，τmin(較小常數(shù))。這樣，信息素更新對路徑信息素含量的影響降到了最低，螞蟻也有了更大的搜索空間。為保證向最優(yōu)方向收斂，每進(jìn)行一次循環(huán)，都只對得出最優(yōu)解的螞蟻?zhàn)哌^的路徑進(jìn)行更新，其他路徑不更新。則信息素的值可以表示為：

(6)

2.3 改進(jìn)算法步驟

1)參數(shù)初始化。設(shè)定N=0(N為螞蟻迭代次數(shù))，信息素τij=0，將m只螞蟻隨機(jī)擺放到初始點(diǎn)上[8]。

2)設(shè)置禁忌表。令禁忌表的第一個(gè)元素為k= 1，螞蟻數(shù)量的變化為k=k+1。

3)實(shí)現(xiàn)螞蟻移動(dòng)。按公式(1)、(5)計(jì)算轉(zhuǎn)移概率，概率值決定了螞蟻移動(dòng)的方向。

4)修改禁忌表。當(dāng)螞蟻從節(jié)點(diǎn)i到達(dá)節(jié)點(diǎn)j時(shí)，更新其信息素并修改禁忌表，同時(shí)將新節(jié)點(diǎn)j置于禁忌表tabuk中。

5)重復(fù)執(zhí)行以上4個(gè)步驟。直到每只螞蟻都遍歷完集合中的所有節(jié)點(diǎn)，終止循環(huán)。

6)對螞蟻找到的每一條最優(yōu)路徑，按公式(2)、(3)、(4)、(6)進(jìn)行信息素更新。

7)確定最優(yōu)路徑。從眾多新生成的可行解中找到一條最短路徑，即為本次迭代的最優(yōu)路徑。

8)重復(fù)執(zhí)行以上步驟。若直到連續(xù)多次循環(huán)迭代沒有出現(xiàn)更優(yōu)解，則停止運(yùn)算，輸出當(dāng)前值作為最優(yōu)解；否則清空禁忌表，跳轉(zhuǎn)到第2)步執(zhí)行。

3 道路網(wǎng)各因素的權(quán)值

3.1 層次分析法

層次分析法(Analytic Hierarchy Process, AHP)，是計(jì)算道路權(quán)重的關(guān)鍵方法。它將定性和定量相結(jié)合[9]，根據(jù)各個(gè)因素相互聯(lián)系的有序?qū)哟?，對每層的各因素進(jìn)行直觀判斷，然后做出相對定量的表示，最后建立數(shù)學(xué)模型。

3.2 路況影響因素

使用層次分析法之前，需要列出影響交通路況的各個(gè)因素，本文主要考慮五種因子：

(1)路徑長度。即靜態(tài)距離，其值為實(shí)際長度，交通路網(wǎng)模型已經(jīng)給出。

(2)交叉口停滯。交叉口設(shè)立了紅綠燈，斑馬線人流通行密集，部分車輛還會(huì)轉(zhuǎn)向，很容易發(fā)生交通事故。因此，交叉口是最容易發(fā)生時(shí)間延誤的地方。

(3)交通擁擠度。它反映交通的繁忙程度，與速度、行車密度、交通量等緊密相關(guān)。

(4)道路容量。道路容量是指單位時(shí)間內(nèi)可以通行的最大車流量，它與道路等級息息相關(guān)。

(5)天氣狀況。這是一個(gè)很隨機(jī)的因素，晴空萬里時(shí)，人們都能夠正常出行。但偶爾也會(huì)遇到濃霧、暴雨、大雪等天氣，一旦出現(xiàn)就直接影響行車安全以及出行效率。

3.3 判斷矩陣和各因素的路徑權(quán)值

由于各因素的權(quán)重不僅僅只是定性的表示，還要有定量的結(jié)合。所以，Saaty等人提出了一致矩陣法，即不把所有因素都放在一起比較，而是兩兩進(jìn)行比較[10]。這種方法，以計(jì)算相對尺度的形式，減少了性質(zhì)不同的諸因素之間相互比較的困難，使準(zhǔn)確度大大提高。

判斷矩陣表示本層中所有因素(指5種路況因素)與目標(biāo)層(指路徑選擇)的相對重要性的比較。判斷矩陣的元素αij用Saaty的1-9標(biāo)度方法給出，本文只考慮5個(gè)因素，其中A1、A2、A3、A4、A5分別代表路徑長度、交叉口停滯、交通擁擠度、道路容量、天氣狀況。判斷矩陣的標(biāo)度及含義如表1所示。

表1 判斷矩陣的標(biāo)度及含義

依據(jù)交通規(guī)劃中各評價(jià)指標(biāo)的重要程度[11]，經(jīng)過現(xiàn)場調(diào)研，并通過咨詢專家意見，在全面了解西安市交通運(yùn)輸質(zhì)量評價(jià)指標(biāo)的基礎(chǔ)上，得出的判斷矩陣如表2所示。

表2 判斷矩陣

于是，可以得到判斷矩陣Aij：

經(jīng)過歸一化計(jì)算，得到權(quán)向量為：w=(0.150 6,0.252 2,0.422 4,0.0102,0.072 8)T)。同時(shí)，求得矩陣的最大特征根為λmax=5.02,也即λmax>n(n為判斷矩陣階數(shù))，滿足一致性檢驗(yàn)要求。

3.4 路徑權(quán)重的確定

基于以上計(jì)算，已經(jīng)知道5種路況因子的權(quán)向量，就可以計(jì)算整個(gè)網(wǎng)絡(luò)中各條路徑的權(quán)重值W，方法如下[12]：

(7)

式中，w1～w5是各動(dòng)態(tài)因子的權(quán)值向量，由判斷矩陣已經(jīng)得出結(jié)果；s是路徑距離，v是道路平均時(shí)速，s/v是路徑參量，可以根據(jù)路網(wǎng)模型設(shè)定；m是交叉口停滯參量，根據(jù)延誤時(shí)間由短到長，可劃分為[0.2，0.4，0.6，0.8，1.0]幾個(gè)等級；n是交通擁擠程度的權(quán)值參數(shù)，按照擁擠程度不同，交通狀態(tài)和權(quán)值系數(shù)可分別表示為非常暢通狀態(tài)(0≤M<0.2)、標(biāo)準(zhǔn)暢通狀態(tài)(0.2≤M<0.4)、輕微擁堵狀態(tài)(0.4≤M<0.6)、擁堵狀態(tài)(0.6≤M<0.8)、嚴(yán)重?fù)矶聽顟B(tài)(0.8≤M<1.0)等五種情況[13]；p是道路容量的參數(shù)，根據(jù)道路等級，要在[0,1]區(qū)間內(nèi)賦值；q是天氣狀況參量，可用0表示天氣晴朗，0.2表示小雨，0.4表示大雨，0.6表示霧天，0.8表示雪天。

3.5 靜態(tài)和動(dòng)態(tài)路徑距離求解

取交通網(wǎng)絡(luò)抽象圖的前10個(gè)節(jié)點(diǎn)，并設(shè)置節(jié)點(diǎn)1為起點(diǎn)，節(jié)點(diǎn)10為終點(diǎn)。設(shè)定天氣狀況為晴朗，即權(quán)值系數(shù)為0。則各個(gè)動(dòng)態(tài)因子的取值情況以及根據(jù)各個(gè)因子求出的靜態(tài)距離(sd)、動(dòng)態(tài)距離(dd)如表3所示：

表3 靜態(tài)和動(dòng)態(tài)距離求解情況

4 算法仿真

根據(jù)前面表格里得到的每條道路的權(quán)重值，基于改進(jìn)的蟻群算法，將程序在Windows7環(huán)境下通過運(yùn)行MATLAB7.0進(jìn)行仿真，并設(shè)置循環(huán)次數(shù)為30次。得到靜態(tài)和動(dòng)態(tài)條件下最優(yōu)距離的仿真圖分別如圖2、圖3所示。

由仿真結(jié)果可以得出最優(yōu)解的情況，如表4所示。

表4 最優(yōu)解情況

圖2 靜態(tài)最優(yōu)距離

圖3 動(dòng)態(tài)最優(yōu)距離

由表4可以看出，靜態(tài)條件下選擇的最優(yōu)路徑1-4-5-6-10，在綜合考慮了幾種動(dòng)態(tài)因素之后，距離變成了99.2，比動(dòng)態(tài)選擇的最優(yōu)路徑1-4-8-9-10多出了32.4的距離，兩者之間的差距還是很大的。

5 結(jié)束語

本文在改進(jìn)的蟻群算法基礎(chǔ)上，結(jié)合層次分析法加入了幾種路況動(dòng)態(tài)因子，并在MATLAB平臺下對靜態(tài)和動(dòng)態(tài)路況分別進(jìn)行了仿真。仿真結(jié)果表明，在綜合考慮各種路況因子的情況下，動(dòng)態(tài)規(guī)劃出來的最優(yōu)路徑能為出行者找到更快更便捷的路線。

[1] 王一松.基于實(shí)時(shí)交通信息的最優(yōu)路徑規(guī)劃算法的研究與實(shí)現(xiàn)[D].上海：東華大學(xué),2013.

[2] 趙燕偉,張景玲,王萬良.物流配送的車輛路徑優(yōu)化方法[M].北京:科學(xué)出版社,2014.

[3] Gambardella L M,TaillardE,Agazzi G.MACS- VRPTW:A multiple ant colony system for vehicle routing problems with time windows[J].New Ideas in Optimization,1999:63-76.

[4] Gan R W,Guo Q S.Improved ant colony optimization algorithm for the traveling salesman problems[J].Journal of System Engineering and Electronics,2010,21(2):329-333.

[5] 楊浩雄,王 丹,張敬蕤.基于蟻群算法的擁堵交通最短路徑研究[J].計(jì)算機(jī)仿真,2015(3):186-191.

[6] 陳迎欣.基于改進(jìn)蟻群算法的車輛路徑優(yōu)化問題研究[J].計(jì)算機(jī)應(yīng)用研究,2012(6):2031-2034.

[7] 張志協(xié),曹 陽.基于改進(jìn)型蟻群算法的最優(yōu)路徑問題求解[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2012(10):76-80.

[8] 夏蘭.基于蟻群算法的交通地理最佳路徑的研究[D].武漢：武漢理工大學(xué),2009.

[9] 張炳江.層次分析法及其應(yīng)用案例[M].北京:電子工業(yè)出版社,2014.

[10] 邊學(xué)叢,朱 嬋,何衍興.引入路徑權(quán)重蟻群算法在應(yīng)急救援中的應(yīng)用[J].工業(yè)安全與環(huán)保,2010(11):60-62.

[11] 李彬何,寧韋昌.大城市客運(yùn)交通方式的綜合分析模型與應(yīng)用[J]. 重慶交通學(xué)院學(xué)報(bào),1997(2):67-72.

[12] 王 洪.基于MATLAB的應(yīng)急救援最優(yōu)路徑選擇[J].工業(yè)安全與環(huán)保,2009,35(1)：48-50.

[13] 陳智宏.基于動(dòng)態(tài)車輛導(dǎo)航系統(tǒng)的道路權(quán)重賦值方法研究[D].北京：北京工業(yè)大學(xué),2006.

Research of Traffic Optimal Path Method Based onImproved Ant Colony Algorithm

Zhang Jirong，Yuan Xiaojie

(Communication and Information Engineering Institute, Xi′an University of Posts and Telecommunications,Xi′an 710061,China)

In view of the increasingly complex traffic networks,this paper proposes a traffic path optimal method based on improved ant colony algorithm, according to the idea of graph theory, first constructed the urban traffic network model, and combined with analytic hierarchy process to consider the road length, the stagnation of intersection, traffic congestion, road capacity and weather conditions, five main dynamic factors. Then, in the MATLAB platform, using the improved ant colony algorithm to solve the shortest path for static traffic and dynamic traffic networks respectively,finally has carried on the comparison and analysis.The research results show that under the influence of all kinds of traffic information, dynamic traffic network under the path optimization algorithm to find more accurate and more convenient route for travelers.

ant colony algorithm; dynamic traffic; optimal path

2015-12-02；

2015-12-31。

張繼榮(1963-)，女，遼寧沈陽市人，教授，碩士生導(dǎo)師，主要從事現(xiàn)代通信網(wǎng)方向的研究。

1671-4598(2016)06-0271-03

10.16526/j.cnki.11-4762/tp.2016.06.074

U491

A