基于绿灯时刻图的车辆行驶路径动态导航方法

刘成生,蔡玉宝,张雷元

(公安部交通管理科学研究所,江苏无锡 214151)

0 引言

城市的交通信号控制系统因包含整个城市信号控制运行的实时数据和计划数据，成为了智慧交通建设过程中提供数据支撑和管控策略实施的中心节点[1-2]。尤其是在以车载导航为代表的车联网与车路协同新兴应用场景中，挖掘和利用信号控制系统的信号配时数据对促进交通管理信息互联开放、改善道路交通安全和效率具有重要意义[3]。

传统的路经导航方法通常只考虑距离、时间和路况等因素，而忽略了信号灯控制的影响，只能计算得出信号无管控状态下的相对较优路径[4]。而用户基于这样的导航结果进行驾驶的时候，经常受阻于路口的信号灯控制，从驾驶时间和能耗的角度来说，并非真的最优导航结果[5]。

当前随着车联网和互联网技术的发展，国内导航公司已经尝试与信号灯数据进行对接[6]。山东省烟台市的公安局交警支队联合高德地图，共同打造了一个“交通信号灯信息推送”的解决方案，将信号灯倒计时信息推送到导航屏幕上，增加了用户导航体验，但并未将配时方案与线路规划相结合，相关方案仍然在探索中。

在近期世界物联网大会上奥迪公司展示了其使用车联网技术与信号灯进行路测通信能力，实现了车内信号灯倒计时[7]。奥迪在拉斯维加斯的测试过程中，出现过车载设备漏掉部分信号灯和系统掉线数秒钟的情况；而且为了避免驾驶员完全依赖车内倒计时器而不再注意实际的信号灯，奥迪将倒计时功能设计为距绿灯亮起4秒时倒计时消失，之后的4秒驾驶员必须抬头看信号灯来决定何时起步。

可以看出近阶段无论是车企还是互联网导航公司在信号灯与导航应用的研究阶段为单个路口、实时路口灯色为目标，由于信号配时参数较为复杂还未进一步拆解信号专业配时参数、未实现信号配时参数与导航路径规划结合。

本文将探讨一种基于绿灯时刻图的车辆行驶路径动态导航方法[8]。利用A*算法搜索出导航起点和终点之间所有可行路径，根据城市交通信号控制系统的信号配时参数及信号阶段、相位灯态等实时运行信息获取所有路径上的各个信号灯控路口的绿灯启止时间，结合路口之间的空间距离，建立路径相关的绿灯时刻图；再综合路径长度、到达时间及停车次数，建立路径评估指数，选取评估指数最大的路径作为候选路径[9-10]。通过动态速度引导，确保车辆通过路径上的各个灯控路口停车次数最少，减少因信号灯控制造成的车辆延误和停车造成的能耗损失，提高车辆导航的效率和可靠性并可减少因多次停车造成的尾汽排放。

1 动态导航算法

由于现有的导航方法未考虑信号灯配时参数影响的因素，导航结果并非效率最优。本文将探讨一种基于绿灯时刻图的车辆行驶路径动态导航方法，从而减少路遇红灯的停车次数和行驶延误从而有效提高出行导航的可靠性和稳定性，导航的具体方案主要包括以下几个方面：

(1)搜索所有可行路径

输入导航起点SP和终点EP，利用A*算法搜索出导航起点和终点之间所有的可行路径P1,P2,…,Pn及对应的路径长度L1,L2,…,Ln。基本步骤如下:

第1步：从起点开始，把它作为一个待处理的节点加入到开启列表(OpenList)中；

第2步：寻找起点周围的路口，并把起点设置为这些路口的父节点，验证起点到这些路口的通达性，若存在物理上未连通或连通路径有交通管制无法通行的路口，则将其剔除，剩余的路口加入到开启列表中；

第3步：从开启列表中删除起点，并把它加入到关闭列表(CloseList)中；

第4步：现在的开启列表中存有起点周围可通达的路口，任意抽取一个路口作为路径的下一个探测点；

第5步：检查这个探测点相邻能到达的路口(关闭列表中的路口不予考虑)，把这些路口加入到开启列表中，并把探测点设置为这些路口的父节点；

第6步：把探测点从开启列表中删除，然后把探测点加入到关闭列表中，从开启列表中任意抽取一个路口作为路径的下一个探测点，转到步骤5，一直循环到开启列表的大小为0或者包含终点为止；

第7步：提取所有路径，从终点开始逐层提取父节点Cm,Cm-1,…,C2,C1，所有这些节点组成了路径。

P={SP,C1,C2,…,Cm,EP}

两个路口(节点)之间的距离计算如下：

路径长度计算如下：

(2)获取路口绿灯起止时间

依据《公安交通集成指挥平台通信协议 第2部分：交通信号控制系统》(GA/T 1049.2—2013)标准，连接信号控制系统，接入各个灯控路口的车道、信号相位、信号阶段、配时方案等配置参数，以及信号周期、阶段、相位灯态等实时运行信息。

基于对路径信息的解析，确定车辆导航将经过的每个路口的交通流向，如北直行、南左转等。再根据交通流向并结合路口车道参数配置的进口车道所在的方向及转向，匹配出车辆导航进入此路口的车道。通过相位参数配置的放行车道列表，搜索出车辆在此路口通行所对应的信号相位。

