基于城市道路交通环境演变的ECEA路径规划算法

温惠英 林译峰 吴昊书 蒋晗 吴嘉彬†

(1．华南理工大学 土木与交通学院,广东 广州 510640;2．华南农业大学 林学与风景园林学院,广东 广州 510640)

在城市路网中，交通流状态受多种因素影响，随时间推移不断变化，例如交通事故、信号控制、路网结构、通行能力、出行规律、驾驶行为特性、交通拥堵、恶劣天气以及自然灾害等。由于交通事件具有明显的随机性与突发性，难以提前预测其发生时间和地点，故交通事故的应急救援工作不可避免地存在滞后性。因此，如何在复杂多变的城市路网交通环境中快速地执行救援工作是应急救援环节中最为关键的问题[1-3]。路径规划作为应急救援的重要环节，影响救援行程时间长短与稳定性。稳定可靠的救援路径有利于救援人员在尽可能短时间内拯救更多的生命，及时控制事故严重性与影响范围，有效降低经济损失。

常用的路径规划方法有两种，即静态路径规划和动态路径规划。作为经典的路径优化方法，静态路径规划的基本思想是在静态交通路网下搜索两点间的最短路径。已有大量学者钻研静态路径优化方法相关理论，并取得了丰富的研究成果与实践经验。多数静态路径规划方法的研究是基于具体的应用场景，解决实际问题，例如应急救援[4-11]。在应急救援路径规划中，静态路径优化的应用较为普遍，常用的方法有Dijkstra算法、蚁群算法、SPFA(Shortest Path Faster Algorithm)、双层优化方法等，其中最常见的是Dijkstra算法[12-14]。

在实际的城市路网中，路径规划受到动态交通环境的影响，而交通环境的演变具有显著的时空特性。在时变特性方面，路网交通环境随时间演变，受路段交通流状态与交叉口通行规则的影响，如常发性交通拥堵、信号控制等[15-16]。在空间分布特性方面，同一时刻下同一路段不同方向或不同路段的交通流状态差异明显。考虑路网动态交通环境对路径规划的影响，学者们致力于研究如何提升动态优化方法的实时性与优化性能，而在线优化方法(OLRO)是解决动态路径规划问题的主流手段[17-18]。在线优化方法的基本思想是基于当前路网交通环境下快速寻找起终点间的最短路径，并根据路网交通环境的演变实时更新剩余优化路径，直到车辆抵达目的地。常见的在线优化方法有单源优化算法、启发式算法与机器学习算法等[19-23]。然而，OLRO方法仅考虑当前路网交通环境状态，忽略了路网交通环境的未来演变趋势对路径优化的影响，将动态路径规划视为多个静态路径规划在不同时间维度的简单组合，容易导致多余的绕行并增加行程时间。

为解决该问题，Hu等[24]提出了一种协同优化方法(CEPO)，在给定的动态路网环境下解决路径规划问题。为进一步研究路网动态因素与不确定性对路径规划的影响，Wen等[25]集成CEPO和OLRO优化特性，提出了一种定时协同优化方法(TCEPO)，在预测路网状态变化的基础上，基于交通环境演变趋势协同优化救援路径，并定时修正不确定性对路径规划造成的影响,以增强行程时间稳定性。但是当数据条件受限时，TCEPO的误差会随着计算过程的推进而增加，降低优化效果。受TCEPO方法的启发，文中在传统A*算法框架的基础上引入TCEPO模型优化原理，基于城市路网交通流的动态演变和可预测性，提出了一种可扩展协同进化算法(ECEA)。该算法可用于探索城市道路交通环境变化下应急救援路径规划问题的解决方案，以提高应急救援效率及其鲁棒性[26-29]。

1 城市路网交通环境运行特征

1.1 交叉口运行特征

