基于交通时空特征的车辆全局路径规划算法

杜 茂，杨 林，金 悦，涂家毓

（上海交通大学 机械与动力工程学院，上海 200240， 中国）

车辆路径问题（vehicle routing problem, VRP）的一个重要研究领域即是时间依赖型车辆路径问题（time dependent vehicle routing problem, TDVRP）。如何为出行车辆提供可靠的全程最低行程时间或者能耗路径依然是TDVRP问题的难点之一。

在路径耗时方面，文献[1-4]在研究过程中提出假设车辆的速度为定值，路段的通行时间只与道路长度相关。因此，路径规划过程中将通行时间问题转换为道路长度问题。而文献[5-9]则通过道路长度与平均车速的比值来表征道路的通行时间。这些方法计算简单，但缺乏对实际交通动态特性的考虑，无法适应实际路网的运行环境。通过道路状态划分[10]的方法忽略了较多的交通细节信息，本质上只能够满足对道路状态的定性分析，无法满足更多需要定量计算的要求。实例学习模型[11]根据历史样本数据估算当前通行时间，但其一般具有较长的时间间隔，适用于交通的长期周期性研究，而非路径规划。

而在出行能耗方面，瞬时计算模型[12]、基于SVM模型[13]、聚合模型[14]、回归拟合模型[15]等方法通过获取的瞬时车速信息提取出多种计算指标，进而对车辆在道路上的行驶能耗进行计算。然而，由于全程瞬时信息预测问题的限制，上述方法计无法展开全程最优能耗路径搜索。文献[16]提出的车速-空间-时间三维搜索体系在寻优过程缺乏对时变的路网参数进行更新，难以在路径寻优中进行准确的能耗优化。

综上所述，当前关于路径时间或能耗最优规划依然存在以下缺点：

1) 未考虑路网的动态时变特性。实际的路径规划过程应该是在三维时空领域展开的。只将累积通行时间作为选择路径的参考指标之一，并未考虑搜索过程的时空化的研究更接近于二维的搜索过程，无法反映时空搜索的本质。

2) 实现手段过于简单或理想化。将道路交通状态进行划分或通过车辆瞬时信息计算的方法，前者限制了路径的优化程度，而后者则由于预测技术的限制无法有效开展全程路径规划。

3) 能耗最优的路径规划研究尚待进一步深入。尤其对混合动力汽车，现有研究中能耗的计算缺少对控制策略的说明，无法判断搜索的能耗是否最优。

本文基于宏观交通信息对道路的通行时间以及最优能耗的影响因素进行了分析。建立了路径的通行时间与PHEV最优能耗回归算法模型。以改进的并行A*算法为基础构建了城市交通时空联合的路径搜索方法。该算法能够在搜索过程中根据已搜索路径的累积耗时与各道路交通特征及时更新后续道路的交通状态，从而实现时空动态搜索过程。为了方便对交通本质进行更加深入的分析，本文研究数据是通过城市交通仿真软件SUMO对来源于开源地图数据库OpenStreetMap的地图数据进行仿真得到[17-19]。

1 基于回归拟合的通行时间计算

1.1 搜索过程的时空特征

道路的行程时间与能耗则是与道路结构（空间）以及其承载的交通（时变）同时有关的动态变量。仅仅基于距离或者交通费用最优的路径搜索实际上是一个无关时间变化的二维空间搜索过程，如图1a所示。而当考虑到达时间与能耗时，其搜索过程实际上应是在三维时空领域展开的，如图1b所示。图1中坐标轴X和Y代表道路空间坐标，坐标Z代表时间。

图1 二维空间搜索与三维时空搜索示意

1.2 通行时间的计算

搜索的路径的累积消耗时间一般计算如下：

其中：τi, t为道路i在时间t时车辆的通行时间；n为道路i在整个路径中的序号；N为路径中道路的个数；li为道路i的长度；为车辆在时间t时通过道路i的平均车速，在实际应用中常使用可预测的宏观交通数据来进行计算。然而，仅仅依据平均车速的方式无法保证其计算精度。

本文基于交通仿真软件SUMO对截取的上海某一区域路网进行了交通仿真计算。以1 min为单位时间整理得到了宏观交通数据。依式 (1) 计算道路的通行时间，其与车辆的实际通行时间平均百分比误差为36.1%。由此可见，式 (1) 的计算误差较大。其根本原因是仅仅依靠平均车速进行计算忽略了其它因素对车辆通行时间的影响。因此，本文简化常见的交通环境如图2所示。

