一类交通信息物理系统的动态路径引导

陈卓然,韩定定

(复旦大学信息科学与工程学院，上海 200433)

0 引言

近年来，随着物联网[1-2]和大数据[3-4]技术的快速发展，城市交通问题的治理方案不断推陈出新。交通系统中，道路和车辆上的监控和传感设备收集的大量信息，经过实时的处理和分析可用于描述道路和车辆的状态和动态行为[5-6]，通过在线模型及时决策和规划能充分利用交通系统资源、提高道路通行能力[7-9]。信息物理系统(Cyber-Physical Systems, CPS)[10-11]可用于管理此类大数据架构。CPS集成了感知、计算、通信、控制等技术，实现了信息空间和物理空间中人、机、物、环境、信息等要素的相互映射、适时交互、相互协同，应用范围涵盖了智能电网等能源与资源分配网络、智能汽车与交通网络、医疗护理、环境监测与灾害响应、机器人团体协作、工业自动化等众多领域[12]。

可靠、有效的实时交通信息在CPS感知、计算、决策、执行过程中的闭环流通，提高了城市交通系统的服务质量，例如其关键服务之一的动态路径引导[13-15]。动态路径引导，一方面可以通过实时信息对道路中的拥堵迹象进行判断、平衡路网中交通负荷[16-19]，另一方面可以考虑将Dijkstra[20]或Hart[21]等的最短路径算法作用于实时更新的拓扑[22-23]。目前已有不少交通信息物理系统(Transportation CPS, TCPS)在动态路径引导方面的尝试，如利用物联网技术从路段和车辆中采集和聚合实时数据并将短期交通预测与实时路径优化相结合，增强路段与车辆之间的协作[24]；研究由物理交通系统和与其相当的人工交通系统组成的并行智能交通系统，用大量的长期迭代模拟来预测和分析预期的操作结果[25]；考虑道路长度、天气状况、事故等综合成本的最小化，将路网建模为一个不断更新的加权有向图，根据时间表用综合成本最小化策略和最快策略进行引导[26]。现有的方法往往只为单一车辆的出行推荐最优路线，未考虑不同车辆采取相同路径后可能会导致潜在的交通拥堵[27]。在实时全局交通信息已知的情况下，如何以合适的频率对出行个体进行引导，如何权衡全局和个体，或许会是未来城市交通系统面临的挑战。

本文提出了基于实时全局交通信息的TCPS框架，针对动态路径引导中的方式和频率展开仿真和讨论。引入强化学习中的Q-learning作为引导策略，通过定时获取道路的平均通行时间作为动作的惩罚、更新Q值表、依据最大化值策略引导车辆来构建感知、计算、决策、执行中信息流通的闭环。考虑了3种动态引导方式：一次性引导、周期性同时引导和周期性各自引导。仿真结果表明，动态引导相较于基于静态拓扑的最短路径在整体性能上有明显提升；周期性同时引导和周期性各自引导之间差别不大，但都优于一次性引导；同时，仿真发现引导过程中产生的博弈现象：车辆采取相同最优策略会使得该策略因车辆的大量涌入失去优势，导致后续车辆采取与之不同的策略形成制约；周期性同时引导和周期性各自引导的博弈强度随周期发生不同的变化，而整体性能未随周期呈现出明显规律。

1 交通信息物理系统框架

1.1 系统框架

交通信息物理系统的框架如图1所示。在物理空间中，利用物联网技术，可通过监控和传感设备获取整个网路中道路和车辆的实时数据，如道路平均通行时间、车辆的位置和目的地等；在信息空间中，可通过对数据处理和分析来驱动模型做出决策，并与道路上车辆实时通信使其在本地更新路径，以尽快到达目的地。

图1 TCPS框架

基于Q-learning[28-29]的动态路径引导流程如图2所示。将车辆所在道路边作为状态x，下一条边的选择作为动作a，若下一条边为终点则给予奖赏R，否则将其平均道路通行时间作为惩罚。为车辆的每一个目的地维护一张累计奖赏函数Q值表，用实时交通信息更新R、利用ε-贪婪策略更新Q值表、最后根据车辆的当前位置用最大化值函数选择最优引导路径。累计奖赏函数的更新方式如式(1)所示：

图2 Q-learning决策流程图

(1)

其中，x′是在状态x执行动作a后转移的状态，a′是在x′上基于策略π选择的动作，α和γ分别为学习率和折扣因子。

定义道路的平均通行时间(Average Travel Time, ATT)为

(2)

(3)

采用不同的执行策略和评估策略。执行策略在训练中与环境互动产生数据，评估策略学习执行策略产生的数据进行迭代优化。执行策略采用ε-贪婪，保证了训练过程的探索性，使每个动作都有可能被探索到，不容易陷入局部最优：

(4)

π(x)=argmaxa″Q(x,a″)

(5)

1.2 仿真实现

仿真通过微观交通仿真器SUMO(Simulation of Urban Mobility)[30]实现。SUMO用连续的笛卡尔坐标系表示车辆位置、等时间间隔更新车辆状态和位置，以及空间连续和时间离散[31]。实时交通信息包括车辆的目的地和当前位置以及道路的平均通行时间的获取、车辆的行驶路径的改变通过控制接口(Traffic Control Interface, TraCI)实现。

1.2.1 路网和流量

仿真中道路网络为一个6×3的矩形网络，东西向和南北向路段长分别为200m和100m，如图3所示。路口无信号灯、采用默认的南北优先。以最小时间间隔从A1B1到E1F1输入100辆车，采用默认的Krauss car-following模型。静态路径引导得到的最短路径为〈A1B1 B1C1 C1D1 D1E1 E1F1〉。

图3 规则路网

1.2.2 事件场景