为提高交叉口安全水平与通行效率，城市路网交叉口常配备较为先进的信号控制设施。尽管救援车辆到达信号控制交叉口时可不受信号灯约束，但其运行状态受限于前方社会车辆在交叉口的排队或减速行为，常被迫停车或减速，进而产生行程延误[30-31]。若救援车辆通过无信号控制交叉口，则可能因减速避让其他机动车、非机动车或行人等交通参与者而产生行程延误。因此，在城市路网行驶过程中，救援车辆通过交叉口时产生的交通延误往往难以避免且其影响不容忽视，是救援行程时间的重要组成部分。

1.2 路段交通流的时空特征

由于道路类型、地理位置、路段长度、路段限速等道路条件存在显著差异，路网交通流在时间与空间分布上具备不均衡性，这种不均匀的现象可概括为交通流的时空分布特征。在微观层面，该特征与驾驶员行为特性存在密切联系，可从驾驶员行为角度进行描述与解释[32-33]。鉴于路径规划效果与路网交通流演变息息相关，文中主要从以下3个方面对交通流演变进行剖析与定义：

(1)由于大多数城市道路未设置专用的应急车道，救援车辆在城市路网中行驶时易受到周围社会车辆的影响。不同驾驶员的驾驶行为差异化明显，对于安全驾驶的理解存在较大偏差。部分不良驾驶行为容易扰乱交通流的稳定运行，甚至会造成路段上的交通拥堵，是造成交通流紊流、不连续的主要原因，例如突然变道、连续换道等[34-35]。

(2)交通流时间分布差异是指同一路段的交通流在不同时间段存在的差异。例如，若某一路段受到交通拥堵影响，其车流平均速度将在短时间内迅速下降；当拥堵范围与负面影响随着时间推移而逐渐消散，其车流速度将逐渐恢复至正常。

(3)交通流空间分布差异是指同一时刻下不同路段或同一路段的不同方向车流平均速度存在的偏差。一般而言，市中心区域车流较多，交通负荷较大，对应路段上的交通流速度相对较低。相对而言，城市郊区车流密度与道路负荷较小，交通流运行速度相对较高。

2 ECEA算法

2.1 目标函数

在城市路网中，交叉口被视为连接多条路段的“节点”。尽管节点间的路段长度固定，但其交通环境随时间动态演变，影响车辆群行驶快慢。车辆通过某一路段的行车时间由路段长度、交通流状态与驾驶员特性等多种因素共同决定。换言之，距离最短的路径不一定等同于行程时间最短的路径。由于城市应急救援对出行时效性具有严格的要求，故行程时间最小化是应急救援路径规划的主要目标，而非行驶距离最小。其目标函数可用下式表达：

minC=f(O,D,R*)

(1)

式中，C表示救援行程时间，R*表示求解的优化路径，f是计算路径R*行程时间的函数，O表示路径R*的起点，D表示路径R*的终点。

2.2 参数定义

为方便理解本文所涉及参数的含义，表1列出了本文部分参数及其实际含义。

表1 参数及其含义Table 1 List of symbols and meanings

2.3 基本原理

本文所提ECEA算法原理包括两部分：一是搜索并确定车辆行驶的下一目标节点，二是随车辆行驶更新路径。如图1所示，ECEA算法通过预测路网交通环境状态的变化计算子路径，根据子路径筛选车辆行驶的下一目标节点；当车辆到达目标节点时，ECEA算法将根据路网交通环境的变化对子路径进行修正和更新，直至车辆到达终点。

图1 ECEA算法基本原理Fig.1 Illustration of the basic idea for the proposed ECEA

图1中，子路径的计算与下一目标节点推导由ECEA算法中节点的F值确定，即：

F(i)=G(i)+H(i)

(2)

