考虑信号交叉口延时的最优车辆路径规划算法∗

胡 林，钟远兴，黄 晶，杜荣华，张 新

(1.长沙理工大学汽车与机械工程学院，长沙 410114； 2.湖南大学，汽车车身先进设计制造国家重点实验室，长沙 410082；3.长沙理工大学，工程车辆安全性设计与可靠性技术湖南省重点实验室，长沙 410114)

前言

随着智能交通(ITS)的发展，最短路径规划已成为解决道路交通拥堵和交通安全的一项重要途径。同时，随着科技的发展，车联网(V2V)和车路协同(V2I)技术在提高道路交通运输的安全、环保和可靠性等方面得到了大量应用。而在城市道路网中，由于信号交叉口(指设置有交通信号灯的交叉口，下同)的大量存在，进一步加剧了交通拥堵和交通延时，并造成严重的环境污染。通过在车辆上安装无线通信设备，使其能与邻近车辆和道路基础设施进行通信，可以辅助车辆安全、环保和快速地通过交叉口。因此，在动态路径规划研究中，有必要将车联网和车路协同技术与交叉口的等待时间结合起来考虑。

现有路径规划中，国内外学者对信号交叉口延时进行了大量研究[1-4]。YANG和Miller-Hooks[5]分析了随机时变路网中由于信号灯导致的额外延时。Khanjary等[6]提出了同步交通灯路网中考虑街道通行时间和绿灯等待时间的标号设定算法。杨帆等[7]提出了信号交叉口处等待时间函数，并将其引入算法中，建立新的标号算法。周熙阳等[8]在此基础上，针对不同转向类型构建信号交叉口等待时间模型，提出了考虑信号交叉口转向类型的CMTA∗算法。但该算法要求确定出发时刻，预知所有交叉口交通灯的当前相位时间点，假定路段行程时间固定并忽略车辆路段行驶延误，难以实际应用。

此外，对车辆通过交叉口的速度优化也进行了广泛的研究[9-11]。Mandava等[12]提出在通过车辆与道路设施的通信预先获取前方交通灯信号相位和配时信息的基础上，对车辆进行动态速度规划，使车辆尽可能避免加速、减速和怠速状态，降低车辆的油耗和尾气排放。Rakha等[13]提出了旨在提高燃油效率的环保驾驶框架，通过车辆与道路设施的通信提前获取交通灯信号相位和配时信息，用以调整车辆通过交叉口的策略，从而达到降低车辆油耗的目的。Butakov等[14]则结合驾驶员的偏好和习惯对车辆通过交叉口的速度进行优化，从而降低油耗，缩短等待时间。安实等[15]提出了一种基于多级可变速度限制的信号交叉口绿色驾驶控制方法，以信号交叉口为背景，对车队中的头车进行速度限制。林培群等[16]在分析车联网环境技术特征的基础上提出交叉口交通流分区控制思想(变速控制区和匀速控制区)，并建立系统优化的数学模型。徐彪等[17]构建了基于DSRC的连续交叉路口通行辅助系统，并提出了连续交叉路口的通行车速计算方法。

综上所述，现有考虑交叉口等待时间的路径规划研究未对车辆通过交叉口的速度进行优化，而聚焦于对车辆通过交叉口的速度进行优化的研究也未将其与全路段的路径规划结合起来。本文中拟将信号交叉口的等待时间和车辆加速通过交叉口结合起来，提出考虑快速通过交叉口的最短路径规划算法。首先，根据浮动车数据获取路网中各路段的车辆平均行驶速度。然后，建立基于马尔科夫链的交通灯转换模型，并通过车辆加速通过交叉口来考虑绿灯时间的延长，以此构建车辆快速通过交叉口的等待时间模型。最后，结合A∗算法，提出一种考虑快速通过交叉口的等待时间的改进A∗算法。

1 最优车辆路径规划算法

1.1 路网模型构建

