基于局部连通性的在途动态路径诱导方法

梁 伟，张 毅*,2,3，胡坚明

(1.清华大学自动化系，北京100084；2.清华—伯克利深圳学院，广东 深圳518055；3.江苏省现代城市交通技术创新中心，南京210096)

0 引言

随着现代城市路网规模的不断扩大，道路结构越发复杂，同时驾车购物出行需求日益增加，使得交通流状态呈现出复杂多样的变化趋势，“行车难、停车难”问题突出，形势严峻，已引起社会各界的广泛关注.为了合理利用资源，解决这一社会难题，给出行者带来舒适的驾车体验，许多专家学者对此展开了研究.目前，出行时规划行车路线，即路径诱导，给出行者提供一个或多个时间最短或距离最短路径，已经成为大多数城市居民驾车购物出行时的优先选择.在路径诱导方法中，通常分为传统路径规划方法和智能路径规划方法两类.传统方法[1-4]应用最短路搜索算法来规划最优行驶路径，这种方法成熟可靠，但是大多不能自适应实时交通流状态的变化，当路网信息发生较大变化时，路径诱导效果就会出现明显偏差，严重影响驾车购物者的出行体验.智能方法利用启发式算法搜索最优路径[5-6]，或者利用神经网络和遗传算法等动态搜索最优路径[7]，大多在全局路网结构上重新搜索，路径规划的计算量和计算时间负担较重，路径规划实时性差.购物出行是以购物为目的的一种出行方式，目的地(购物中心)多处于闹市区.人们购物出行时希望处于舒适的出行环境中，通常会对心理预期的车辆平均行驶速度格外关注；而且，由于目的地比较明确，途中如果需要改变行驶路线，出行者也大多倾向于局部调整其行前诱导路径.因此，有必要研究根据交通流状态动态变化情况自适应对局部路径进行更新的路径诱导方法，以满足驾车购物的实际诱导需求.

本文首先引入出行期望速度阈值，分析路网中节点之间的动态连通性，优化路网结构，限制路网规模，建立局部路网模型，然后提出一种基于局部连通性的在途路径诱导方法，实现有效的在途动态路径诱导.

1 局部路网建模

一个包含m个路口和路口间路段组成的路网可表示为有向图模型其中P={p1,p2,…,pm}是节点(路口)集合；E={eij|i,j=1,2,…,m} 是边(路段)集合，eij是从节点pi出发到达节点pj的路段是路阻集合，dij是边eij的路阻，表示车辆通过该路段的通行代价，用道路交通状态系数[8]Iij来描述，它是在途车辆在路段上平均行驶速度的倒数，即

在途车辆行驶通常会受到道路交通流状态的影响，道路交通状态系数可以描述道路的交通流状态.路网模型中，路阻越大，道路交通越拥堵，这将直接影响节点之间的连通状态.

1.1 动态连通性分析

引入出行期望速度阈值λ，其描述了购物者出行希望达到的平均速度(即出行者能畅通行驶的速度).根据中国道路交通管理评价指标规定：城市主干道机动车平均行程速度不低于30 km/h为畅通，20～30 km/h为轻度拥挤，10～20 km/h为拥挤，低于10 km/h为严重拥挤.将20 km/h与道路的实际限速进行比较，取两者平均值，作为出行期望速度阈值.

当某路段的路阻大于阈值时，说明出行者驾车行驶时，将不能处于通畅状态，影响其出行体验，该路阻可近似为无穷大，此时连接该路段的多个节点之间视为不连通；反之，节点之间处于连通状态.路阻矩阵D(λ)表示在λ下路网中相邻2个节点之间的实际通行代价，表达式为

式中：aij是2个节点的空间邻接关系.

在出行期望速度阈值λ下，路网的空间动态邻接矩阵为

进而，在2个节点之间的所有连通路径中，经过l条边的路径总路阻为

式中：p1,p2,…,pl-1是从节点pi出发到达节点pj的连通路径所经过的节点，满足p1,p2,…,pl-1∈P且p1≠p2≠…≠pl-1.