图2 简化交通环境示意图

由图2可见：车辆在行驶过程中会受到当前道路（空间信息）其它车辆状态（交通信息）以及红绿灯状态等因素的直接影响。而当前道路的交通状态又会收到其邻接道路交通状态的影响，进而影响目标车辆的行驶状况。影响因素有：

1) 当前道路i在第t个采样周期的交通信息，包括平均车速以及单位长度上车辆密度ρi, t：

其中：vk为第k辆车经过道路（或指定位置）的车速；α(t)为道路i在第t个采样周期内运行的车辆数量；li为道路i的长度。

2) 当前道路i的主要属性，包括通行道路长度li、路口长度γi。

3) 道路预估通行时长τi, t（见式 (1)），以及道路的通行功率：

其中：Fk,i1与vk,i1分别为第k辆车在i1时刻的驱动力和车速。n(i1)为时间i1时刻在道路i上运行的车辆数量，Δt为采样时长。

4) 当前道路i与下一道路j之间的红绿灯的状态，包括：在时间t时剩余一个周期内绿灯时长gi, t以及非绿灯的时长ri, t。

5) 下一道路j的交通状态，包括：平均车速以及密度其中：

上述影响因素与车辆在该道路上的通行时间之间的关联性计算如表1所示。

表1 通行时间与各影响因素之间的关联性

从表1来看，单独每个影响因素与通行时间之间的关联性都不是特别强。因此，为了增加计算的准确性，本文考虑同时采用多个影响因素来对道路的通行时间进行拟合。以径向基函数神经网络(radical basis function，RBF)和线性神经元组合成的广义回归神经网络（general regression neural network，GRNN）具有很强的非线性映射能力和学习速度。径向基核函数的高维投射能力也使得GRNN更适合于处理多维输入的回归问题。因此，本文采用GRNN网络来处理不同影响因素组合带来的对通行时间的回归效果。

表2为8种计算方案 （ID）以及每种方案计算结果（相对误差RE以及绝对误差MAE）。由表2可知：由于涉及到更多瞬时车速信息的计算，平均功率的加入能够使模型获得更好的计算精度。

由于在实际的宏观交通系统中，不可能获得某一道路未来具体的车速情况，平均功率无法直接计算得到；因此，以方案8所选因素作为GRNN网络输入，构建了计算车辆通行时间的计算模型，即：

其中： Δti,j,t为车辆在时刻t通过道路i到达道路j的通行时间；函数fT为搭建的GRNN网络。式(5)与式(1)的计算差异见图3（截取第950～1 000算例的结果）。由图3可见：利用本文模型对不同计算样本所计算的通行时间，均与真实值一致；能将误差RE从利用式 (1) 所计算的36%，减小至9%。

表2 不同影响因素搭配方案

图3 路段通行时间计算对比

2 全局最优能耗模型

路径的全局能耗计算模型应符合以下特点：

1) 全局能耗具有最优性。从理论上保证计算的全局能耗最优（或者接近最优）是能耗最优路径搜索的基础。也是为出行车辆提供最具有节油潜力的路线的基础。

2) 输入参数具有可获取性。由于是时空领域的全局搜索，必须要考虑模型输入参数在未来能够预测或者有效获取。

基于此，本文提出一种基于宏观交通信息来计算未来规划的路径的全局能耗的方法。为了能够减少其它因素（例如驾驶习惯不同、能量管理策略）对节能效果带来的影响，依据动态规划（dynamic programming，DP）方法对车辆的全程最优油耗进行了计算。具体车型参数及计算方法见文献[20]中的双离合并联汽车。由于车辆的DP油耗为全程指标，路径上每一个道路的交通状态都会对其产生影响；因此，本文选取了能够反映路径全局特征信息的8个参数：

参数1行程距离。路径的累积行驶距离为

其中： 为道路编号，I为路网中道路的数量。

参数2总能耗。路径中所有道路的通行能耗的和为

其中：为道路的通行功率。 Δti,j,t为在时间t时通过道路i到达道路j的通行时间。

参数3平均能耗。路径通行能耗的平均值为

