張程程，康維新

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱150001

交通動態(tài)路網(wǎng)模型與能耗最優(yōu)路徑誘導

張程程，康維新

哈爾濱工程大學信息與通信工程學院，黑龍江哈爾濱150001

針對智能交通誘導中出行者路徑選擇以及汽車能耗問題，對路網(wǎng)模型及能耗最優(yōu)路徑進行了研究。在傳統(tǒng)圖論方法基礎上建立動態(tài)路網(wǎng)模型，細化路段和交叉口處的動態(tài)信息，加入交叉口處排隊車輛數(shù)及排隊等待時間;并分別計算路段和交叉口處勻速及怠速時的汽車行駛能耗，進而建立了能耗最優(yōu)路徑誘導模型;再將能耗融入到蟻群算法的信息素更新規(guī)則中，用改進后的蟻群算法進行實驗仿真。仿真結(jié)果驗證了動態(tài)路網(wǎng)模型的有效性，得到的能耗最優(yōu)路徑能夠有效減少行程內(nèi)10%左右的能耗，達到節(jié)能減排的目的，符合實際需求。

智能交通誘導;動態(tài)路網(wǎng)模型;動態(tài)交通信息;能耗最優(yōu)路徑;改進蟻群算法

網(wǎng)絡出版地址: http://www.cnki.net/kcms/detail/23.1191.U.20150727.1031.006.html

交通擁堵、汽車尾氣問題一直都是智能交通的研究重點，怎樣選擇便捷路徑行駛以減少汽車能耗已成為出行者日益關(guān)注的問題。生態(tài)智能交通［1］的提出為交通誘導與節(jié)能減排提供了一個新的發(fā)展方向，能夠有效地降低汽車能耗。

國內(nèi)外學者在有關(guān)交通誘導的路網(wǎng)建模、最優(yōu)路徑以及汽車排放等方面進行了很多的研究。在構(gòu)建路網(wǎng)模型方面，曹政才等［2］建立了以道路為基本元素的RBM模型，但如果交通信息量大則會增加計算量。Demir等［3］構(gòu)建一種聚類超圖模型，并通過把基于節(jié)點的數(shù)據(jù)存儲方式轉(zhuǎn)化為基于路段的數(shù)據(jù)存儲方式，減少路網(wǎng)數(shù)據(jù)的存儲量;宋青等人［4］建立了一個基于小區(qū)的大規(guī)模分層圖論路網(wǎng)模型，提出新型分層路由算法提高了空間搜索精度。文獻［5］將靜態(tài)路網(wǎng)與動態(tài)信息結(jié)合起來建立了動靜態(tài)廣義路網(wǎng)模型。文獻［6］提出了考慮用戶均衡的新型動態(tài)模型，解決靜態(tài)和動態(tài)交通分配問題。以上的路網(wǎng)模型，都把交叉口當作路段的一部分。但是實際上，交叉口處的信息是不可忽略的。在最優(yōu)路徑方面，文獻［7］提出了基于智能優(yōu)化搜索理論和人工免疫系統(tǒng)的最優(yōu)搜索算法，實現(xiàn)路徑誘導。文獻［8］在博弈論基礎上，建立了考慮廣義出行費用的路徑選擇模型。文獻［9-11］針對蟻群算法易陷入局部最優(yōu)解的問題對蟻群算法進行了改進，實現(xiàn)有效的路徑搜索。另外，李世武等［12］從排放角度確定了最佳的信號配時優(yōu)化方案。文獻［13］研究了道路等級以及行車速度對排放的不同影響。由以上研究可以看出，若從路網(wǎng)模型和能耗的角度進行交通誘導路徑尋優(yōu)，對實現(xiàn)交通節(jié)能減排具有重要的現(xiàn)實意義。

文中在傳統(tǒng)圖論的基礎上，構(gòu)建出動態(tài)路網(wǎng)模型，細化交叉口和路段的動態(tài)信息。對交叉口和路段的行駛能耗進行計算并得出能耗最優(yōu)路徑誘導模型，應用改進蟻群算法對模型進行求解，得出能耗最優(yōu)路徑。

1　動態(tài)路網(wǎng)模型的構(gòu)建