当出行期望速度阈值不同时，路网节点间表现出不同的连通性.如图1所示的仿真路网，线段上的数字表示该道路的路阻值.

当期望速度阈值分别是0.050、0.040和0.033时，其路网拓扑如图2所示(图中相应节点的编号同图1).

图1 仿真初始路网的拓扑结构Fig.1 The initial road network

图2 不同期望速度阈值下的路网拓扑Fig.2 Structures under different traffic congestions

考察图2中从节点p6到节点p7的边e6-7，当出行者驾车行驶时，期望速度较小时(λ=0.050)，边e6-7处于连通状态；当期望速度较大时(λ=0.040)，边e6-7处于断路状态.在以上2种不同期望速度下，路网表现出截然不同的连通性.

交通路网是一种复杂网络，由相关研究[9]可知，复杂网络的连通性能可用网络节点之间连通路径的总数目来评价.以此为基础，提出2个动态连通性指标——有效可达值Φ和平均可达路阻γ，来评估在不同出行期望速度阈值下节点之间的动态连通可达程度.

(1)有效可达值Φ.

(2)平均可达路阻γ.

式中：Nij(L,λ)是从节点pi出发到达节点pj的连通路径数目[9]；Qij(λ)是从节点pi出发到达节点pj时含有回路的连通路径数目；l为2个节点之间的连通路径经过的边数目；L是连通路径经过边的最大数目；M是连通路阻阈值，它限制了路网节点间连通路径的最大路阻，通常受到行前诱导路径路阻的影响，当行前诱导路径路阻较大时，阈值也较大，反之则较小.

1.2 局部路网模型

当城市交通路网中局部交通流较大或发生交通事故、临时交通管制等，致使车辆还未行驶过的诱导路径出现拥堵、造成连通失效时，在途车辆须及时更新诱导路径.为了保证行驶路径的可靠有效连通，本节利用动态连通性指标来计算并评估车辆当前位置附近的局部路网，并在其中进行诱导路径的局部更新.局部路网以在诱导路径上行驶的车辆位置为基准，涵盖周围部分区域.它随着在途车辆的行驶位置动态可变，保持着从当前节点到目的地终点的动态连通能力.

节点pO和pD均处在行前诱导路径上，它们之间满足pO,pD的关系，即车辆行驶时先经过节点pO，后经过节点pD.为了讨论方便，本文将局部诱导路径上的节点按照车辆行驶通过的先后次序进行编号，即局部诱导路径上的节点pO,…,pi,…,pD映射为正整数1,…,i,…,q，依此，节点pO和pD的关系也可表示为pO＜pD.另外，2个节点之间动态路阻和拓扑关系是有向图模型分析的重点，这里用一个ω算子将实际距离Ψ转换成诱导路径上它们之间间隔的节点数目以避免实际距离不同对模型分析的影响.

假设车辆到达节点pGet时获取到实时交通信息，计算诱导信息花费时间是tcompute-select；当出行者收到诱导信息后开始做出更换车道等操作反应时，车辆位置处于反应节点pRenew；车辆执行操作反应所花费的最少时间是tmin，之后车辆到达起点pO.另设计算局部路网需要的最大时间值是T，在途车辆的平均行驶速度是，实时交通信息更新周期为Γtr.虽然在收到诱导信息时，出行者也需要一个心理反应时间，但根据蔡伯根等[10]的研究，该心理反应时间相对较小，本文暂不考虑.上述节点之间的关系如图3所示.

图3 起点与其他节点之间的关系示意图Fig.3 Relationship between the origin and other intersection

(1)起点的计算.

计算起点pO的目的是为出行者更新路径提供充足时间进行决策并做出反应，具体来说，它影响着局部路网的计算、诱导路径的更新、车辆对诱导做出反应的时间等.起点的设置与车辆的当前位置、车辆行驶速度和实时交通信息更新频率等因素有关.

若Γtr≥tcompute-select+tmin，即车辆经过反应节点pGet后，就不再接收新的交通信息，此时可得T=Γtr；若Γtr＜tcompute-select+tmin，则可令Γt'r=n⋅Γtr,n=1,2,…，取的最小值

