城市交通网络单向拥堵分流算法的设计与实现

唐俊勇郝海燕

（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－），男，西安工业大学计算机科学与工程学院讲师，研究方向为计算机网络，网络协议与分析。