1.1動態(tài)交通路網(wǎng)模型

城市交通路網(wǎng)復雜多變，從總體上看，都是由道路交叉口和路段相互連接而成的。可以用圖論法對交通路網(wǎng)進行拓撲化抽象，圖論中的節(jié)點及弧段分別與實際路網(wǎng)的交叉口及路段一一對應，并且對弧段進行賦權(quán)描述。

1.2路網(wǎng)中動態(tài)交通信息

實際路網(wǎng)中，影響交通網(wǎng)絡通行能力的交通因素分別發(fā)生在交叉口和路段上。下面分別對交叉口和路段相關(guān)信息進行描述。

信號交叉口延誤是由于交叉口處信號控制引起交通流間斷而損失的車輛行駛時間，文中以十字交叉路口為例。根據(jù)質(zhì)點排隊模型，當交叉口駛出流量大于出口通行能力時，則在該處將出現(xiàn)點排隊。此處，可以簡化交叉口處的動態(tài)因素，排隊時間的計算僅考慮路口排隊車輛數(shù)，可以更直觀、簡便地反映實際路網(wǎng)，減少計算量。

交叉口排隊延誤時間與排隊車輛數(shù)關(guān)系為

式中: tcross為交叉口排隊延誤時間，T為周期長度，λ為交叉口信綠比，X為交叉口飽和度，Q為交叉口交通量。飽和度X表示為

式(1)中: Qk(t)為t時刻的排隊車輛，veh; Ck(t)為t時刻交叉口最大負荷，veh。

城市交通路段上的動態(tài)因素相對復雜，其中單位時間內(nèi)的交通量表現(xiàn)為動態(tài)性和隨機性;通行能力則為交通規(guī)定運行特征下的最大流量，表現(xiàn)為相對穩(wěn)定性和規(guī)律性;行車速度、車流密度在交通狀態(tài)上也表現(xiàn)出敏感性。下面將對主要的路段動態(tài)信息進行描述。

由交通流理論可知，交通量、速度和密度3個參數(shù)之間的關(guān)系為

式(2)中: Qa(t)為路段的車流量，M為路段車流密度，(t)為路段行車速度。式(3)中: C為路段的通行能力，Vf為自由流行駛時的行車速度，Mmax為最大車流密度。

設定某路段的長度為la，則有

式中t0為自由流狀態(tài)下經(jīng)過路段a的所需的時間。

路段流量與路段行駛所需時間的關(guān)系為

路段的行程時間是影響路徑尋優(yōu)的一個重要指標，而道路的擁堵的判定指標也備受關(guān)注。交通擁堵指數(shù)(traffic performance index，TPI)是北京市首創(chuàng)的綜合反映道路網(wǎng)暢通或擁堵的概念性數(shù)值。TPI分成5個等級，取值用0～10之間的正整數(shù)來表示，數(shù)值越高，擁堵越嚴重。

為了簡化計算，文中在此基礎上簡化了TPI等級，如式(4)所示，路段擁擠程度值為

在進行交通狀態(tài)分析時，可取TPI的不同值來判斷路段的擁擠程度，對交通狀態(tài)進行評價。此外，影響路段通行能力還有另外一個動態(tài)信息，如當遇到修路、雨雪天氣導致的封路時，這個路段就為限行路段，這個路段的耗費可以設置為無窮大。

1.3車輛行駛能耗

城市道路上車輛行駛的能耗分為2部分，主要是在路段上以及交叉口紅綠燈時的能耗。車輛行駛能耗的特點是，車輛從怠速到勻速行駛過程中能耗相對勻速行駛較大。在有信號控制的交叉口上，車輛一般有2種運動狀態(tài):一是車輛到達交叉口時遇到紅燈和擁堵狀態(tài)需要排隊等待時，車輛必須怠速再啟動通過交叉口。二是車輛到達交叉口時信號為綠燈，車輛勻速通過交叉口，其能耗量近似按路段能耗計算。

按照不同車型，能耗率也是不同的，見表1。

表1　不同車型能耗率

文中定義式(5)計算能耗:

式中: qv為油耗率，也可稱作怠速因子; l為路段長度; V為行駛速度。

