城市交通網(wǎng)絡(luò)單向擁堵分流算法的設(shè)計(jì)與實(shí)現(xiàn)

唐俊勇郝海燕

（1.西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710032；2.咸陽師范學(xué)院物理與電子工程學(xué)院，陜西 咸陽 712000）

城市交通網(wǎng)絡(luò)單向擁堵分流算法的設(shè)計(jì)與實(shí)現(xiàn)

唐俊勇1郝海燕2

（1.西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，陜西 西安 710032；2.咸陽師范學(xué)院物理與電子工程學(xué)院，陜西 咸陽 712000）

城市交通流的信息具有實(shí)時性特點(diǎn)，傳統(tǒng)道路擁堵的預(yù)報(bào)都是在堵塞事件發(fā)生后進(jìn)行發(fā)布，擇路分流也是憑著駕駛?cè)藛T的經(jīng)驗(yàn)，準(zhǔn)確率很低。文章提出一種實(shí)時計(jì)算道路信息流并選擇最優(yōu)道路進(jìn)行分流的算法，具有實(shí)時性、智能化高的特點(diǎn)。該算法設(shè)計(jì)了一個五維向量作為輸入信息，采用向量組優(yōu)先級比較的方法，通過對道路端口計(jì)算來生成最優(yōu)化路徑。文章最后給出一個實(shí)際計(jì)算實(shí)例，擁堵分流算法生成其他最優(yōu)備選道路，從而有效的實(shí)現(xiàn)了擁堵分流，使城市交通性能得到優(yōu)化。

城市交通；擁堵分流；向量優(yōu)先級

隨著城市交通網(wǎng)絡(luò)的建設(shè)和應(yīng)用，城市交通道路越來越多地連接城市不同的地點(diǎn)。城市交通網(wǎng)的特點(diǎn)是冗余性設(shè)計(jì)被采用，即通過多條鏈路連接同一地點(diǎn)形成網(wǎng)絡(luò)環(huán)路，確保某條鏈路擁堵后城市交通網(wǎng)絡(luò)仍能保持通暢。這些冗余鏈路對交通管理帶來一個新問題，即當(dāng)某條或者若干條城市交通鏈路發(fā)生擁堵，如何選擇若干條交通量最小，或者通行效率最優(yōu)的道路來連接整個城市，即能保證城市正常的交通運(yùn)力，又能緩解擁堵路段的壓力進(jìn)行分流，有效提高了道路運(yùn)行效率。

1 擁堵分流算法

1.1算法概述

本算法的思想就是要在整個城市中形成連接到各個地點(diǎn)的樹形道路，各個地點(diǎn)的道路連接點(diǎn)處（道路匯聚點(diǎn)）通過交通流量采集設(shè)備獲得道路流量信息，道路匯聚點(diǎn)通過信息數(shù)據(jù)包（IDU）的交換來進(jìn)行計(jì)算，選定城市交通網(wǎng)中的根匯聚點(diǎn)（Root Convergence Point）和指定匯聚點(diǎn)（Designated Convergence Point），確定道路端口的角色是根端口（Root Port）、指定端口（Designated Port）或者備用端口（alternate Port）。經(jīng)過計(jì)算后，生成了一個無環(huán)路的“樹”型交通通行率最小的道路結(jié)構(gòu)。

1.2算法信息數(shù)據(jù)單元（IDU）的構(gòu)成

城市交通網(wǎng)絡(luò)內(nèi)各個道路匯聚點(diǎn)（Convergence Point）根據(jù)每個道路端口優(yōu)先級向量決定每個道路端口角色。這些角色分別為：root port, designated port, alternate port, alternate1port。

（1）城市交通網(wǎng)絡(luò)中匯聚點(diǎn)不是根匯聚點(diǎn)，且該匯聚點(diǎn)的某個端口優(yōu)先向量來源于根匯聚點(diǎn)，那么該端口是根 端口（root port）。

（2）道路路徑端口優(yōu)先向量來源于指定向量，則該端口是交通網(wǎng)絡(luò)中的道路指定端口（designated port）。

（3）城市交通網(wǎng)中，除了根端口外，匯聚點(diǎn)某個端口的端口優(yōu)先向量是從其他匯聚點(diǎn)接收來的，該端口是替代端口（alternated port）。

1.3向量組優(yōu)先級比較

每個道路端口將參與運(yùn)算的關(guān)鍵參數(shù)字段構(gòu)成一個五維向量：