分析信号阶段参数的放行相位列表和阶段时长，查找出车辆在此路口通行所对应的信号阶段及绿灯时长G1,G2,…,Gm。综合路口配时方案时间周期长度、放行阶段列表基础信息，以及路口信号周期与信号阶段、相位灯态运行实时信息，算出该路口相应交通流向的绿灯启亮及结束时间。

(3)建立绿灯时刻图

综合道路通行条件、限速措施及交通安全等因素，设置车辆行驶的最大速度Vmax与最小速度Vmin分别为80 km/h与20 km/h。结合路口之间的空间距离，路径上车辆到达每个路口的时间分别为T1,T2,…,Tm，建立路径相关的绿灯时刻图如图1所示。

图1 路径绿灯时刻图

上图中的V表示车辆在两路口中的平均速度，前置条件为V≤Vmax，当V

TSi=mod[(Offseti+BeforeTimei-T0),Ci]+
Ti-1-mod[Ti-1,Ci]

根据阶段时长G，可算出T0后的该路口绿灯结束时间：

TEi=TSi+Gi

则该路口绿灯的时间区间GRi为[TSi,TEi]。

根据车辆的最大速度和最小速度限制，若车辆从上一个路口的出发时间为Ti-1，则到达本路口的时间区间为[Tmini,Tmaxi]，其中：

Tmini=Ti-1+Di/Vmax
Tmaxi=Ti-1+Di/Vmin

将到达路口的时间区间映射到T0点后第一个周期，则到达时间所对应的信号周期区间Ri为[Tmini,Tmaxi]，到达第i个路口的时间为：

以第j条路径Pj为例，T0为导航开始时间，通过m次计算可以得到Tm为终点路口车辆驶出时间，即为该路径的最终到达时间PTj。当Ri∩GRi≠Φ时，则车辆到达该路口无需停车，由此可判断出车辆通过路径上的各个路口是否有停车，从而得出此路径的总路口停车次数PPj。

(4)确定导航候选路径

综合路径长度Lj、最终到达时间PTj、停车次数PPj建立路径评估指数，将所有可行路径按照评估指数进行排序，找到评估指数最大的路径，即为候选路径。第j条路径的评估指数PIj：

式中：w为评估权重，根据高峰、平峰、低谷时段选取不同权值，建议高峰取0.4，平峰取0.5，低谷取0.6；Li为第j条路径的长度；Lmin为所有路径的最小长度；PTj为第j条路径最终到达用时；PTmin为所有路径的最短到达用时；PPj为第j条路径的停车次数；PPmin为所有路径的最少停车次数；k为单次停车等效时间损耗系数，建议取值10秒/次。评估指数PI值越大则路径越优。

(5)路径导航速度引导

Vi=Di/(Ti-Ti-1)

车辆在通往第i个路口前的引导速度为：

VSi=max(Vmin,Vi)

车辆按照引导速度行驶，可确保在行车安全条件下，以最快时间到达且停车次数最少。

(1)～(5)为正常状况下车辆路径导航，如途中车辆因意外情况未执行到上述引导速度，导致车辆在某个路口实际离开时间与上述计算的离开时间之间存在较大偏离，则将此路径中下一路口作为起点，终点不变，重复(1)～(4)计算出候选路径，然后根据(5)重新计算后续路段引导速度。

2 算法验证

在此将通过一个示例来验证算法的可行性。以城区典型的非垂直交叉路口组成的路网为参考，用本文的算法对图2所示路网进行路径导航。

图2 路网示意图

路网中共有A、B、C…F 6个路口，导航起点位于A路口的西进口SP，导航的目的地位于F路口的北出口EP。

(1)搜索所有可行路径

利用A*算法搜索出导航起点和终点之间所有的可行路径共有3条，具体如表1所示。

表1 路径信息表

(2)建立绿灯时刻图

从信号控制系统中获取路径方向A、B、C、D、E、F各路口的绿灯启亮时间及绿灯时长；针对每条可行路径，建立绿灯时刻图，并计算出到达时间及停车次数。图3为路径1的绿灯时刻图。

根据绿灯时刻图获得其到达时间为104 s，停车次数为2。

图3 单条绿灯时刻图

采用同样方法获得路径2的到达时间为110 s，停车次数为1；

采用同样方法获得路径3的到达时间为118 s，停车次数为2。

(3)确定导航候选路径

假设当前为高峰期，按照评估指数计算公式，评估权重取值0.5计算出各条路径的评估指数，得到表2所示的结果。

表2 评估信息表

(4)路径导航速度引导

根据以上结果，路径1的评估指数最优，选取路径1作为候选路径。

基于绿灯时刻图，采用引导速度计算方法获得各个路段的引导速度值，如表3所示。

表3 导航速度表

经过上述过程的推演，证明了算法的可行性。

3 结论

本文探讨了一种全新的路径导航方法，在传统基于距离、时间和路况的路径选取方法上，动态地融入了交通信号控制实时数据，为导航路径的优化提供了一个全新的实践思路。

同现有的技术相比，具有明显的优点和效果。首先该方法充分结合了信号灯控制信息，能够获得信号管控条件下的最优路径；其次，在行车过程中，提供车辆导航速度引导，确保车辆到达每个信号灯控路口不停车或停车时间最短，减少停车次数和行驶延误，减少停车造成的能耗损失。

同时本文研究方法基于理想路况，未能与互联网实时路况进行数据对接，导航算法偏向于理想化。后期进一步更为准确的线路规划需要结合路况实时数据和信号配时数据对线路规划进行用时预估，由于路况状态是波动变化的，故进一步的导航方法研究更加复杂。