2　能耗最優(yōu)路徑誘導模型及改進蟻群算法

2.1能耗最優(yōu)路徑誘導模型

交通網(wǎng)絡中最短路徑問題一直都是研究的熱點。但是由于交通信息的不斷變化，最短路徑已經(jīng)不能夠作為最合理路徑的標準。最優(yōu)路徑將從距離最短、時間最少和能耗最短等角度來詮釋。

結(jié)合上述所建立的動態(tài)路網(wǎng)模型，建立了最優(yōu)路徑誘導模型，也可稱作耗費最小模型。設Lmin為車輛最小耗費所經(jīng)過的路徑，rij、ri、rj為所經(jīng)過的路段和交叉口。這是一個組合優(yōu)化問題，可用式(6)的數(shù)學模型來表示:

式中:若最優(yōu)路徑經(jīng)過節(jié)點或路段，則rij、ri、rj取值為1，反之，取0。

根據(jù)車輛行駛的能耗公式，可得出能耗最優(yōu)路徑誘導模型:

式中: Wij為綠燈或路段上的能耗，Wi、Wj為交叉口處紅燈或擁堵時的能耗。同理，當計算距離最短和時間最少路徑時，只需將式(6)中的耗費值改成相應的距離和時間。

2.2改進蟻群算法

蟻群算法作為一種啟發(fā)式算法，常用在智能交通中的路徑誘導方面。它是一種仿生學算法，通過模擬螞蟻覓食的過程，將其應用到路徑搜索過程中，并及時對外界的信息做出響應得到最優(yōu)路徑。影響蟻群算法的核心因素有2個，一個是節(jié)點間轉(zhuǎn)移概率的計算策略，另一個是信息素更新規(guī)則。而傳統(tǒng)蟻群算法在路徑尋優(yōu)過程中，搜索效率低并易陷入局部最優(yōu)，搜索結(jié)果不穩(wěn)定。

為了提高算法效率，使蟻群算法更加適應外界信息的變化，得到最優(yōu)路徑，文中分別在轉(zhuǎn)移概率選擇和信息素更新規(guī)則上進行改進。

在蟻群算法中，β為期望啟發(fā)因子。外界的動態(tài)信息影響螞蟻轉(zhuǎn)移概率中的β，所以這里β不再是一個固定值，它與交通道路的擁堵指數(shù)有關(guān)，令β=TPI，當TPI越小時，道路越暢通，此時螞蟻傾向于選擇信息素濃度較高的地方。設m為蟻群中螞蟻的數(shù)量，τij(t)相鄰2個節(jié)點間的信息素量，為了提高算法的效率，直接去遍歷和節(jié)點i相連接的節(jié)點，這里Vk={和i直接相連的節(jié)點}，則轉(zhuǎn)移概率為

否則式中:α為信息啟發(fā)因子，ηij=1/dij為能見度啟發(fā)因子。

在信息素更新規(guī)則上，螞蟻每走一步后所經(jīng)過的路徑上的信息素要進行揮發(fā)，如式(7)所示。

式中:ρ為信息素的揮發(fā)程度，Δτij(t)為路徑上的信息素增量。局部更新可以有效地避免螞蟻收斂于同一條路徑。

而螞蟻每經(jīng)過一次循環(huán)后時，得到的最優(yōu)解所經(jīng)過的路徑上的信息素要增強，而非最優(yōu)解的路徑上的信息素要減弱。將更新因子引入全局更新中，按照式(8)更新信息素:

式中: G(p)為更新因子，是能耗的函數(shù)，μ為正實數(shù)，表示此路徑的相對重要性，L(p)為能耗估計。若螞蟻所選路徑上的能耗相對較小，則更新好該路徑上信息素將增強，其他螞蟻選擇此路徑的幾率相對增大。通過上述更新后的信息素不僅可以反映各路徑和節(jié)點的權(quán)值變化，也反映出最優(yōu)路徑的選擇情況。

算法的具體步驟如下。

1)初始化各路徑上的信息素都為一常數(shù);螞蟻數(shù)目為m;并將m只螞蟻放在起點處。

2)在t時刻每只螞蟻按式(6)所示的轉(zhuǎn)移概率選擇下一節(jié)點。