在动态分时路网[18]的基础上构建城市道路网模型，以 G＝(N，D，V，T)表征路网，其中 N＝{1，…，n}表示节点集合(即交叉口)，D＝{dij(t)｜(i，j)∈N}表示连接各节点之间的弧段长度，V＝{Vij(t)｜(i，j)∈N}表示各弧段的实时速度，T表示车辆从起点到终点的行程时间。城市路网中，车辆的行程时间主要由路段行驶时间和信号交叉口等待时间组成。节点i到j的行程时间包括路段dij的行驶时间和交叉口j的等待时间，如图1所示，即有

式中:dij和Vij分别为交叉口i到交叉口j之间路段的距离和车辆平均速度；Wj为车辆在交叉口j处的等待时间。

图1 车辆通过交叉口示意图

1.2 路段行程时间计算

现在，越来越多的车辆上安装了卫星导航和无线通信设备，通过车上安装的卫星导航模块和通信模块，定期向信息中心发送车辆位置、速度和时间信息，对这些信息进行分析处理可实时获取各路段的交通流信息。假设t时刻一条道路上的浮动车辆数为 n，每辆车的瞬时速度为 Vi(i＝1，2，…，n)，则该路段在t时刻的车辆平均速度为

将卫星导航数据与地图进行匹配[19]，可得到每一路段dij的车辆实时速度Vij，则各路段的行程时

1.3 基于马尔科夫链的交通灯模型

对于一个4相位的信号控制交叉口(周期时长为Tc)，其中每一相位所对应行驶方向的交通灯有两个状态，即红灯和绿灯状态(为简化计算，将黄灯时间纳入红灯状态)，如图2所示。红灯和绿灯交替转换的过程可看成一个按两态连续时间马尔科夫链规律转变的过程。下一时段交通灯的状态与过去的情况无关，只取决于当前状态，具有明显的马尔科夫性质。

图2 交通灯相位示意图

计算交通信号灯稳态概率分布的步骤如下。

(1)确定状态转移概率矩阵Pij(t)

定义Xij(t)为车辆在路段(i，j)行驶时前方交通灯j的状态。Xij(t)＝g时，车辆无需等待；Xij(t)＝r时，车辆需要等待下一周期绿灯的到来。

假设当前状态为绿灯，记为状态g(绿灯时长为g)，绿灯结束后转为红灯状态，记为状态r(红灯时长为r)。当前状态为g下一刻(经过t)状态仍为g的概率为Pgijg(t)，即有

相应地定义当前时刻为绿灯下一刻转为红灯、当前为红灯下一刻仍为红灯和当前为红灯下一刻转为绿灯的概率分别为t)，(t)和t)。

式中:Pr为交通灯是红灯状态的稳态概率；Pg为交通灯是绿灯状态的稳态概率。

1.4 车辆加速通过信号交叉口模型

车辆通过交叉路口示意图如图3所示。由图可见:当前方交通灯为绿灯状态且绿灯剩余时间足够时，车辆无需等待，以路段实时平均速度Vi通过交叉口；当前方交通灯状态为红灯时，车辆需要等待绿灯相位的到来。通过车路协同方式(V2I)，车辆在与前方交叉口距离S时就能知道交通灯的当前相位及其剩余时间。这样，当前方交通灯即将由绿灯转变为红灯时，车辆可加速通过以避免交叉口的等待。假设车辆距离交叉口停止线为S时，车辆以速度Vi行驶，到达停车线的时刻为t2；车辆以加速度a1加速到最大速度Vmax行驶时，到达停车线的时刻为t1，则有

图3 车辆通过交叉口示意图

(2)确定稳态概率P

由马尔科夫链的无记忆性规律可知，稳态概率只取决于交通灯状态转移概率矩阵Pij，与初始状态无关。可求得稳态概率为

值得注意的是，当车辆加速通过前方交叉口时，须考虑车辆前方是否有车和前车与本车的车头间距(本文中不考虑超车的情况)。本车与前车的车头时距示意图如图4所示。由图可见，本车距离前方交叉口S时加速到最大速度Vmax行驶，经过t1时间车辆刚好驶过停车线，若前方有车且以速度Vi行驶，本车与前车的车头间距L应满足:

