考虑交叉口延误的超路径算法及其应用

杜牧青 鞠姿彦 吕晨希 李东宇 李 嘉 赵国军

(河海大学土木与交通学院 南京 210098)

0 引 言

车辆路径诱导系统向司机提供的最优路径，一般是一条以行驶距离最短或者行驶时间最短为目标的简单路径[1].从易于实现的角度，主流车辆路径诱导系统多采用Dijkstra算法及其改进算法(如考虑启发信息的A*算法)实现路径搜索功能.这类路径算法在本质上都是单路径算法，通常每次搜索只能得到一条最优路径[2].但是，单一的路径诱导并不能考虑道路状况的不确定变化，如拥堵、交通事故的影响，容易将车流集中引导至相同的路线上，导致沿途道路交通量急剧增加形成拥堵，降低了导航系统的实用性和可信度[3].由于单路径算法的不足，寻求有效的多路径算法成为车辆路径诱导领域的热点[4].

目前，常见的多路径生成算法可以被划分为k-最短路径算法和完全不相交路径算法两种[5].研究学者在此基础上提出了许多改进算法.Jin等[6]研究了基于一种有约束弧的时间网络的K条最短路径问题.赵礼峰等[7]结合遗传算法和模拟退火算法，提出了求解K最短路径问题的新算法.一些学者提出采用k-最短路径算法求取多条候选路径供驾驶员选择，将最后的决策权留给驾驶员[8-11]，需要进一步考虑驾驶员对每条路径的个性化评价[12].因此，目前常用的方法是考虑驾驶员不同偏好的多路径诱导，其本质上仍然是将不同最优目标的简单路径作叠加.上述多路径算法通常不考虑网络中延误的不确定性，尤其是信号交叉口延误的不确定性.且从多路径搜索算法的原理而言，驾驶员需要在起点确定方案选择，不能在多方案之间实现路径的转换(除非驾驶员在行驶过程中手动更改路线).可见考虑驾驶员偏好的多路径到并不能够从本质上实现回避延误的问题.因此，如何实现多路径诱导方案中路线的灵活转换，是帮助驾驶员回避交通延误的关键问题.

Spiess等[13]基于公交线路的客流分配模型，最早提出了超路径的概念.在公交模型中，最优超路径被解释为一种最优的乘车策略，包含了起终点之间所有可以降低乘车者等车时间的公交线路集合.Bell[14]进一步考虑了道路网络中每条路段上行程时间的不确定性，将Spiess和Florian的公交超路径应用于道路网络.Bell指出超路径搜索算法是一种特殊的多路径算法，以期望行程时间最小为目标，从实际路网中搜索出起终点之间所有可能最短路径，纳入超路径子网中.Ma等[15]在Bell研究的基础上，提出了加快超路径算法的搜索速度的改进方法.然而，当前适用于道路网路的超路径算法都未考虑交叉口延误对期望行程时间的影响，且未考虑超路径算法在诱导系统的应用，无法为车辆进行实用可靠的路径诱导.

文中基于交叉口信号配时提出了一种交叉口延误的计算方法，重新编写了超路径算法，用于路径搜索.并依据超路径算法“推荐优先绿灯相位”的特点，引入了车路协同技术完善超路径诱导系统.通过车辆和道路的信息交互，超路径诱导系统不断以语音、文字、图像、视频等方式向驾驶者提示前方路况和应做的选择，实现车辆在超路径子网中灵活转换路线，降低交叉口延误.同时依托超路径诱导系统可以实现流量在网络中的合理分配，降低网络整体车辆行程时间，优化网络性能.

1 考虑交叉口转向延误的超路径算法

1.1 超路径搜索原理

超路径考虑路网中延误的不确定性，是由起终点之间所有可能最短路径构成的集合.原始的超路径算法，以终点作为初始搜索节点对路网中的路段逐一搜索，筛选出能降低期望行程延误的路段，组成超路径.超路径搜索结果还包括每个路段在超路径集合中被选择的概率，该概率可作为将流量分派到超路径集合各路段上的比例[16].本文对原始的超路径搜索算法做出改进，对信号交叉口节点进行扩展，以路段的行驶时间与交叉口期望延误之和最小为目标函数，得到起讫点之间的超路径结果.

原始的超路径算法仅考虑路段延误的不确定性，将其解释为离开其上游结点的延误.当考虑交叉口转向延误时，离开结点的延误将取决于车辆经过交叉口的转向行为.由交叉口西侧和北侧进口道进入交叉口的车辆，在从南侧和东侧出口道离开时所受延误影响会有明显不同，即分别为右转对应直行和直行对应左转.两种转向对应的相位配时不同，所受延误影响必然存在差异.基于此，本文在路网中对于有信号控制的交叉口节点进行扩展，克服了原始超路径算法不能反映交叉口转向阻抗的缺点.本文采用网络扩展法表示交叉口的转向行为，将交叉口的各个转向抽象成虚拟路段，用这些路段阻抗代表交叉口转向延误[17].以图1为例，对于单行车道，有四种转向，引入四条虚拟路段；对于双行车道，有十二种转向，引入十二条虚拟路段.