图4 事件场景

1.2.3 引导方式

考虑静态路径引导和动态路径引导的几种方式：1)静态引导：只根据静态路网信息，用最短路径算法生成时间最短路径。2)一次性动态引导：在车辆进入路网时，根据该时刻实时路网信息，进行一次性的引导；3)周期性同时引导：按时间间隔τ，更新全局信息并对路网中所有车辆同时进行引导；4)周期性各自引导：从车辆各自发车时刻开始，按时间间隔τ，更新全局信息，进行单独引导。

2 仿真结果

2.1 一次性动态引导

图5 动态路径引导

图6 动态路径引导中的博弈

经过整个路网的车辆行驶距离如图7所示。图7中，行驶距离较长的车辆对应采取博弈行为绕路的车辆。较长行驶距离的频率随着车辆编号增加，可见博弈的正反馈趋势。

图7 一次性动态引导下车辆的行驶距离

2.2 周期性动态引导

在2.1的路网基础上仅保留坑洼路段、去除两处故障拥堵，赋予道路更大的自由度。如图8所示，博弈强度随着路网的自由度变大而增强，在目的地E1F1前的交叉口E1汇聚了来自各个方向的车流。

图8 终点前交叉口E1发生拥堵

首先考虑引导频率即不同时间间隔τ对动态路径引导的影响。τ越小，引导越频繁；τ越大，车辆上一次引导的保持时间越长。受限于路网大小，τ>30时，在周期性同时引导中会出现尚未对车辆进行引导车辆就已驶入坑洼路段的情况。因此取τ=1,2,3,…,30，同时引导和各自引导在不同τ下的平均行驶距离、通行时间和等待时间如图9所示。注意到，同时引导和各自引导在τ=1时是等价的，因此两子图在τ=1的数值相同。

图9 不同时间间隔τ下的平均通行时间、平均等待时间和平均行驶距离

车辆的平均行驶距离反应了整体的博弈强度。随着τ的增大，引导频率降低，车辆维持上一次引导的时间变长，平均行驶距离整体呈现下降趋势，博弈强度减小。其中，同时引导的博弈强度随着τ的下降速度更快。考虑到同时引导会使处于相同状态即位于同一条道路上的车辆采取相同动作，当τ较大时，同时引导更容易形成车队。而引导一旦采取了与τ时刻前不同的动作路径，在引导的早期阶段一般都是博弈行为，博弈的结果是路径经过优先级较高的南北向。此时同时引导因为产生车队，在优先级的路口更具有竞争优势，能够较快通行、减少行驶距离；但产生的后果是会有车队整体被更高优先级路口的其他车队较长时间截断，因此即使行驶距离降低较快，但在平均通行时间和等待时间上并无明显优势。各自引导可视为τ批次的同时引导，因此在引导频率的两极，即τ<13或τ>23时，不同批次的车辆实际上所处的状态在引导早期阶段基本相同，效果和同时引导相近；在τ=15左右时，各自引导呈现出对交通信息更为敏感的特性，平均行驶距离较长、平均等待时间较长，表明其充分利用了路网资源但又受限于路口优先级。

为了进一步比较4种引导方式，通过路网中车辆数量和到达车辆的平均行驶时间这两个指标进行对比。取τ=5，10，15，20，25，结果如图10所示。在两个指标上，动态路径引导都明显优于静态路径引导如图10a，10b所示，能够明显减少路网中车辆数量，降低所有车辆通过路网的用时。此外，如图10c，10d所示，到达车辆的平均行驶时间呈上升趋势，意味着车辆在交叉口的等待是影响其通过路网用时的主要因素之一。

图10 路网中车数和到达车辆平均行驶时间随仿真时间的变化趋势

最后，为了进一步探究周期性引导两种方式与一次性引导的区别，比较了静态引导、一次性引导以及两种周期性引导τ=15按车辆到达次序的总通行时间、等待时间和非等待时间，结果如图11所示。图11a中静态引导的车辆全体经过了坑洼路段，总通行时间与非等待时间重合，整个过程车流没有停滞，但前60辆车的用时不断增加，说明车队在行驶过程中会受到驾驶员差异的影响。图11b～11d中，非等待时间均处于[100,200]区间内，说明当车辆运动时，基本上以较快速度行驶，其通行时间差异主要由等待时间引起。一次性引导中，最后到达的一部分车辆都经历了长时间等待，即图8所示的目的地前的拥堵；而周期性引导通过基于实时交通信息的多次引导能缓解这部分潜在的拥堵，但也在一定程度上造成了提前的小规模长时间等待。另外，如图11d所示，各自引导的等待时间呈现多个尖峰，说明有个别车辆经历了长时间的等待，成为引导过程中的信息敏感性对出行个体带来的不稳定性的牺牲品。

图11 总通行时间、等待时间及非等待时间与到达次序的关系

3 结论

本文提出了基于实时交通数据的交通信息物理系统框架，对利用实时交通信息的动态路径引导的策略和频率进行了研究。仿真结果表明，相对基于拓扑信息的静态引导，动态引导策略具有优势，能够明显地提升道路通行能力，更充分地利用路网资源。然而，在不同的动态引导策略中，对路网中所有车辆进行高频率的引导，相对更长周期的引导并不具有明显优势；周期性引导能够在一定程度上缓解一次性引导中潜在的拥堵问题；各自引导和同时引导两种策略在引导频率较高和较低时具有一定相似性，而在引导频率处于中间范围时，各自引导策略的博弈强度更大。系统仿真实验对路网设置和框架中路径引导策略的选取较为简单，后续可以考虑在真实路网中选用更复杂的一系列引导方案进行验证。此外，将引导频率与道路网络特征相结合，将是本研究的一个很好的延续。