已知车辆到达节点pGet时，获取实时交通信息，则有

观察组治疗总有效率98.67%(148/150)高于对照组87.33%(131/150),对比差异有统计学意义(P<0.05)。见表1:

节点pRenew满足

综上，起点pO应满足

(2)确定终点和局部路网规模.

终点和局部路网规模决定了出行者在局部路网中可能选择的备选路径.合理的终点能够保证在不同程度的交通拥堵下，其与起点之间总能存在连通路径.设置1个有效可达值阈值K，终点pD须满足式(11)的条件.

而局部路网规模则决定了出行者选择备选路径的范围.当规模较大时，备选路径一般也会较多.当备选路径达到一定数量时，出行者就足以寻找到高效合理的连通路径.但是，如果规模太大，备选路径的冗余率提高，从而增加驾车购物者的出行成本，加大城市交通出行的整体压力.另外，一般会存在多个满足式(11)要求的局部路网，但是它们涵盖备选路径的路阻却不尽相同，平均可达路阻越小的那些局部路网的连通性能自然越好.因此，最优局部路网的规模须满足

综上，根据交通拥堵阈值和路阻函数，计算D(λ)，在此基础上，求得起点pO，根据式(11)求得终点pD，再根据式(12)，计算集合P和E，至此解得最优局部路网，可保证在途车辆在遇到交通拥堵时能够选择高效的备选路径行驶，更新诱导路径.

2 在途动态路径诱导方法

在途动态路径诱导方法是在局部路网中寻找最优路径以局部更新行前诱导路径，保证在途车辆当前位置与终点的连通性，自适应道路交通流的变化.具体地，该方法将行前诱导路径作为初始路径，根据车辆位置，首先确定起点pO和终点pD，并构建一个初始局部路网Ginit作为初始解，再求解出最优局部路网GLocal，继而在GLocal上更新局部路径，直至诱导车辆到达终点.整个方法采用开放式设计，原理框架图如图4所示.

3 实验验证和评估

实验以北京市海淀区某购物中心驾车出行为例，出行起点为学府树家园，终点为金源新燕莎购物中心(行程距离约15 km)，出行区间涵盖约上百个路口.出行区间的部分地图如图5所示，图中黑色实线是行前诱导路径，右图为左边圆圈内实验区域路网的有向图(道路均是双向通行，由于篇幅限制，图中未标出道路方向和路阻).

实验假设在途车辆到达节点p29前的一个计算周期内，节点p3处发生3种不同严重程度的交通事件，导致附近交通状态变化较大，分别造成1个路口、3个路口和4个路口的拥堵(图6中深黑色线条所示)，分别优化求解局部路网，验证本文方法对不同最短路算法(Dijkstra算法、A*算法)的有效性和适应性.

图4 在途动态路径诱导方法原理框架图Fig.4 Diagram of en-route dynamic route guidance

实验中交通拥堵影响了从节点p29到节点p2的诱导路径其原路阻为0.057.本文方法需要优化局部路网，而局部路网规模受到出行期望速度阈值的影响，针对3种情况分别进行讨论，结果如表1所示.实验中，出行期望速度阈值设置为0.070.

(1)当交通拥堵影响1个路口(p3)时，本文方法中最优路径搜索算法采用Dijkstra算法，路径规划时涉及到8个节点，计算时间为0.12 s，诱导路径更新为

图5 北京市海淀区部分地图及实验区域Fig.5 Example in part of Beijing Haidian District

图6 不同严重程度交通拥堵示意Fig.6 Congestions in different intersections

(2)当交通拥堵影响3个路口(p3、p4、p6)时，求解出的局部路网规模相应变大，本文方法中最优路径搜索算法采用A*算法，路径规划时涉及到10个节点，计算时间为0.18 s，局部诱导路径更新为

(3)当交通拥堵影响4个路口(p3、p4、p6、p11)时，求解出的局部路网规模较大，本文方法中最优路径搜索算法采用A*算法，路径规划时涉及到11个节点，计算时间为0.22 s，局部诱导更新路径为

