城市交通網絡單向擁堵分流算法的設計與實現

唐俊勇郝海燕

（1.西安工業大學計算機科學與工程學院，陜西 西安 710032；2.咸陽師范學院物理與電子工程學院，陜西 咸陽 712000）

城市交通網絡單向擁堵分流算法的設計與實現

唐俊勇1郝海燕2

（1.西安工業大學計算機科學與工程學院，陜西 西安 710032；2.咸陽師范學院物理與電子工程學院，陜西 咸陽 712000）

城市交通流的信息具有實時性特點，傳統道路擁堵的預報都是在堵塞事件發生后進行發布，擇路分流也是憑著駕駛人員的經驗，準確率很低。文章提出一種實時計算道路信息流并選擇最優道路進行分流的算法，具有實時性、智能化高的特點。該算法設計了一個五維向量作為輸入信息，采用向量組優先級比較的方法，通過對道路端口計算來生成最優化路徑。文章最后給出一個實際計算實例，擁堵分流算法生成其他最優備選道路，從而有效的實現了擁堵分流，使城市交通性能得到優化。

城市交通；擁堵分流；向量優先級

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

1 擁堵分流算法

1.1算法概述

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

1.2算法信息數據單元（IDU）的構成

城市交通網絡內各個道路匯聚點（Convergence Point）根據每個道路端口優先級向量決定每個道路端口角色。這些角色分別為：root port, designated port, alternate port, alternate1port。

（1）城市交通網絡中匯聚點不是根匯聚點，且該匯聚點的某個端口優先向量來源于根匯聚點，那么該端口是根 端口（root port）。

（2）道路路徑端口優先向量來源于指定向量，則該端口是交通網絡中的道路指定端口（designated port）。

（3）城市交通網中，除了根端口外，匯聚點某個端口的端口優先向量是從其他匯聚點接收來的，該端口是替代端口（alternated port）。

1.3向量組優先級比較

每個道路端口將參與運算的關鍵參數字段構成一個五維向量：

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

（1）計算Root Convergence Point：在道路交通網絡中各個匯聚點首先推舉一個匯聚點作為樹形道路的根匯聚點，推舉依據是各個匯聚點的優先值，優先值的選擇根據匯聚點在城市交通中重要程度和設計標準選擇，值范圍為[0，1]，計算公式如①所示：

Root Convergence Point =

Priority（Convergence Point {n}） ①

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

Root Path Cost

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

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

（4）確定根端口（Root Port）和替代端口（Alternate Port）：非根匯聚點上接收的最優五元向量組的端口為根端口。除了根端口和指定端口，其余的端口都是替代端口，這樣就構成了一個邏輯樹形結構的最低擁堵交通網絡。

2 算法實現

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

圖1　城市交通網絡匯聚點與端口權值

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

（2）從root path cost vector中找到最優向量作為指定匯聚點向量，再根據根匯聚點的權值和接收端口的擁堵因子值進行更新，生成指定端口。

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

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

當計算完成后可以定時重復運算，通過道路流量監測在只改變端口擁堵因子值的條件下重新計算單向通道花費值，找到最優的覆蓋所有匯聚點的道路。其他匯聚點以相同算法運算，這樣在城市交通網絡總形成了一條單向最優道路。如圖2所示，其中實線為最優道路，虛線為擁堵道路。

圖2　城市交通網最優道路選擇

3 結束語

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

[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的負載均衡算法設計[J].電子設計工程,2011,19(215):83-86.

[5] 呂俏,劉啟文,石冰心.STP協議原理的算法與實現[J].華中理工大學學報,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] 關積珍,鄭長青,朱雪良,等.北京奧運交通誘導 VMS信息發布研究[J].交通運輸系統工程與信息,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

西安工業大學校長基金（XAGDXJJ1216）。

唐俊勇（1975－），男，西安工業大學計算機科學與工程學院講師，研究方向為計算機網絡，網絡協議與分析。