图1 道路交叉口的扩展表示

在扩展的道路网络中，最优超路径问题被描述为以路段行驶时间和交叉口期望延误之和最小为目标函数的数学优化模型，为

(1)

s.t.

(2)

pij∈[0,1],∀(i,j)∈A

(3)

wi≥dij·pij,∀(i,j)∈A

(4)

对于扩展的网络，虚拟路段对应于交叉口的转向，其最大延误dij由信号灯周期性变化引起，令其等于该转向的非绿灯时长.本文假设车辆在随机时刻到达交叉口，并定义交叉口转向ri服务频率fri(fri=1/dri).在超路径中，对于任意交叉口进口道节点i，可能存在多个可用的转向ri，采用集合Ri表示该节点的全部可用转向.进一步，定义交叉口服务频率fi=∑ri∈Rifri，则车辆在交叉口进口道的等待时间期望wi为

(5)

式中：α∈(0,1]，α的取值取决于对交叉口信号配时的估计，在本文中假设α=1.

1.2 算法步骤

因此，本文的超路径算法流程包括以下步骤：

步骤1指定起点r和终点s；创建路段集合L，将路网中所有路段加入集合L中；创建超路径的路段集合H，令集合H初始为空集.初始化各变量如下：

令us=0，yr=1；

令ui=∞，∀i≠s；

令yi=0，∀i≠r；

令fi=0，∀i∈V；pij=0，∀(i,j)∈A；

当dij>0时，令fij=1/dij；当dij=0时，令fij=∞.

步骤2查找集合L中(uj+cij)最小的路段(i,j)，作为当前路段，并将其从集合L中移除.

步骤3若当前路段满足条件ui≥uj+cij，则进入步骤4；否则，返回步骤2.

步骤4更新当前路段(i,j)的上游节点i到终点s的考虑延误的最短行驶时间ui.

若ui=∞，fi=0，则进行如下运算：

否则，进行如下运算：

步骤5更新节点i处的组合服务频率变量和数据，作如下运算：

fi=fi+fij

步骤6将当前路段(i,j)加入到集合H中，此时，若满足条件L=Ø或uj+cij≥ur，进入步骤7；否则，返回步骤2.

步骤7求解路段及节点选择概率：将网络中的全部路段(i,j)，按照uj+cij的值，从大到小排序；根据排序后的顺序遍历全部路段，若路段(i,j)∈H，则进行如下运算：

否则，令pij=0.

从起点r开始，追溯到达终点s的超路径并输出，用于路径诱导决策.

1.3 算例

为了进一步阐明超路径算法的含义，采用方格网型的交通网络并对每个节点进行编号，见图2.以点r为起点，点s为终点，除5、16外其余为信号灯控制的节点，网络中共含有20个节点和31条双车道路段，并将网络图进行虚拟路段展开.图3为路网中有信号控制的各交叉口的信号相位配时图，表1为各路段的行程时间，表2为基于最大悲观期望假设求得的各交叉口转向的等待时间.

图2 实例网络图

图3 交叉口相位配时图

表1 路段的行驶时间

基于最大悲观期望假设，对于各转向路段延误的计算以图2所示T型交叉口2为例进行说明.当行驶路线的前向交叉口编号为r，后续交叉口编号为3时，车辆在交叉口2时需要直行.对照图3的相位图，在交叉口2处的直行只属于第一相位且在一个周期内第一相位的绿灯时间是25 s，黄灯时间是5 s，红灯时间是60 s.由于车辆在黄灯时间和红灯时间内停车等待，因此，确定执行通过的转向延误为65 s.依照这个原理，推出图2道路网络中所有交叉口的转向延误，见表2.

表2 交叉口转向的路段延误

按算法步骤，筛选出超路径，并在每条路段上标注其被驾驶员选择的概率，即诱导系统将车流量分配到各路段的比重，见图4.

图4 实例的路线概率图

由路段概率得出可靠最短路径一共有3条：①r-6-11-12-13-18-19-s，被选择的概率为0.25；②r-6-11-16-17-18-19-s，被选择的概率为0.25；③r-6-7-12-13-18-19-s，被选择的概率为0.5.

算法运行获得的三组结果见图5.由图5可知，在获取的多组解中，用户可以选择这3条出行路径灵活地改变行进路线，降低延误时间.

图5 实例的路线选择图

2 基于车路协同的超路径诱导应用