式中，G(i)表示从当前位置到节点i的移动代价，H(i)表示从节点i到终点的估算代价。在寻找下一目标节点的过程中，ECEA算法比较当前位置节点搜索范围内所有备选节点的F值，通过计算当前位置节点与F值最小的备选节点间的子路径，推导并行驶至下一目标节点，并随车辆行驶实时更新路网交通环境，不断迭代更新子路径。若终点在搜索范围内，则通过回溯方法得到完整的优化路径。因此，ECEA算法不仅具有根据实时修正路网交通环境演变的特性，还考虑了未来路网交通环境演变趋势对路径规划的影响，进而实现救援路径与路网交通环境的协同优化。

2.4 算法步骤

2.4.1 优化流程

ECEA算法的优化流程如图2所示。步骤1到步骤7表示在预测路网交通环境条件下筛选最佳下一目标节点的过程；步骤8到步骤12给出了救援车辆行驶至下一目标节点的实际运算过程。步骤1初始化变量；步骤2标定路网起点为当前节点；步骤3根据当前节点和设定的搜索层数，通过备选节点搜索模块筛选出所有的备选节点np；步骤4运用式(2)计算步骤3中所有备选节点np的F值，然后回溯推导得到路径R(nc,np)，拼接R(Oc,nc)与R(nc,np)形成完整路径R(Oc,np)，并通过对比更新机制操作Olist：若np不在Olist中，则将np加入Olist，并将F(np)记录为Fm(np)；若np已经在Olist中，则通过式(3)判断是否需要更新Fm(np)。

图2 ECEA算法步骤Fig.2 Algorithm steps of ECEA

(3)

式中，Fm(np)表示节点np原有的F值，F(np)表示节点np在当前步骤计算得到的F值。若F(np)

2.4.2F值计算模块

由式(2)可知，F值由G值和H值组成。为了有效筛选最佳的下一目标节点，本文中引入波纹扩散算法(RSA)协同路网交通环境变化，推导当前节点与备选节点之间的G(i)值，优化G(i)值的计算过程。作为一种新兴的算法，RSA算法在计算路网两点间的移动代价时有速度快、精度高等优势，其协同优化机制与路网交通环境演变高度契合，具体运算过程如图3所示。

图3 RSA算法运算流程图Fig.3 Flowchart of ripple spread algorithm

图3中，T=0表示当前时间单元，k=n(n=1,2,…,6)表示在当前时刻下往后预测的第n个时间单元。路网节点存在4种状态，即未激活、等待、已激活和死亡，且所有节点初始状态均为未激活。k=1时，波纹从起点处激活向四周邻近节点扩散。k=2时，从1号起点激发的波纹到达4号节点并将其激活，波纹继续向邻近未被激活的节点扩散。k=3时，1号节点波纹激活2号节点后产生新的波纹，新生波纹在2号节点停留一段时间，模拟车辆到达交叉口的排队行为，进入等待状态。k=4时，2号节点转为激活状态，其波纹向邻近节点扩散，并激活未被其他波纹访问过的节点。k=5时，波纹抵达3号节点，因其所有邻近节点均被波纹访问过，故停止激发新的波纹，转变为死亡状态。波纹的扩散过程随着时间推移不断进行，其扩散速度与动态演变的路网交通环境协同变化。k=6时，从6号节点激发的波纹到达终点，终止波纹扩散过程，并从终点开始回溯该波纹遍历节点的记录，得到起点与终点节点间的最优路径。

引入RSA算法优化G值，计算式为：

(4)

式中，t表示在预测道路交通环境下从节点nc到节点np所需要经历的时间单元数，T表示救援车辆到达节点nc时所处的时间单元，CT|T+k(nc,np)表示在预测时间单元T+k内通过路段(nc,np)所需的行程时间。G值从起点开始不断迭代计算，该过程与道路交通环境协同演变，起点O的G值为0，即G(O)=0。

在实际行驶时，G值根据预测路网交通环境数据推导得到，与实际G值存在偏差。因此，在确定下一节点后，ECEA算法基于实际路网交通环境数据迭代更新G值。

H值的计算式为：

(5)