参数4总功率。路径中所有通行功率的和为

参数5平均功率。路径通行功率的平均值为

参数6总耗时。路径通行时间累积值为

参数7平均耗时。路径通行时间的平均值为

参数8平均车速。车辆经过路径上所有道路时的道路车速的平均值为

上述参数以及DP油耗之间的关联性计算结果如表4所示。

表4 各参数以及DP油耗之间的关联性

由表4可知：各个参数与DP油耗之间的关联性比较明显，且不同的参数之间又存在一定的关联性。为了简化影响因素的表征，本文引入了因子分析法（factor analysis, FA）来对这些变量之间的内部关系进行分析。经过分析，各个参数在不同的公共因子上的载荷分布具有明显的差异性。依据结果，得到3个主要公共因子：时间因子、距离因子、速度因子。鉴于多因子回归的方式，本文同样以GRNN网络为基础，依据各个参数在3个公共因子上载荷分布大小， 组成3种方案，进行仿真计算；结果如表5所示。

表5 3种参数组合方案计算结果

由表5可知：随着输入参数数量的增加，准确度缓慢降低。这表明：增加在相同公共因子上同样具有较高载荷分布的参数的个数，并不能够为回归模型带来更高的计算精度，反而对回归计算带来了更多的干扰。考虑计算精度以及模型的复杂性，采用方案1的参数，搭建GRNN网络，对DP油耗进行回归拟合处理，计算如下：

其中：Fk为拟合得到的路径的全局DP油耗；函数fE为GRNN网络。

3 基于并行A*的时空全局搜索算法

在得到道路的通行时间以及全程最优能耗计算方法后，基于路径搜索算法即可进行最优路径的搜索。在常用的搜索算法中，A*算法由于启发项的加入使其具有结构简单、计算速度快等优点，且从理论上其能够得到最优搜索结果；因此，该算法在众多领域得到了广泛的应用。针对出行车辆的最优路径规划，假设道路个数为k的路径的当前道路为i，下一搜索道路为j，则A*算法的惩罚函数可以定义为：

其中：α1、α2、α3、α4分别为行程时间、行程距离、DP油耗、启发项等指标的惩罚系数；η0= 0，L0= 0，Fk= 0；hi为启发项，为当前搜索道路i与终点道路之间的距离；函数g(x)为归一化函数；Xmax与Xmin分别为参数样本的最大与最小值。

DP油耗计算需要引入全局因素（例如整条路径的平均车速），这将导致整个搜索过程变得更为复杂。除距离外的其它参数均无法参与启发值hi的计算，这些参数的计算过程更接近于Dijstrla算法。而Dijstrla搜索算法的遍历本质属性会影响算法的搜索效率。假如启发项的惩罚系数过小，那么计算耗时将非常长；而假如启发项的惩罚系数过大，那么搜索得到的路径效果可能会无法得到有效保证。本文提出以距离为基础指标，同时搜索多条路径的搜索方法。具体步骤为：

步骤1以累积距离与启发距离的加权和计算代价函数：

其中，β为启发距离权重。

步骤2根据当前道路的到达时间ηk更新其交通状态，包括道路车速、密度、红绿灯信息。

步骤3通过式(5)计算当前道路的通行时间 Δti,j,t并计算新路径的行程时间ηk+1=ηk+ Δti,j,t。更新道路个数、平均耗时、行程距离、平均车速，同时依据式（14）计算新路径的DP油耗Fk+1。

步骤4若当前道路为终点道路，则执行步骤 (5)，否则，依据A*算法，重复步骤1—步骤3。

步骤5按照距离最短依次计算n（例如1 000）条不同路径。

步骤6在所得的路径集合中，分别选择DP油耗、行程时间或者行程距离最小路径，为满足不同指标最优的路径。

传统的A*算法中每次都是选择当前最优点进行新一轮的搜索。然而，由于需要搜索多条路径，为了加快整个搜索过程，本文选取当前的最优点以及其后一定数量的次最优点同时进行新一轮的搜索。其中，次最优点选择为除去最优点后依据惩罚函数从小到大而得到的一定数目的点。改进的并行A*搜索算法的搜索过程示意图，如图4所示。

图4 改进的多点并行A*搜索算法示意图

