基于车辆的混合式路径诱导系统框架研究

倪玲霖^{1, 2}，秦进¹

(1．中南大学 交通运输工程学院，湖南 长沙，410075；

2．浙江财经学院 工商管理学院，浙江 杭州，310018)

摘要：结合中心式诱导系统和分布式诱导系统的优点，提出基于车辆的中心/分布混合式路径诱导系统的框架结构及其路径修正算法。该系统包括中心子系统和分布子系统2部分，其中中心子系统根据系统中车辆所收集的实时交通信息，通过给定的交通模型生成预测型诱导信息，并将诱导信息向系统中的被诱导车辆发布；分布子系统中的车辆则同时充当诱导系统的感应装置、数据传送装置、计算单元以及使用者，在收到中心子系统发布的诱导信息后，车辆可再结合其邻域内的实时交通信息对诱导信息进行修正，以帮助驾驶员选择最合适的诱导路径。算例计算分析结果表明：混合式路径诱导系统能有效降低交通网络内车辆的平均旅行时间。

关键词：混合式；路径诱导系统；框架；路径修正

中图分类号：U492          文献标志码：A         文章编号：1672-7207(2011)S1-0530-06

Framework for vehicle-based hybrid route guidance system

NI Ling-lin^{1, 2}, QIN Jin¹

(1. School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China；

2. College of Business Administration, Zhejiang University of Finance & Economics, Hangzhou 310018, China)

Abstract: This work mainly presents concept, framework and decentralized algorithms for a vehicle-based centralized/decentralized hybrid route guidance system. In the hybrid route guidance, the vehicle senses, transmits and receives network real-time traffic information, and acts as a computer and user of guidance. A hybrid framework was presented, in which the predictive guidance information was computed by centralized sub-system using special traffic information and model, and these information was received and revised according to the real-time local information by the vehicle-level decentralized sub-system, and the drivers used the revised information to help select the rational paths. The results show that the vehicle-based hybrid route guidance system can reduce the average travel time in the transportation network obviously.

Key words: hybrid; route guidance system; framework; path adjustment

智能交通系统(Intelligent transportation system, ITS)是将先进的信息技术、通讯技术、传感技术、控制技术以及计算机技术等有效地集成运用于整个交通运输管理体系，建立起一种在大范围内、全方位发挥作用的，实时、准确、高效的综合运输和管理系统。路径诱导系统(Route guidance system, RGS)是智能交通系统的一个重要组成部分，它是基于电子、通信以及网络等现代技术，通过诱导驾驶员的出行行为来改善路面交通系统，防止交通阻塞的发生，并且最终实现交通流在交通网络中各个路段上的合理分配。

根据系统中最优路径计算和发布地点的不同，路径诱导系统可分为中心式路径诱导系统(Centrally route guidance system, CRGS)和分布式路径诱导系统(Distribution route guidance system, DRGS)^[1]。前者是在交通信息中心的主机上，基于实时交通信息进行路径优化选择，为每一个可能的OD对计算出最优或准最优路线，然后，通过广播或通信网络提供给用户；而后者则是信息中心，只负责从传感器接收实时交通信息，并将此信息发送给网络中的车辆，车辆则根据从通讯网络中接收到的实时交通信息，结合车载设备中存储的有关数据，在车载计算机内计算出最优或准最优路径，依次进行路径诱导。由此可以知道：CRGS是一种典型的预测型诱导系统，而DRGS则是一种典型的反应型诱导系统。

CRGS与DRGS各有其优缺点：DRGS由于不能充分共享信息，因此，对交通网络交通状况的预测往往与实际相差较大；而CRGS虽然能提供较高质量的预测，但是由于计算量巨大，因此，对于较大范围内的交通状况预测存在一定难度。研究表明：预测型CRGS在具有可靠数据的前提下，能够提供高质量的路径诱导信息^[2-4]，而反应型DRGS则在CRGS不能奏效的情况下(比如由于计算资源稀少，预测质量差，以及设备限制等)，能提供达到驾驶员可接受水平的各种路径诱导信息^[5-8]。