式中，L(np,D)表示从节点np至终点D的直线距离；Vave表示畅通路段车流的平均行驶速度。H值的计算可参考A*算法原理，此处不作赘述。

2.4.3 备选节点搜索模块

由ECEA算法优化流程可知，在计算G值时，首先需要根据当前节点位置和搜索层数搜索所有备选节点np。假设集合M用于记录G(i)值计算过程中搜索范围内的所有备选节点，令l表示G(i)的搜索层数。在ECEA算法中，l≥1，如图4所示。搜索过程需要满足以下条件：

图4 不同搜索层数的备选节点Fig.4 Candidate nodes of different search levels

(1)在搜索开始前，将当前节点加入到M中，并将其标记为已被搜索过的节点，随后进行第1层搜索。

(2)在每一层的搜索中，ECEA搜索的对象是在上一层搜索中所得到的集合M中的所有备选节点，基于上一层备选节点迭代搜索邻接节点，若邻接节点未被遍历搜索，则将其视为新增节点。

(3)每一层搜索结束后，更新集合M中的所有备选节点。将集合M中的所有原有备选节点移除，再把该层搜索得到的新增节点加入到集合M，并令l的值增加1。当l值达到预设值时，集合M中所有节点均为该层的备选节点，即G(i)值的计算对象。

3 实验分析

本文在矩形区域内随机均匀设置N个节点生成城市路网拓扑结构，路径起点为路网左下角，终点为路网右上角。仿真路网规模分为4类，即N∈{400，900,1 600，2 500}。为模拟城市道路交通实际运行环境，提出以下3种假设：

(1)交叉口的运行特征决定了救援车辆通过交叉口时会产生行程延误。令d(i)表示节点i的延误，取值范围为[20,60]，单位为s。当波纹到达节点i时，需要等待d(i)时间，其行程时间随之增加。

(2)城市路网交通拥堵随着时间推移分为扩散和消散两个过程。每隔10～15个节点设置一个交通拥堵中心点(简称“中心点”)，即拥堵源头。拥堵范围随时间推移而扩散，中心点的邻接节点逐渐成为拥堵节点，并不断扩散传递拥堵状态，此时节点延误是畅通状态下的两倍。当拥堵区域扩张至一定规模时，拥堵开始消散，拥堵区域由外向内逐层收缩至中心点为止。

如图5所示，黄色区域表示城市路网的拥堵区域，根据拥堵的变化方向，在同一时刻下，区域1和区域4正在扩散，表示拥堵正在不断传递；区域2和区域3正在收缩，表示拥堵正在逐渐消散。

图5 拥堵区域变化示意图Fig.5 Congestion evolution process in network(N=400)

(3)道路交通环境变化体现为各路段车流平均速度的动态演变。在各时间单元内生成各路段的平均速度，且路段初始平均速度V0服从N(40,5)的正态分布模型，取值范围为[20,60]，单位:km/h。令时间单元T的长度为60 s。根据城市路网交通流的时空特征，随着时间单元的推移，各路段平均速度在[-4,4]km/h范围内随机变化。若路段处于拥堵状态，路段平均速度将下降至[0,5]km/h的范围。

3.1 实验1 算法搜索层数优化分析

为了探索搜索层数对路径规划优化性能的影响，实验1以N=400路网为例，选取搜索层数范围为[1,10]，并忽略预测误差对优化结果的影响。实验所用计算机的参数如下：CPU处理器型号为Intel(R)Core(TM)i5-6500U，内存为4 GB，操作系统为Windows 64bit。搜索层数优化分析结果如图6所示。

由图6(a)可知，搜索层数较小时，行程时间随着搜索层数的增加呈现快速下降的趋势，当搜索层数增加到5层时，行程时间最小；5层之后，继续增加搜索层数，行程时间无明显变化。由图6(b)可知，随着搜索层数的增加，算法运算时间基本上处于平缓波动状态。根据ECEA的计算原理可知，计算时间的决定因素有二：一是优化次数，二是遍历备选节点所需时间。当搜索层数增加时，一方面，下一目标节点的选择范围扩大，遍历时间增加；另一方面，优化次数可能会减小。因此，ECEA算法的计算时间与搜索层数无明显正或负相关性。为提高算法优化性能，降低运算负荷，本文选取算法搜索层数为5，用于实验2与实验3的计算。