{Root Convergence Point, Root Path Cost, Designated Convergence Point, Designated Port,RcvPort }，匯聚點(diǎn)各個道路端口通過比較彼此交換的IDU包中的五元向量組進(jìn)行優(yōu)先級確定，優(yōu)先級比較順序是從左至右，如果靠前的向量值小，則表明為優(yōu)先向量組。五維向量組的比較過程如下：

（1）計(jì)算Root Convergence Point：在道路交通網(wǎng)絡(luò)中各個匯聚點(diǎn)首先推舉一個匯聚點(diǎn)作為樹形道路的根匯聚點(diǎn)，推舉依據(jù)是各個匯聚點(diǎn)的優(yōu)先值，優(yōu)先值的選擇根據(jù)匯聚點(diǎn)在城市交通中重要程度和設(shè)計(jì)標(biāo)準(zhǔn)選擇，值范圍為[0，1]，計(jì)算公式如①所示：

Root Convergence Point =

Priority（Convergence Point {n}） ①

（2）計(jì)算累積擁堵因子Root Path Cost：如果匯聚點(diǎn)本身是根匯聚點(diǎn)，則到根匯聚點(diǎn)路徑開銷為0，否則就為其他匯聚點(diǎn)所收到的IDU的Root Path Cost(receive)值與收到該配置消息的道路端口擁堵因子(Port Cost)之和。擁堵因子Root Path Cost計(jì)算公式如②所示：

Root Path Cost

=Root Path Cost(receive)+Port Cost(receive)②

（3）確定指定匯聚點(diǎn)和Designated Port：一條道路路徑分別連接到兩個不同的匯聚點(diǎn)，根據(jù)公式①和公式②的計(jì)算結(jié)果，Root Path Cost最優(yōu)先，即擁堵因子值最小的匯聚點(diǎn)為指定匯聚點(diǎn)。一條道路鏈路中所屬指定匯聚點(diǎn)的端口為指定端口（Designated Port）。

（4）確定根端口（Root Port）和替代端口（Alternate Port）：非根匯聚點(diǎn)上接收的最優(yōu)五元向量組的端口為根端口。除了根端口和指定端口，其余的端口都是替代端口，這樣就構(gòu)成了一個邏輯樹形結(jié)構(gòu)的最低擁堵交通網(wǎng)絡(luò)。

2 算法實(shí)現(xiàn)

根據(jù)上節(jié)提到的向量組優(yōu)先級比較以確定最終的匯聚端口優(yōu)先向量，根據(jù)端口優(yōu)先向量的內(nèi)容確定端口角色，這樣可以實(shí)時計(jì)算整個城市交通網(wǎng)中存在一條通過花費(fèi)最小的道路。當(dāng)?shù)缆钒l(fā)生堵塞觸發(fā)重新計(jì)算進(jìn)程，從而找到其他備份的最優(yōu)道路。下面以一實(shí)例說明：如圖1所示，所在城市有四個主要道路匯聚點(diǎn)，根據(jù)重要性匯聚點(diǎn)賦值分別為：0.65，0.97，0.86和0.78。以第二個匯聚點(diǎn)為例，其有四個Port連接到城市交通網(wǎng)，67.2代表第二個端口的花費(fèi)值為67，其余匯聚點(diǎn)和端口均為此表示方法。使用向量優(yōu)先比較，以下計(jì)算為第二個匯聚點(diǎn)，權(quán)重值為0.97的端口角色。

圖1　城市交通網(wǎng)絡(luò)匯聚點(diǎn)與端口權(quán)值

（1）第二個匯聚點(diǎn)各個道路端口接收的道路對端端口發(fā)來的五維消息向量組與初始化時本匯聚點(diǎn)各個端口的優(yōu)先向量，根據(jù)優(yōu)先級得到根匯聚點(diǎn)為權(quán)值是0.65的匯聚點(diǎn)和各個端口的更新累積擁堵因子值的端口向量組：

（2）從root path cost vector中找到最優(yōu)向量作為指定匯聚點(diǎn)向量，再根據(jù)根匯聚點(diǎn)的權(quán)值和接收端口的擁堵因子值進(jìn)行更新，生成指定端口。

（3）在更新過的端口優(yōu)先向量組中，1端口與2端口的向量都來自其本省的擁堵因子累積向量，端口1的擁堵花費(fèi)為45，而端口2為67，端口1由于端口2為最優(yōu)路徑端口。端口角色被定義后，port priority vector參與下一輪運(yùn)算。