CRGS能在整个交通网络上进行配流优化，而DRGS则能在小范围内提供高质量的路径诱导信息，因此可考虑将上述2种诱导系统的优点结合起来，构建中心/分布混合式路径诱导系统。系统包含中心诱导子系统和分布诱导子系统2子系统。中心诱导子系统是在城市的交通信息中心内进行部署，其计算能力和功率都比较强大，可以用来执行大范围的预测型诱导任务；而分布诱导子系统则配置于交通网络中的车辆上(所有车辆上的相应车载设备构成分布子系统)，其功率和计算能力也比较有限，一般不能进行大范围内的通讯和过于复杂的计算，但是，可以用来收集其所处的局部区域内的实时交通信息，并据此对来自中心子系统的路径诱导信息进行修正；同时，分布子系统还可以将实时交通信息传递给中心子系统，以辅助中心子系统更新相关数据并重新求取最优的诱导路径。

1  混合式路径诱导系统框架

通过对基于车辆的混合式路径诱导系统结构框架进行分析，以期有效结合CRGS与DRGS的优点，使两者达到协调配合和相互补充。基于车辆的混合式路径诱导系统的基本框架图和运行结构图如图1和图2所示。

图1  混合式路径诱导系统框架图

Fig.1  Framework of vehicle-based hybrid route guide system

图1中的t和t′均表示时间，在该诱导系统框架结 构中，上层的中心子系统固定的每隔a分钟就计算并发布1次全网络的路径诱导信息。该诱导信息使用基于当前OD需求矩阵的动态交通分配(Dynamic Traffic Assignment，DTA)模型生成，因此，是典型的预测型信息。分布式子系统配置于相应车辆上，这些车辆可视为网络信息的感应装置和数据传送装置以及诱导信息的计算单元和使用者，车辆每隔a分钟就可收到来自中心子系统更新后的诱导信息。在这个时间间隔 中，一定区域内的车辆之间还可以相互保持信息通讯联系，只要发生了特定的“事件”(如车辆到达了某个节点，或区域内发生交通事故等)，区域内的所有车辆都会收到更新后的交通信息数据。因为车辆之间的信息交换只能在局部区域内进行，这里为了方便后面描述问题，使用r邻域来定义车辆的局部区域，即当前车辆的r邻域是以车辆当前所在位置为圆心，以长度r为半径的范围，如图2和图3中所示。

图2  混合式路径诱导系统运行结构图

Fig.2  Operation architecture of vehicle-based hybrid route guide system

图3  车辆的r邻域以及旅行费用构成

Fig.3  The r-neighborhood of the vehicle and the components of travel cost

混合式路径诱导系统中的中心子系统会根据数据库中的相关交通信息，计算生成预测型的路径诱导信息，并将此诱导信息传输到交通网络中所有装备有相应车载设备的车辆上。由于交通网络上交通流量的情况复杂多变，导致中心子系统的算法复杂度会很高，计算时间也相应比较长，因此其生成的诱导信息就可能会存在一定的滞后性。由此，交通网络中装备有诱导设备的车辆所收到的路径旅行时间信息与仅向中心子系统提供计算资源用来产生诱导信息的车辆所感知的路径旅行时间就可能不一致，这可能是由于中心子系统存在滞后性而没有注意到区域内一些事件的发生，也可能是由于交通网络随机性事件的影响，或者是由于在中心子系统的计算(预测或需求估计时)出现了较大的误差。在期望旅行信息和实际旅行信息之间存在差异性的情形下，就非常需要使用实时交通信息数据来改进中心子系统所求得的最优路径信息。使用实时数据对中心诱导子系统的计算进行改进的目的，正是为了使系统能更迅速地对时刻变化的交通网络状况做出及时反应。当然，这还需要尽可能降低相应算法的计算复杂度。

在基于车辆的混合式路径诱导系统中，装有车载设备的车辆具有感应装置，可以用来收集实时交通信息，并将这些信息传输给中心子系统，后者可以利用这些数据对中心子系统的数据库进行更新并生成修正后的OD需求估计，据此再实时更新路径诱导信息。因而，在系统框架内，中心诱导子系统在部分依靠网络中车辆收集数据基础上，可以滚动式地预测网络中各路段和交叉口的交通流量，从而生成各类路径诱导信息。