图6 ECEA不同搜索层数的性能分析(N=400)Fig.6 Performance analysis of different search levels for ECEA(N=400)

3.2 实验2 无预测误差下的算法性能分析

随着计算机科学的快速发展，路网交通环境演变趋势或多或少可利用交通流预测算法进行预测。为凸显ECEA算法在城市路网的优化性能，选择TCEPO、A*算法与Dijkstra算法作为对比算法，其中TCEPO是协同优化方法，A*算法与Dijkstra算法是在线优化方法。图7给出了ECEA、TCEPO、A*算法与Dijkstra算法在无预测误差时不同路网下20次测试的平均计算结果。tTT表示行程时间,min;tCT表示运算时间,s;lPL表示路径长度,km;δTD表示行程延误,min。

δTD的计算方法如式(6)所示，Vd表示城市道路设计行驶速度，本文取Vd=60 km/h。

(6)

由图7(a)可知，在tTT方面，ECEA优于TCEPO、A*算法与Dijkstra算法。ECEA输出路径的行程时间比TCEPO短8.48%～30.9%,比A*短18.74%～43.3%，比Dijkstra算法短22.46%～35.18%。

由图7(b)可知，在tCT方面，ECEA最长，TCEPO次之。随着路网规模的扩大，4种算法的计算时间逐渐增加。尽管ECEA的计算时间最大，但并不影响ECEA规划路径的应用可行性。

由图7(c)可知，在lPL方面，TCEPO最短，ECEA次之。其中，ECEA比A*算法短了7.07%～25.37%，比Dijkstra算法短了4.81%～19.15%。

图7 4种算法在无预测误差时不同路网下的计算结果Fig.7 Average results of four algorithms under different networks without predicted errorECEA TCEPO A*Dijkstra

由图7(d)可知，在δTD方面，ECEA最小，比TCEPO降低17.65%～51.48%，比A*算法降低26.9%～54.55%，比Dijkstra算法降低33.33%～48.05%。

3.3 实验3 不同预测误差下的算法性能分析

尽管各类先进的交通流预测算法层出不穷，但其预测结果难以达到绝对精确。为清晰表示路段车流平均速度预测值与实际值之间的关系，引入速度预测误差参数φ，则有：

VT+k(i,j)=VT|T+k(i,j)×(1+φ)

(5)

式中，VT+k(i,j)表示路段(i,j)在时间单元T+k的路段车流平均速度实际值；VT|T+k(i,j)表示路段(i,j)在预测时间单元T|T+k的路段车流平均速度预测值。图8分别给出了4种算法在不同预测误差下20次运算的平均结果(φ=[ 0.05,0.1])。

图8 4种算法在不同预测误差下的平均结果Fig.8 Average results of four algorithms under different predicted error φ

由图8可知，在考虑预测误差的情况下，ECEA在行程时间和行程延误方面仍优于TCEPO及其它两种在线优化方法，在运算时间上虽为最长，在路径长度上要优于A*算法和Dijkstra算法。尽管ECEA在φ=0时优化效果最小，但始终保持降低20%左右的行程时间。这主要是因为ECEA每次达到目标节点时自动更新路网交通数据，重新规划剩余路径，以修正累积的预测误差。且随着预测误差的增加，ECEA的优化幅度总体上逐渐增加。例如，相比于TCEPO，在φ=0时，ECEA缩短了20.5%的行程时间，当φ=0.05时，优化幅度达到23.65%，φ=0.10时优化幅度达到27.35%。这说明ECEA对于预测误差的包容性更好，在不同的预测误差下，能够始终保持较好优化性能。