每次都选择当前最优点与多个次最优点进行新的搜索，这种并行的计算方式使得部分次最优点成为新的最优点的所需迭代次数减少了。并行搜索点数量的增加可能会导致下一搜索点数量的成倍增长。考虑到实际计算开销问题，基于改进的多点并行A*搜索算法的过程需要优化2个参数：启发项惩罚系数以及A*算法单次搜索数量。本文选取了不同的参数组合进行了仿真计算。计算结果显示：

1) 搜索算法的计算耗时与启发项惩罚系数以及单次搜索数量具有较强的关系。由于影响着启发值在惩罚函数中的占比，整体上计算耗时随着惩罚系数的增加而快速降低；而虽然并行多次计算能够缩短非最优点达到最优点的迭代次数；但是过高的单次搜索数量也会增加算法耗时；因此搜索耗时随着单次搜索数量的增加呈现先降低后增加的情况。

2) 启发项惩罚函数越大，说明启发值在惩罚函数占比越大；惩罚函数的最优值会受到启发值的更多的影响，进而降低其它指标的最优表征能力； 最优DP油耗、行程时间、行程距离等指标，整体上呈现随着启发项惩罚系数的增加而增加。同时，单次搜索数量越大意味着越多的次最优点与最优点具有同等地位，算法在本质上越接近于Dijstrla算法。在这种情况下，启发值对惩罚函数的影响越小。故而最优路径的DP油耗、行程时间、行程距离等指标，随着单次搜索数量的增加而降低。

综合考虑指标优化以及计算耗时，本文选择启发项惩罚系数β= 1.4，单次搜索数量为200的参数组合。

4 仿真试验分析

本文中SUMO仿真采用的城市交通地图结构如图5所示。SUMO软件仿真过程主要包括设置.route文件（车辆出行路径文件）以及.sumocfg文件（仿真系统文件）。前者文件主要用来在仿真之前规定每辆车的起终点道路以及具体行驶路径，后者文件则是对仿真过程以及仿真结果记录等方面进行设置。

图5 仿真地图道路结构

本文的仿真试验采用多辆车同时出行的方式来构成该路网上的宏观交通数据。在.route文件设置方面，依据SUMO系统默认的最短路径进行规划，出行车辆的起点道路与终点道路依据地图随机选择。依据SUMO系统的仿真原则设定了车辆出行间隔时间。该时间是指SUMO系统在路网中产生一个随机起终点出行车辆的间隔时间，即系统仿真期间新车辆介入路网的间隔时间设置为1 s。车辆动力性参数，例如最大加、减速度等，均采用SUMO默认值。.sumocfg文件的设置参数为：

1) 仿真开始时间：0 s；

2) 仿真结束时间：104s；

3) 仿真时间步长：1 s；

4) 仿真记录参数包括：系统时间、车速、所处道路、所处位置以及该道路对应的红绿灯状态等信息。

仿真结束后，提取仿真记录参数，得到每辆车的行驶数据，进而得到每条道路在指定宏观采样时间内的交通状态。具体计算方法如第2、3小节所述。其中，提取部分道路的交通流量与平均车速信息如图6-7所示，图中不同颜色的柱体代表不同道路。

图6 道路平均交通流量

图7 道路平均车速

为了对本文提出的基于动态时空特征的全局车辆路径规划算法进行验证，本文进行了以下对比计算。基于城市路网交通具有动态变化的特性，为出行车辆提供时空领域的全局路径规划必然离不开对交通参数的预测。本文主要是针对路径通行时间以及全程最优能耗的研究，重点不在预测算法上面；为了保证测试的合理性，首先假设未来交通参数均是已知，然后在此基础上为其添加不同信噪比数据来模拟实际应用中对交通参数的预测值。通过文献调研发现，当前的交通信息预测算法的精度会随着预测时长的增长而下降。预测时长在5～50 min的预测误差为10%～20%[21]。为了保证测试过程的合理性，本文分别添加平均百分比误差为0%、10%、15%、20%的噪声来生成测试交通信息数据。本文添加的噪声为Gauss白噪声，符合正态分布。具体添加方式为：

1) 将交通信息数据通过标准化转换为均值为0，方差为1的正态分布数据。

2) 信噪比公式，计算噪声在指定相对误差ε下的信噪比为：

得到信噪比后，产生指定噪声。本算法中搜索路径集合大小为300，计算机配备有主频为3.0 GHz的i-7处理器，内存16 GB。