装备有车载设备的车辆作为路径诱导系统的用户，一般只是单纯的与交通信息中心进行信息的交 换。但是考虑到在这类车辆上装有先进的通讯技术设备，该设备不仅包含感应装置，还可以配置小型的计算单元，因此车载设备作为分布子系统的主要构成组件，完全可以在系统中发挥更大的作用。如果在车辆的r邻域内，车辆之间可以保持相互通讯，实时交通信息等数据是由车辆收集并在车辆之间共享，这使车载设备储存其r邻域内的最新交通信息数据并对其进行实时更新成为可能。在此基础上，分布子系统的计算单元根据这些实时的最新交通信息，就可以对之前由中心子系统发布的路径诱导信息进行即时修正和更新。因此，通过交通信息中心的预测型中心子系统和基于车辆的反应型分布子系统的有机结合和相互补充，构成以车辆为中心的混合式路径诱导系统，可以对单一类型诱导系统生成的路径诱导信息质量进行有效提升。

综上所述，对于基于车辆的中心/分布混合式路径诱导系统，车辆不仅充当中心子系统的感应装置和数据传送装置，在交通网络中收集实时交通信息并向中心子系统传输，同时也作为分布子系统中的个体。车辆上的车载设备可以接收由中心子系统计算生成的路径诱导信息，并充当诱导系统的计算单元，利用其收集的局部区域内的实时交通信息，对中心子系统生成的最优诱导路径进行修正。由此可知：在混合式路径诱导系统中，车辆充当了感应装置、数据传送装置、数据接受装置、计算单元和用户等多重角色，发挥了极其重要的作用，因此，本文作者所提出的混合式路径诱导系统，实际上是以分布子系统(即车辆)为中心的。

2  分布式路径修正算法

对于在中心子系统中根据当前的交通信息进行动态交通分配以预测网络流量分布，已经有很多的成熟的模型和方法，下面仅讨论分布子系统中的算法问 题。此处将给出基于车辆的混合式路径诱导系统中分布子系统的路径修正算法，该算法能够考虑中心子系统和分布子系统之间的内在联系，并对中心子系统产生的预测型诱导路径信息进行改进，而且算法中所使用的优化路径，来自于事先确定的备选路径集合。

中心子系统计算生成的诱导信息来自于大规模的预测型动态交通分配模型，这些信息可能对交通流的长期预测更为有利，但是对于短期情形而言，其预测情况可能与实际交通状况并不一致，因此，如果能使用实时交通数据进行预测和分析，显然能提供质量更高的路径诱导信息。但是，对于中心子系统而言，由于数据庞大且复杂，实时数据的收集和预测模型的运算量都需要一定时间，因此，在中心子系统层面进行诱导路径信息实时修正的计算难度过大。对于配置在车辆上的分布子系统而言，由于其计算能力有限，不能根据大范围的实时信息对诱导信息进行有效的计算分析，但却可以考虑较短时间内其r邻域内的交通实时信息，利用路径修正算法对中心子系统生成的诱导路径进行修正，考虑到其计算能力有限，利用路径修正算法仅对车辆r邻域内的部分路径进行修正。

路径修正算法中所使用的路径旅行费用，即车辆从当前所在点i沿路径p到达预定的终点d的费用c_p，由2部分组成：第1部分是从点i沿路径p到达其r邻域范围内另一点j(一般是最靠近其邻域边界的点)的旅行时间，记做，这是一个较精确的旅行费用值，其值是车载的分布子系统修正中心子系统的有关数据之后得到的；另一部分则是从j到达r邻域范围之外的终点d的旅行时间，记这个估计值为，该值是由最近一次的中心子系统预测产生的最新数据，不用对其再次计算和修正。因为车辆目前也缺少此区域的实时交通信息，而且这也可以减少分布子系统的计算量，因此，车辆从当前点i沿路径p到达终点d的估计旅行费用为：

               (1)