图9是4种算法分别在不同预测误差条件下运算输出20次tTT结果的分布状况。ECEA稳定性优于TCEPO、A*算法和Dijkstra算法，且所有运算结果在较小范围内波动。且随着路网规模的扩大，ECEA优化效果明显。由此可见，ECEA在城市道路交通环境动态演变下优化路径的抗干扰能力更强，更适合应对城市道路交通环境中难以预测的突发状况。

图9 4种算法在不同路网规模的行程时间稳定性对比Fig.9 Comparative results of travelling time reliability for four algorithms on different road network scales

4 讨论

在行程时间方面，ECEA要优于TCEPO、A*算法和Dijkstra算法。这主要是因为ECEA的协同优化机制能够提前避开拥堵区域，避免不必要的绕行，从而减少行驶过程中所遭遇的拥堵延误。此外，相比于TCEPO，ECEA优化间隔短、搜索范围大，能够在尽可能获取最佳下一目标节点的同时有效控制预测优化和协同计算过程中的误差。基于在线优化的传统方法在每一步计算时，仅考虑当前时刻的路网状态规划救援路径，忽略未来路网交通环境演变对路径规划造成的干扰，尤其是在应对拥堵演变方面存在严重的时滞性，得到的结果是仅在当前时刻下的最优解。

在运算时间方面，ECEA在不同路网规模中的计算时间均为最长，且随着路网规模的扩大而增加。这主要是因为较大的搜索范围使得ECEA每一子步骤均需计算更多的节点，且需同时兼顾道路交通环境演变。尽管ECEA每次计算时间相对较长，但因计算时间远小于每次运算优化的时间间隔，故不影响其应用实时性。

在路径长度方面，ECEA比其他两种在线优化算法短，而比TCEPO长。这主要是因为ECEA能在到达拥堵区域前做出正确的绕路决策，或在即将消散的拥堵区域选择暂时等待，从而避免冗余的绕行。此外，ECEA是根据节点位置来进行优化的，优化次数较多，因而优化路径的长度比TCEPO长，但是在行程时间上有明显缩短。

在行程延误方面，ECEA要优于TCEPO、A*算法和Dijkstra算法，这主要是因为ECEA的行程时间最短，且其路径长度相对较短，仅次于TCECO。因此，在行驶速度相同的情况下，ECEA的行程延误最小。

5 结语

本文提出一种可扩展协同优化算法(ECEA)规划救援路径，以缩短应急救援行程时间。ECEA考虑了城市车辆运行特性与交通环境演变，使路径优化步骤与交通环境演变协同进行，减少交通拥堵等因素对路径规划的影响，并动态调整救援路径。

文中ECEA的搜索层数越大，其优化路径的行程时间越小。当搜索层数为5时，行程时间最小且趋于平稳。在行程时间方面，ECEA优于TCEPO、A*算法和Dijkstra算法，比TCEPO短8.48%～33.22%，比A*短18.74%～46.4%,比Dijkstra算法短22.46%～38.1%。在运算时间方面，虽然ECEA略大于其他算法，但在可接受范围内，不影响其在实际应用中的实时性。在路径长度方面，TCEPO最短，ECEA次之，比A*算法短7.07%～26.85%，比Dijkstra算法短4.81%～19.15%。在行程延误方面，ECEA优于TCEPO、A*算法和Dijkstra算法，比TCEPO低17.65%～53.5%，比A*算法低26.9%～57%,比Dijkstra算法低32%～51.5%。最后，在考虑预测误差的情况下，ECEA依然能够保持良好的优化性能，呈现强鲁棒性。

为进一步提升ECEA算法性能，下一步工作拟从以下两方面开展：(1)通过改善算法的逻辑框架和完善数据结构，缩短ECEA的运算时间；(2)与更多算法做对比，验证ECEA算法的有效性和可靠性。