对比算法方面，本文基于A*算法分别构建了在时空领域和空间领域搜索的2种对比算法。称前者为对比算法1，后者为对比算法2。对比算法1与对比算法2均为基于A*的搜索算法。2种算法的步骤为：

步骤1初始化当前道路信息，对于对比算法2而言，路径搜索过程中的交通信息保持不变，均采用当前时刻所有道路各自的值。对于对比算法1而言，需要基于当前时刻以及历史时刻的交通数据对，来路网未来交通信息进行预测，将预测信息视为其后续路径搜索交通信息。

步骤2类似于式（15），2种算法采用的惩罚函数为

其中：τi, t与fi, t分别为道路i的通行时间与能耗；α1、α2、α3、α4的取值决定搜索算法对不同指标优化的重视程度，当取值（1, 0, 0, 0）以及（0, 0, 1, 0）时，分别代表按照累积通行时间最优以及累积能耗最优进行路径规划。

步骤3更新开放集合与历史集合，选择当前开放集合中的最优道路（惩罚函数最小）的邻接道路作为新的当前道路进行计算。

步骤4对比算法1根据当前道路的到达时间更新其交通状态。2种对比算法均采用式(1)与式(7)分别计算当前道路的通行时间与能耗。

步骤5若当前道路为终点道路，则结束搜索过程，得到最优路径。否则依据A*算法重复步骤2—步骤5。

具体试验过程为：

1) 选择测试车辆，以其出发时间为起点时间，以其出发道路为起点道路。

2) 基于宏观交通未来预测，分别根据上述3种方法规划测试车辆起点到终点的路径。

3) 根据规划的路径，更新原.route文件中测试车辆的路径，再次通过SUMO进行车辆行驶仿真。

4) 整理得到对应规划路径下的车辆行驶数据。

理论最低能耗的路径是车辆实际能耗降低的基础。本文根据行驶结果采用DP算法计算得到车辆的行驶油耗来进行3种算法的车辆能耗比较。3种算法基于能耗最优路径得到的DP油耗与基于时间最优路径得到的行程时间（t）的计算结果，如图8所示。

为比较算法的计算效率，图9和图10所示为几种算法的搜索耗时对比；其中对比算法2与本文提出的全局搜索算法对应的曲线，参考左侧坐标轴，对比算法1曲线，参考右侧坐标轴。

表6所示为本文提出的算法规划的最优能耗路径与最短时间路径相对其它两种算法的优化效果。表7所示为相比其它2种算法的搜索效率的提升效果。

表 6 本文算法规划的最优能耗路径带来的能耗下降效果

表7 搜索算法效率的提升效果

图8 3种算法计算结果对比图

图9 测试算法的最优能耗路径搜索耗时

图10 测试算法的最短时间路径搜索耗时

可见，相较于对比算法，本文提出的基于动态时空特征的全局路径规划算法能够获得更优的能耗优化或者时间优化路径，可降低车辆能耗11%以上或缩短行车时间13%以上。这是由于本文方法综合考虑了道路通行时间以及全程最优能耗的影响因素，提高了道路通行时间与能耗模型的计算精度，同时采用了针对时变环境的时空联合搜索方法。

在搜索耗时方面，对比算法1完全在时空领域进行搜索，维数增多带来了巨大的搜索耗时；对比算法2则仅仅是在二维空间领域进行搜索，具有最快的搜索速度；本文采用的搜索算法由于是并行计算，且每次搜索仅仅考虑距离指标，能够加快搜索速度，在能够获得更优路径的同时，与对比算法2耗时差并不是很大；因此，本文提出的基于动态时空特征的全局路径规划算法能够更加有效地优化出行车辆的路径选择。

5 结 论

为科学合理的路径规划，本文基于当前的宏观交通信息对道路的通行时间以及能耗的影响因素进行了分析。依据回归方法构建了计算道路通行时间以及针对混合动力汽车的路径全程能耗的计算方法。以改进的并行A*算法为基础，构建了城市交通时空联合领域的路径搜索方法。对提出的算法进行了对比验证。

结果显示：本文提出的方法能够在可接受时间内为出行车辆提供更加合理的路径规划，相比依据平均车速与道路功率的计算方法，可降低车辆能耗11%以上或缩短行车时间13%以上。