如果交通网络中的所有车辆都执行同一路径优化算法，那么所有车辆都会选择最短旅行时间路径，这就会造成相应路径上的交通拥堵，该路径上的旅行时间就会增加。也就是说，被诱导的车辆总是选择最优路径并不一定是最有利的，而被诱导的车辆如果能分流到一些次优的候选路径上，会对整个交通网络的运行更为有利，因此，可以使用下面的Logit函数将被诱导的车辆分流到次优的备选路径上：

，         (2)

其中：集合P是一个备选路径集合，它是从当前节点到d的所有路径的集合的一个子集，目的地为d的车辆被诱导分流到这些路径上；ε_p是在当前节点上前往d的所有车辆中被诱导至路径p的比例；c_p为从当前节点沿路径p到达d的费用；c₀是一个用来保证公式计算精度的常数，在上面的模型中，参数θ可以根据实际情况进行合理调整，以求得到尽可能符合实际情况的分流结果，如当交通网络中配置有诱导设备的车辆数量较大时，那么θ取值应相对较小，从而能够尽可能平衡所有候选路径上的车流量。

分布子系统中被诱导车辆在运行过程中都要执行路径修正算法，算法求取的是车辆从其当前所在点i到其终点d的路径，其中算法中路径的初始路径p是由中心子系统发布的相应诱导路径，p_jd为初始路径p上从j到d的子路径，即。

路径修正算法的具体计算步骤如下：

Step1: ；

Step2: 对路径p上位于邻域之内且离其边界最近的点j，计算从i到j的最短路集合p_ij；

Step3:，，；

Step4: 生成1个随机数，重新选择从i到j的路径；

Step5: ，并输出路径p。

上述路径修正算法最终输出的路径p，是分布子系统利用实时交通信息对中心子系统发布的路径诱导信息进行修正后的诱导路径。上述路径修正算法的复杂度与车辆的r邻域大小有关，但考虑到在实际中车辆的r邻域会是有限的，因此算法的执行时间也会非常短。

3  算例

这里使用1个如下图4所示的交通网络进行计算分析，该网络中共有9个节点和24条路段，路段上的旅行时间采用标准的BPR函数，即：

其中：t_a表示用户在路段a上的实际旅行时间；表示路段a上的自由流时间；x_a为路段a上的实际交通流量；C_a为路段a的设计通行能力；α和β为给定参数，一般可取值为α=0.15，β=4。

图4  算例交通网络结构

Fig.4  Small transportation network

在上述交通网络中，所有路段长度统一设置为30，各路段上的通行能力值和自由流时间分别在区间 (80, 100)和(10, 40)中一次性随机生成。网络中共有4个OD对，即(1, 9)，(3, 7)，(9, 1)和(7, 3)，每个OD对之间的出行需求速率都设置为1 200辆/h。对于前面算法中所使用的其他参数的初始值具体设置如下：θ=0.1，r=100，c₀=10。下面的分析计算都是针对20 min内的网络运行数据进行分析的。中心子系统的预测型诱导信息使用DTA模型进行计算生成，这里选择使用文献[9]中的模型和算法。

图5所示为从平均旅行时间的角度对网络运行状况进行的分析结果，其中诱导系统市场渗透率是指网络中配置有诱导系统的车辆占总车辆数的比例，平均旅行时间差异是指配置有诱导系统和未配置诱导系统的两类车辆之间的平均旅行时间差值。从图5可以看到：随着诱导系统市场渗透率的提高，被诱导和未被诱导车辆之间的平均旅行时间差异一直呈现出不断降低的趋势。这时由于被诱导车辆数量的增加，它们都能更好地选择不拥堵的路径出行，其实是减轻了拥堵路段的拥挤程度，因此，2类车辆之间的平均旅行时间差异性会随着被诱导车辆数量的增加而持续降低。