3)到達下一節(jié)點后，用式(7)進行信息素的局部更新。

4)判斷節(jié)點j是否為目的節(jié)點，若為目的節(jié)點則保存螞蟻走過的路徑。若不是目的節(jié)點，則返回步驟2)。

5)當m只螞蟻全部迭代完后，則將各路徑上的信息素按式(8)進行全局更新。并將每只螞蟻搜索到的最優(yōu)路徑進行比較，得出全局最優(yōu)路徑。

3　仿真實驗

城市路網(wǎng)建設錯綜復雜，文中借助VS2010軟件平臺，對真實道路網(wǎng)應用改進的圖論模型進行網(wǎng)格化抽象。圖1為仿真路網(wǎng)環(huán)境，其中黑色節(jié)點部分為交叉口，連接節(jié)點之間的連線為路段，每條路段間距離不同，示意圖中標注了相應靜態(tài)距離。下面將從能耗角度對最優(yōu)路徑進行模擬驗證。首先進行初始化設置，設上路車輛均為小轎車，標準乘載，能耗率qv為0.23 mL·s－1，假設此時的路網(wǎng)正處于早高峰時段，局部車流相對緩慢，交通狀況實時變化。此時在路口n5、n7處出現(xiàn)輕微擁堵;在n11、n22交叉口處排隊車輛數(shù)較多，車行緩慢;其他路段相對較暢通。此時，車輛以n1為起點，終點為n19。

圖1　仿真路網(wǎng)示意

算法的參數(shù)設置為:車輛數(shù)量m=30;量子位數(shù)為2;概率參數(shù)q0=0.5;揮發(fā)系數(shù)ρ=0.7;α=0.5; β=0.5;最大迭代次數(shù)為400。在動態(tài)路網(wǎng)下應用改進后路徑尋優(yōu)算法得出的路徑為n1－n2－n6－n10－n14－n18－n19，行車距離為19.5 km，能耗為0.49 L。而在靜態(tài)路網(wǎng)下，車輛選擇的是距離最短路徑為n1－n5－n9－n10－n11－n15－n19，雖然走過路程為18.5 km，但是由于路口擁堵而造成等待時間延長，耗油量為0.55 L。路徑仿真結(jié)果如圖2。

圖2　路徑仿真結(jié)果

選擇2組起點終點，在靜態(tài)和動態(tài)路網(wǎng)下有不同路徑，具體數(shù)據(jù)見表2、3。

表2　不同起終點的能耗最優(yōu)路徑

表3　不同路徑的能耗量對比

分析上面的路徑表可知，盡管在靜態(tài)路網(wǎng)下能使行駛距離減少，但是卻在行駛過程中增加了等待時間，增大了能耗，靜態(tài)路網(wǎng)不能及時的對路網(wǎng)上的動態(tài)信息做出及時響應。而在動態(tài)路網(wǎng)中，距離不一定最短，但能夠避開交叉口擁堵，減少了行程內(nèi)怠速等待，根據(jù)表3所示，在動態(tài)路網(wǎng)下的能耗相對減少，比較符合出行者的需求。圖3為改進蟻群算法下能耗最優(yōu)解收斂圖，在圖中可以看出，未改進的蟻群算法在搜索過程中易出現(xiàn)早熟現(xiàn)象，收斂速度也較慢，未搜索到全局最優(yōu)解。而改進蟻群算法可以有效避免局部最優(yōu)現(xiàn)象的出現(xiàn)，提高了收斂速度。

圖3　改進蟻群算法下的能耗最優(yōu)解收斂

4　結(jié)束語

文中針對實時變化的交通路況，在圖論基礎上建立的動態(tài)路網(wǎng)模型綜合考慮了交叉口和路段的動態(tài)信息，進而推導出能耗最優(yōu)路徑誘導模型;再針對螞蟻狀態(tài)轉(zhuǎn)移概率和信息素更新規(guī)則方面對蟻群算法進行改進，改進后的蟻群算法可以有效地避免局部最優(yōu)解，提高了算法的效率;由不同起終點得出的能耗最優(yōu)路徑可以有效地節(jié)省能耗，符合實際需求;也為今后研究交通誘導中的系統(tǒng)綜合最優(yōu)提供了基礎，具有現(xiàn)實意義。

