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

張程程，康維新

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

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

張程程，康維新

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

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

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

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

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

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

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

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

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

城市交通路網(wǎng)復(fù)雜多變，從總體上看，都是由道路交叉口和路段相互連接而成的?？梢杂脠D論法對(duì)交通路網(wǎng)進(jìn)行拓?fù)浠橄螅瑘D論中的節(jié)點(diǎn)及弧段分別與實(shí)際路網(wǎng)的交叉口及路段一一對(duì)應(yīng)，并且對(duì)弧段進(jìn)行賦權(quán)描述。

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

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

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

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

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

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

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

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

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

設(shè)定某路段的長度為la，則有

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

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

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

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

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

1.3車輛行駛能耗

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

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

表1　不同車型能耗率

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

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

2　能耗最優(yōu)路徑誘導(dǎo)模型及改進(jìn)蟻群算法

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

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

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

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

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

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

2.2改進(jìn)蟻群算法

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

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

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

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

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

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

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

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

算法的具體步驟如下。

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

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

3)到達(dá)下一節(jié)點(diǎn)后，用式(7)進(jìn)行信息素的局部更新。

4)判斷節(jié)點(diǎn)j是否為目的節(jié)點(diǎn)，若為目的節(jié)點(diǎn)則保存螞蟻?zhàn)哌^的路徑。若不是目的節(jié)點(diǎn)，則返回步驟2)。

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

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

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

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

算法的參數(shù)設(shè)置為:車輛數(shù)量m=30;量子位數(shù)為2;概率參數(shù)q0=0.5;揮發(fā)系數(shù)ρ=0.7;α=0.5; β=0.5;最大迭代次數(shù)為400。在動(dòng)態(tài)路網(wǎng)下應(yīng)用改進(jìn)后路徑尋優(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，但是由于路口擁堵而造成等待時(shí)間延長，耗油量為0.55 L。路徑仿真結(jié)果如圖2。

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

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

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

表3　不同路徑的能耗量對(duì)比

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

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

4　結(jié)束語

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

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

［2］曹政才，韓丁富，喬非.基于新型路網(wǎng)模型的路徑尋優(yōu)方法研究［J］.電子學(xué)報(bào)，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］李世武，王云鵬，付建萍，等.基于車輛排放的城市道路交叉口信號(hào)配時(shí)優(yōu)化仿真［J］.吉林大學(xué)學(xué)報(bào):工學(xué)版，2007，37(6) : 1268-1272.

［13］王云鵬，郭棟，隗海林，等.城市分等級(jí)道路車輛運(yùn)行速度對(duì)排放的影響［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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)絡(luò)出版日期: 2015-07-27.

黑龍江省交通運(yùn)輸資助項(xiàng)目(G084812068).

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

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