另外，从图5还可以发现：网络中被诱导车辆的平均旅行时间随着诱导系统市场渗透率的提高，呈现出先上升后下降的趋势。这主要是因为在市场渗透率较低时，被诱导车辆会很容易寻找到不拥挤的替代路径到达目的地，因此，其平均旅行时间会较低；随着市场渗透率的逐渐提高，被诱导车辆的平均旅行时间却随之延长，这是因为随着网络中被诱导车辆数量的增加，原最优路径上发生拥堵，更多的被诱导车辆会选择替代路径，使得替代路径上也产生了拥堵，而此时其他路径上的拥堵并没有缓解，从而导致被诱导车辆的旅行时间上升；随着诱导系统市场渗透率的继续提高，被诱导车辆的平均旅行时间又会逐渐下降。这是因为此时网络中大部分车辆都能获得诱导信息并进行修正，因此，都可以选择合适的替代路径，从而降低了总体的旅行时间。

图5  车辆平均旅行时间分析

Fig.5  Performance of the average travel time of vehicles

4  结论

(1) 提出了基于车辆的中心/分布式混合路径诱导系统的系统框架，并设计了交通网络中被诱导车辆的路径修正算法。

(2) 在混合式路径诱导系统中，位于交通信息中心的中心子系统通过装载在车辆上的车载设备收集交通网络中的交通信息，据此进行计算生成预测型诱导信息并向网络中所有被诱导车辆发布；配置有车载设备的车辆构成分布子系统，且车辆接受中心子系统发布的路径诱导信息，同时，通过与其邻域内的车辆相互交换信息以获得邻域内的最新实时交通信息，在将该实时信息传递回中心子系统的同时，车辆将结合接收到的路径诱导信息和区域内的实时交通信息，利用车载设备的计算单元对其诱导路径进行修正，并选择最合适的替代路径到达目的地。

(3) 混合式车辆路径系统可以有效地降低交通网络内车辆的平均旅行时间，尤其是在达到合适的市场渗透率时，被诱导车辆的出行信息服务质量将得到明显的提高。混合式路径诱导系统结合了中心式诱导系统和分布式诱导系统的优点，因此在未来必然具有广阔的发展前景。

参考文献：

[1] 张国伍. 智能交通系统工程导论[M]. 北京: 电子工业出版社，2003: 22-24.
ZHANG Guo-wu. Introduction of intelligent transportation system engineering[M]. Beijing: Electronic Industry Press, 2003.

[2] 杨兆升, 初连禹. 动态路径诱导系统的研究进展[J]. 公路交通科技, 2004,17(1): 34-38.
YANG Zhao-sheng, CHU Lian-yu. Study on the development of the dynamic route guidance systems[J]. Journal of Highway and Transportation Research and Development, 2004,17(1): 34-38.

[3] Bottom J. Consistent anticipatory route guidance[D]. Cambridge: Massachusetts Institute of Technology, 2000: 113-118.

[4] Wahle J, Annen O, Schuster C, et al. A dynamic route guidance system based on real traffic data[J]. European Journal of Operational Research, 2001, 13(2): 302-308.

[5] ZOU Liang, XU Jian-min, ZHU Ling-xiang. Application of genetic algorithm in dynamic route guidance system[J]. Journal of Transportation Systems Engineering and Information Technology, 2007, 7(3): 45-48.

[6] Pavlis Y, Papageorgiou M. Simple decentralized feedback strategies for route guidance in traffic networks[J]. Transportation Science, 2002, 33(3): 264-278.

[7] Yaser E. Hawas, Mahmassani H S. Comparative analysis of robustness of centralized and distributed network route control systems in incident situations[J]. Transportation Research Record, 1996, 1537: 83-90.

[8] Wunderlich K, Kaufman D, Smith R L. Link travel time prediction for decentralized route guidance architectures[J]. Transactions on Intelligent Transportation Systems, 2000, 1(1): 4-14.

[9] Bellei G, Gentile G, Papola N. A within-day dynamic traffic assignment model for urban road networks[J]. Transportation Research Part B, 2005, 39(1): 1-29.

(编辑 何运斌)

收稿日期：2011-04-15；修回日期：2011-06-15

基金项目：国家自然科学基金资助项目(70901076)；中南大学自由探索计划资助项目(201012200168)；浙江省社科基金资助项目(11YD24YB)

通信作者：秦进(1978-)，湖北京山人，博士，副教授，从事交通运输系统优化研究；电话：13787414541；E-mail: qinjin@csu.edu.cn