［1］朱昊，陶晨亮，趙方.發(fā)展生態(tài)型智能交通系統(tǒng)的建議［J］.交通與運輸，2013，29(3) : 21-22.

［2］曹政才，韓丁富，喬非.基于新型路網(wǎng)模型的路徑尋優(yōu)方法研究［J］.電子學報，2012，40(4) : 756-761.

［3］DEMIR E，AYKANAT C，CAMBAZOGLU B B.A linkbased storage scheme for efficient aggregate query processing on clustered road networks［J］.Information Systems，2010，35(1) : 75-93.

［4］SONG Qing，WANG Xiaofan.Efficient routing on large road networks using hierarchical communities［J］.IEEE Transactions on Intelligent Transportation Systems，2011(12) : 132-140.

［5］YANG Yuhong，HAN Xiaowei，YUAN Zhonghu.A model of dynamic traffic road network［J］.IERI Procedia，2012 (13) : 46-51.

［6］JIN Wenlong.A dynamical system model of the traffic assignment problem［J］.Transportation Research Part B，2006，41 (1) : 32-48.

［7］YANG Licai，LIN Jie，WANG Dewei，et al.Dynamic route guidance algorithm based on artificial immune system［J］.Journal Of Control Theory and Applications，2007，5 (4) : 385-390.

［8］FENG Yuqin，LENG Junqiang，XIE Zhongyu，et al.Route choice model considering generalized travel cost based on game theory［J］.Mathematical Problems in Engineering，2013(1) : 1-5.

［9］LIU Zhishuo.SHEN Jinsheng，CHAI Yueting.Hybrid multiple ant colonies algorithm for capacitated vehicle routing problem［J］.Journal of System Simulation，2007，19(15) : 3513-3520.

［10］SONG Jinjuan，BAI Yanping.An improved ant colony algorithm and its application in optimal routing problem［J］.Journal of Measurement Science and Instrumentation，2013，4(1) : 23-29.

［11］GAN Rongwei，GUO Qingshun，CHANG Huiyou，et al.Improved ant colony optimization algorithm for the traveling salesman problems［J］.Journal of Systems Engineering and Electronics，2010(2) : 329-333.

［12］李世武，王云鵬，付建萍，等.基于車輛排放的城市道路交叉口信號配時優(yōu)化仿真［J］.吉林大學學報:工學版，2007，37(6) : 1268-1272.

［13］王云鵬，郭棟，隗海林，等.城市分等級道路車輛運行速度對排放的影響［J］.哈爾濱工業(yè)大學學報，2009，41 (7) : 110-114.

Traffic dynamic road network model and energy consumption optimal route guidance

ZHANG Chengcheng，KANG Weixin

College of Information and Communication Engineering，Harbin Engineering University，Harbin150001，China

To solve the problem of the traveler route choice and energy consumption in intelligent traffic route guidance，a dynamic road network model was established based on the traditional graph theory methods.This model described the dynamic information of road segments and intersections，with the relationship between the number of queuing vehicles and the queue waiting time.The energy consumptions of vehicles moving at even and idle speed on the roads and intersections was calculated，respectively.Then the energy consumption optimal route guidance model was suggested，and the energy consumption was integrated to the pheromone updating rule of an ant colony algorithm; then simulation was carried out by the improved ant colony algorithm.The simulation results show that the dynamic road network model is effective.In addition，the derived optimum route of energy consumption can effectively reduce the vehicle energy consumption in the travel，which saves about 10% energy compared with the static road network.

intelligent traffic guidance; dynamic road network model; dynamic traffic information; energy consumption optimal route; improved ant colony algorithm

TP301.6

A

1009-671X(2015) 04-043-05

10.3969/j.issn.1009-671X.201412001

2014-12-01.網(wǎng)絡出版日期: 2015-07-27.

黑龍江省交通運輸資助項目(G084812068).

張程程(1987-)，女，碩士研究生;康維新(1963-)，男，教授，博士.

康維新，E-mail: kangweixin@hrbeu.edu.cn.