式中:d为本车通过交叉口停止线时与前车的最小安全车距；a2为车辆的减速度，本车通过交叉口停止线后即减速至路段平均车速；D为车辆跟驰的最小车距。

图4 本车与前车的车头时距示意图

车头时距t为

1.5 车头时距的确定

当本车与前车的车头时距较大时，本车可加速通过交叉口以避免停车等待；当本车与前车的车头时距较小时，本车不能加速通过交叉口。根据信号交叉口处的车辆到达规律[20]可知，车头时距的分布模型有负指数模型、移位负指数模型、威布尔模型和爱尔朗模型等。本文中采用三参数的威布尔分布模型来描述车头时距的分布。

根据威布尔分布提出的车头时距大于等于临界车头时距的概率分布:

式中:P(h≥t)为相邻两车的车头时距h大于或等于临界车头时距t的概率；α，β和γ为分布参数，α为起点参数，β为形状参数，γ为尺度参数。

威布尔分布的概率密度函数为

图5为采用MATLAB绘制的不同分布参数下的威布尔概率密度曲线。

根据不同车流对应的车头时距分布，可得该车流产生的大于临界间距的概率为

图5 威布尔分布概率密度曲线

通过对各交叉口的车辆到达规律进行统计分析，采用MATLAB对车头时距的分布函数进行拟合，即可算出不同交叉口到达车流大于所需临界间距的概率。

图6为某交叉口特定时间段内车头时距的统计分布及其概率密度曲线，其分布参数分别为:α＝2.440，β＝2.661，γ＝0.342。

图6 车头时距概率密度分布

1.6 考虑快速通过信号交叉口的车辆等待时间

由于车辆到达交叉口的随机性和不确定性，可假定在交通灯信号周期内的各个时刻车辆到达交叉口的概率是均等的。当前方交通灯为绿灯状态时，车辆等待时间为0；当前方交通灯为红灯状态时，车辆需等到红灯结束绿灯启亮时才能通行，根据概率，等待时间约等于红灯时间的一半。

考虑当前方交通灯即将由绿灯变为红灯，同时车头时距满足要求时，车辆可以在该绿灯相位时间内快速通过交叉口，可理解为对绿灯时间的拓展。故可将交通灯稳态概率(Pr，Pg)修正为(P′r，P′g)。其中 P′r和 P′g分别为

此外，车辆通过交叉口后的行驶方向可分为直行、左转和右转，本文中假定右转无专用相位，故当选择右转时，车辆在信号交叉口的等待时间为0。

图7 算例路网

表1 算例路网中各路段长度 m

1.7 实时最短路径算法

A∗算法[21]是求解最短路径最有效的直接搜索方法，它通过构造启发式函数来寻找从起点到终点代价最小的节点。对于节点n的估价函数的一般形式为

式中:g(n)为起始节点到当前节点的实际代价；h(n)为当前节点到目标节点的估计代价。

对A∗算法进行拓展，在A∗算法的基础上考虑快速通过交叉口的等待时间，得到的估价函数为

式中:f(j)为弧节点j的估计代价；g(j)为从初始弧节点到达弧节点j的实际代价；g(i)为从初始弧节点到达弧节点i的实际代价；dij为路段(i，j)的长度；Vij为路段(i，j)的平均车速；Wj为信号交叉口j的等待时间；D(j)为弧节点j到目标节点的欧式距离；Vmax为路网最高限速值。

2 仿真分析

首先，设计一个简单路网来阐述本文算法的实现过程。该路网包含了25个交叉口和40条路段，如图7所示，算例设置如下。

(1)路网的40条路段均为双向通行，路网的最高限速为60km/h，各路段长度如表1所示。路网中各路段车辆的平均通行速度实时更新，图中黑色路段(7-8，8-13，17-18 和18-19)代表拥堵路段，其平均通行速度为25km/h，灰色路段(9-14)为基本畅通路段，其平均通行速度为35km/h，其余路段为畅通路段，平均通行速度为45km/h。