将本文方法和神经网络与遗传算法相结合的动态路径诱导方法[7]进行比较.在车辆到达节点p29前的计算周期里，对比方法基于神经网络对实验区域内各路段的路阻进行预测，并构建其具有时变性的路阻矩阵，再采用遗传算法选择最优路径.针对3种不同拥堵情况，对比方法计算时分别涉及到28个、26个和25个节点，计算时间分别为0.73 s、0.61 s和0.45 s.具体计算指标如表1所示.

表1 不同方法的计算指标比较Table 1 Comparison of different approaches

从表1中可以看出，在3种不同交通拥堵情况下，本文方法具有更好的开放性和计算规模上的优势，表现出良好的诱导效果和对于实时交通流状态变化的自适应能力.

4 结论

针对传统路径诱导方法没有实现实时局部在途更新的缺陷，本文针对驾车购物出行的自适应路径诱导方法展开研究.引入出行期望速度阈值，研究了实时交通流影响下路网的动态连通性，给出动态连通性指标，优化局部路网结构，提出了一种在途动态路径诱导方法，根据实时交通流状态为出行者实时更新局部诱导路径.对该方法进行了实地实验验证，并跟神经网络与遗传算法相结合的动态路径诱导方法进行比较，实验结果表明，本文方法更能实时准确地确定局部路网最优路径.在该算法的开放性结构下，随着更先进的最短路径搜索算法和路阻函数的出现可得到进一步的发展，以满足在途动态路径诱导的实际需要.

[1]HAWAS Y E,EL-SAYED H.Autonomous real time route guidance in inter-vehicular communication urban networks[J].Vehicular Communications,2015,2(1):36-46.

[2]SHIFFMAN S.Analytical hierarchy process using fuzzy inference technique for real-time route guidance system[J].IEEE Transactions on Intelligent Transportation Systems,2014,15(1):84-93.

[3]LIANG Z L,WAKAHARA Y.Real-time urban traffic amount prediction models for dynamic route guidance systems[J].EURASIP Journal on Wireless Communications and Networking,2014,2014(1):1-13.

[4]PAN J,POPA I S,ZEITOUNI K,et al.Proactive vehicular traffic rerouting for lower travel time[J].IEEE Transactions on Vehicular Technology,2013,62(8):3551-3568.

[5]SHAHZADA A,ASKAR K.Dynamic vehicle navigation:An A*algorithm based approach using traffic and road information[C]//IEEE International Conference on Computer Applications and Industrial Electronics.Penang:IEEE,2011:514-518.

[6]JIANG J C,WU L X.A re-optimization dynamic shortest path algorithm for vehicle navigation[C]//Geoscience and Remote Sensing Symposium,IEEE,Quebec City,2014:3109-3112.

[7]吴成东,杨丽英,许可.神经网络和遗传算法在动态路径诱导中的应用[J].计算机应用研究,2006(5):177-179.[WU C D,YANG L Y,XU K.Application of neural network and genetic algorithm in dynamic route guidance[J].Application Research of Computers,2006(5):177-179.]

[8]张和生,张毅,胡东成,等.区域交通状态分析的时空分层模型[J].清华大学学报(自然科学版),2007,47(1):157-160.[ZHANG H S,ZHANG Y,HU D C,et al.Spatial-temporal hierarchical model for area traffic state analysis[J].Journal of Tsinghua University,2007,47(1):157-160.]

[9]吴俊,谭索怡,谭跃进,等.基于自然连通度的复杂网络抗毁性分析[J].复杂系统与复杂性科学,2014,11(1):77-86.[WU J,TAN S Y,TAN Y J,et al.Analysis of invulnerability in complex networks based on natural connectivity[J].Complex Systems and Complexity Science,2014,11(1):77-86.]

[10]柴琳果,蔡伯根,王化深,等.车联网中驾驶员反应时间实时估计方法[J].交通运输系统工程与信息,2016,16(5):71-78.[CHAI L G,CAI B G,WANG H S,et al.Real-time estimating method of diver’s reacting time under the condition of internet of vehicles[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(5):71-78.]