分析：經(jīng)過以上算法，算出權(quán)值0.97的匯聚點(diǎn)的端口優(yōu)先向量，端口1和2的優(yōu)先向量表明，根匯聚點(diǎn)和上游匯聚點(diǎn)均為0.65，由于端口2到根匯聚點(diǎn)開銷比端口1大，所以端口2為替代端口最為端口1的冗余。端口3、4的port priority vector來自designated vector，所以為指定端口。

當(dāng)計(jì)算完成后可以定時重復(fù)運(yùn)算，通過道路流量監(jiān)測在只改變端口擁堵因子值的條件下重新計(jì)算單向通道花費(fèi)值，找到最優(yōu)的覆蓋所有匯聚點(diǎn)的道路。其他匯聚點(diǎn)以相同算法運(yùn)算，這樣在城市交通網(wǎng)絡(luò)總形成了一條單向最優(yōu)道路。如圖2所示，其中實(shí)線為最優(yōu)道路，虛線為擁堵道路。

圖2　城市交通網(wǎng)最優(yōu)道路選擇

3 結(jié)束語

現(xiàn)代城市交通網(wǎng)中，道路擁堵現(xiàn)象非常普遍。本文以通過比較向量優(yōu)先的方法構(gòu)造了一個五維向量組，使得在擁堵發(fā)生后通過計(jì)算快速找到最優(yōu)疏散道路，有效緩解交通壓力，并且避免了傳統(tǒng)憑經(jīng)驗(yàn)疏散的弊端。通過本算法比較向量組優(yōu)先級的方法明了直觀，便于計(jì)算機(jī)運(yùn)算，下一步研究重點(diǎn)是如何生成雙向通道的最優(yōu)道路。

[1] Russell T F.Time stepping along characteristics with incomplete iteration for a Galerkin approximation of miscible displacement in porous media[J].SIAM J Numer Anal,2009, 22(5):970-1030.

[2] De Sousa. Improving Load Balance and Resilience of Ethernet Carrier Networks with IEEE 802.1D Spanning Tree Protocol[Z].Mauritius Islands: 5th Int Conference on Networking,2006.

[3] ZHANG Yin-di,LI Ka-i tai.The error estimates of the characteristic finite element method for nonlinear advection-diffusion equation [J]. Journal of Changpan University:Natural Science Edition,2004,24 (6):106-110.

[4] 王輝.一種基于 MSTP的負(fù)載均衡算法設(shè)計(jì)[J].電子設(shè)計(jì)工程,2011,19(215):83-86.

[5] 呂俏,劉啟文,石冰心.STP協(xié)議原理的算法與實(shí)現(xiàn)[J].華中理工大學(xué)學(xué)報(bào),2008,28(1):38-41.

[6] G Ibanez, Garc?-Mart?,Azcorra. Bridges:Scalable,selfconfiguring Ethernet campus networks[J/OL].Computer Networks, 2008,52(3):630-649.

[7] 關(guān)積珍,鄭長青,朱雪良,等.北京奧運(yùn)交通誘導(dǎo) VMS信息發(fā)布研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2008,8(6):115-120.

[8] MEI Zhen-yu,XIANG Y-i qiang,CHEN Jun,et al.Optimization method of configuration of traffic flow guid-ance information board in urban[J].Journal of Traf-fic and Transportation Engineering,2007,7(5): 88-92.

The design and implementation of the algorithm for the traffic congestion in urban traffic network

The information of urban traffic flow has the characteristics of real time. The prediction of the traditional road congestion is carried out in the event of blockage, and the road diversion is also based on the experience of the drivers, the accuracy rate is very low. In this paper, a new algorithm is proposed, which is used to calculate the road information flow in real time and to select the optimal path. The algorithm designed a five dimensional vector as input information, the vector group priority comparison method, through the road port calculation to generate optimal path. At the end of this paper, a practical calculation example is given, and the congestion diversion algorithm can generate the other optimal path, so that the traffic flow can be optimized.

Urban traffic; traffic congestion; vector priority

TP 393.1

A

1008-1151(2015)09-0004-03

2015-08-12

西安工業(yè)大學(xué)校長基金（XAGDXJJ1216）。

唐俊勇（1975－），男，西安工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院講師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)，網(wǎng)絡(luò)協(xié)議與分析。