(2)试验车辆与各交叉口的交通灯进行通信，通信距离设为200m，车辆在该距离范围内可获取前方交通灯的实时相位及其剩余时间。

(3)交叉口各信号相位相互独立、已知且固定，部分交叉口信号配时参数如表2所示。

表2 各节点交叉口信号配时表

(4)交叉口的到达车流符合分布参数为α＝2.2，β＝2.5和γ＝1.7的威布尔分布，其概率密度曲线如图8所示。

图8 威布尔概率密度曲线

根据本文中提出的算法计算所得路径为:21-16-11-6-1-2-3-4-5，路径包含了7个交叉口，其中一个右转，6个直行，路段总长为4.65km。由各信号交叉口的相位配时参数可计算出各交通灯红灯、绿灯状态的稳态分布概率，当信号灯即将由绿灯变为红灯时，位于信号交叉口距离S范围内的车辆可加速到最大限速通过交叉口，结合所需车头时距的概率可求出当前交通灯的绿灯拓展时间，进而求出车辆在各个信号交叉口的等待时间，如表3所示。最后，将交叉口等待时间加上路段行驶时间可得到车辆通过路径的总时间为535.9s。

表3 各节点交叉口等待时间s

为仿真真实场景，本文中通过开源地图Open-StreetMap下载长沙市某片区地图作为算例路网，该路网包含路段65条，节点40个。采用Visual C++6.0对算法进行编程实现，并通过城市交通仿真软件SUMO[22]进行仿真。

使用传统A∗算法所得路径如图9中虚线所示，路径包括7个交叉口，其中1个左转，1个右转，5个直行，路段总长为3.42km，通行所用时间为453.6s。根据本文中提出的改进A∗算法计算所得路径如图10中虚线所示，路径包含了8个交叉口，其中1个左转，3个右转，4个直行，路段总长为3.74km，通行所用时间为433.7s。

图9 路径1(A∗算法)

图10 路径2(改进A∗算法)

由表4可以看出，改进A∗算法得到的路径长度比A∗算法长9.4%，但得到的行驶时间却比A∗算法减少了4.4%。

表4 不同算法所求路径总费用

选取不同的起点和终点进行多次仿真，得到A∗算法和改进A∗算法仿真结果，如图11所示。由图可见，考虑快速通过交叉口等待时间的改进A∗算法所得路径的通行时间明显短于A∗算法。这是因为传统A∗算法侧重于考虑路段通行时间，而本文中提出的考虑快速通过交叉口的改进A∗算法则兼顾了考虑交叉口的等待时间，并通过车路协同的方式在车辆接近交叉口时优化其速度，使其快速通过交叉口，减少车辆在交叉口的等待时间。

图11 仿真结果对比

3 结论

本文中提出了考虑快速通过信号交叉口的车辆最短路径规划算法。通过构建基于马尔科夫链的交通信号灯模型，考虑前方交通灯即将由绿灯转变为红灯，同时车头时距大于临界阈值时，车辆加速通过交叉口，在此基础上结合A∗算法，提出了考虑信号交叉口等待时间的改进A∗算法。算例验证表明，相比传统的A∗算法，该算法所计算出的路径更优，耗时更短。本文中提出的算法适用于交通灯密集的城市道路网，且路段交通灯越密集，该算法的优越性越明显。不过，算法也存在一定的局限性，在不同时间段内信号交叉口的到达车流具有明显的差异。在交通流高峰时间段内，车流密集，车头时距小，车辆加速通过交叉口的概率也小。

后续研究中，须进一步考虑4个方面的问题:(1)考虑信号交叉口干线协调，对相邻交叉口的相位差进行协调控制；(2)考虑不同时间段的交通流分布，进一步分析交通流影响下的车头时距，提高算法的精确性；(3)考虑路段最大限速和车辆加速度对交叉口绿灯拓展延时的影响；(4)在交通流大的情况下，须考虑车辆排队的延时。