车路协同基于无线通信、传感探测等技术获取车辆和道路信息，通过车车、车路通信进行信息交互和共享，实现车辆与基础设施之间智能协同与配合[18].车路协同系统由智能交通管理系统、智能通信系统、智能车辆子系统和智能路侧系统四个部分组成[19-20].智能交通管理系统处理由智能车辆子系统和智能路侧系统获取的信息，计算超路径子网中包含的各转向对应的时间，具体分为以下两种情况：

分析比较出时间最短的转向，并推荐给驾驶员.从而保证车辆在交叉口处始终选择优先绿灯相位，最小化交叉口等待延误.图6为车路协同系统的构架，图7为依托车路协同技术的超路径诱导系统的信息交互原理.

图6 车路协同系统构架图

图7 车路协同信息交互

车辆在实际路况中行驶，超路径诱导系统将进行如下诱导.在出发前，车辆路径诱导系统为驾驶员筛选出图4的超路径子网，首先推荐驾驶员沿路段r-6行驶.具体流程如下.

步骤1当车辆行驶接近交叉口6的通信范围时，路侧系统检测到车辆驶入，获取该车辆前直行车辆数Q1直=40辆、直行车流速度v1直=60 km/h、直行车辆流率q直=3 600辆/h、左转车辆数Q1左=30、左转车流速度v1左=50 km/h、左转车辆流率q左=3 000辆/h、该交叉口信号灯当前相位状态信息，将这些信息传输给管理系统.

步骤2智能车辆子系统从多路径诱导方案中获得在当前交叉口的转向策略集合S和车辆当前位置，S包括直行和左转，并将这些信息传输至智能交通管理系统.

步骤3计算车辆到直行和左转的停车线时间.

最后，根据判断条件t左>t直，向智能车辆子系统递直行转向.

步骤3车辆子系统显示路径推荐，车辆接收直行指令，车辆会提前变道，驶离交叉口.

图8为车路协同诱导示意.驾驶员依据图5三组行驶路线进行灵活的路线转换.行驶至下一个路口时，超路径诱导系统继续根据“推荐优先绿灯相位”的原则，从超路径子网中搜索路径推荐给驾驶员，直至行驶至目标点.全部交叉口诱导示意图见图9.

图8 车路协同诱导示意图

图9 完整交叉口诱导示意图

由此可见，在以超路径算法为依托的车辆路径诱导系统中，驾驶员在交叉口可以灵活变换行车路线，达到降低交叉口延误的效果，从而实现“可靠最短”的出行目的.

基于1.3提出的超路径搜索算法，并应用上述车辆诱导方法，从网络总体流量角度分析超路径诱导方案的优点.假设某时段内共计100名驾驶员从起点r行驶至终点s.分别沿超路径算法筛选出来的三条路径(见图5)和时间最短的唯一路径行驶，统计出车辆在交叉口的延误情况，见表3.其中，车辆依据图4的选择比例计算结果，分配在超路径中.

表3 超路径和单路径延误时间对比

由表3的结果表明，在路网中应用超路诱导系统，可降低21.9%的总体平均延误.由此可见，采用超路径诱导策略，可以实现流量在网络中的合理分配，达到网络整体车辆行程时间最短的目的.

3 结 束 语

本文基于交叉口信号配时提出了一种交叉口等待时间的计算方法，并用于超路径搜索.基于最大悲观期望假设利用信号配时方案求得交叉口各转向最大等待时间，进一步通过线性组合求出车辆在交叉口等待期望，避免了处理大量数据，加快了路径诱导方案的搜索速度.在路径诱导方面，提出了在车路协同环境下实现对优先绿灯相位的判断的解决方案，进一步完善了超路径诱导系统，达到了优先推荐绿灯相位的目的.

对于个体而言，驾驶员可以通过诱导系统在超路径子网中灵活改变行驶路线，实现达到降低行程延误的目的.对于整体网络而言，超路径基于交叉口服务频率来合理分配路段车流量，降低整体网络的车辆行驶时间，提升交通网络性能，会产生巨大的经济效益.随着人们对个性化出行需求的增多，超路径诱导系统可引入相应的需求因子变更目标函数，在提高网络性能的同时，实现对用户的个性化诱导.同时，本文通过完善车路协同技术的判断机制，实现了车路协同技术与超路径诱导系统的结合，将在有效降低驾驶员行程延误和完善智能交通诱导体系上发挥巨大作用.

本文基于信号配时计算车辆在交叉口的等待时间时，存在两个假设条件：①最大悲观期望假设，假设车辆在交叉口每个转向的等待时间是红灯加黄灯时间；②独立性假设，假设车辆可选择的相位相互独立，计算在交叉口的期望等待时间时将各转向等待时间线性组合.这两个假设较为理想，可能会导致与实际情况存在一定偏差.今后的研究将上述假设条件做进一步完善，使得超路径搜索结果更加贴合实际路网情况.