J Automotive Safety and Energy, Vol. 12 No. 1, 2021
杜 茂，杨 林*，金 悦，涂家毓
（上海交通大学机械与动力工程学院，上海 200240，中国）
摘要：为降低混合动力汽车（HEV）的出行时间和出行能耗，提出了一种基于时空动态交通信息的路径规划算法。分析了影响车辆通行时间和全程最低能耗的因素。一种基于广义回归网络（GRNN）模型，拟合计算了道路通行时间以及整体路径的全程能耗。构建了基于并行A*算法的车辆路径规划算法，为确定起终点位置后的车辆，规划了一条耗时更短、更加节能的路径。进行了仿真对比试验。结果表明：相比于依据平均车速与道路功率的计算方法，该算法能够获得更优的出行路径，可降低车辆能耗11%以上，缩短行车时间13%以上。因而，该算法可为车辆规划更优的路径。 关键词：混合动力汽车(HEV)；城市交通；路径规划；时空搜索
中图分类号： U 469.7 文献标识码： A DOI： 10.3969/j.issn.1674-8484.2021.01.005 Vehicle global path planning algorithm based on spatio-
temporal characteristics of traffic
DU Mao, YANG Lin*, JIN Yue, TU Jiayu
(School of Mechanical Engineering, Shanghai Jiao Tong University, Shanghai 200240, China) Abstract: A path planning algorithm based on spatiotemporal dynamic traffic information was proposed to
reduce the travel time and energy consumption of hybrid electric vehicles (HEV). The factors that affect the
vehicle travel time and the minimum energy consumption in the whole path were analyzed. The travel time
and the path energy consumption are calculated based on the generalized regression network (GRNN) model.
A vehicle path planning algorithm based on parallel A * algorithm was constructed to plan a shorter time-
consuming or more energy-saving path for vehicles after determining the starting and ending positions. The
黄金分割率
virtual simulation test was implemented. The results show that the proposed algorithm can obtain a better travel path and reduce vehicle energy consumption by more than 11% or driving time by more than 13% compared
with the calculation methods through average speed or power parameters. Therefore, the proposed algorithm
can plan a better route for vehicles.
Key words: hybrid electric vehicle (HEV); urban traffic; path planning; space-time searching
收稿日期 / Received ：2020-11-11。
基金项目 / Supported by ：国家自然科学基金资助项目（51875339）。
第一作者 / First author ：杜茂（1990—），男（汉），河北，博士研究生。E-mail：*****************。
* 通讯作者 / Corresponding author ：杨林，教授。E-mail：****************。
图1 二维空间搜索与三维时空搜索示意
车辆路径问题（vehicle routing problem, VRP ）的一个重要研究领域即是时间依赖型车辆路径问题（time dependent vehicle routing problem, TDVRP ）。如何为出行车辆提供可靠的全程最低行程时间或者能耗路径依然是TDVRP 问题的难点之一。
opera 迅雷在路径耗时方面，文献[1-4]在研究过程中提出假设车辆的速度为定值，路段的通行时间只与道路长度相关。因此，路径规划过程中将通行时间问题转换为道路长度问题。而文献[5-9]则通过道路长度与平均车速的比值来表征道路的通行时间。这些方法计算简单，但缺乏对实际交通动态特性的考虑，无法适应实际路网的运行环境。通过道路状态划分[10]的方法忽略了较多的交通细节信息，本质上只能够满足对道路状态的定性分析，无法满足更多需要定量计算的要求。实例学习模型
[11]
根据历史样本数据估算当前通行时间，但
其一般具有较长的时间间隔，适用于交通的长期周期性研究，而非路径规划。
而在出行能耗方面，瞬时计算模型[12]、基于SVM 模型[13]、聚合模型[14]、回归拟合模型[15]等方法通过获取的瞬时车速信息提取出多种计算指标，进而对车辆在道路上的行驶能耗进行计算。然而，由于全程瞬时信息预测问题的限制，上述方法计无法展开全程最优能耗路径搜索。文献[16]提出的车速-
空间-时间三维搜索体系在寻优过程缺乏对时变的路网参数进行更新，难以在路径寻优中进行准确的能耗优化。
综上所述，当前关于路径时间或能耗最优规划依然存在以下缺点：
1) 未考虑路网的动态时变特性。实际的路径规划过程应该是在三维时空领域展开的。只将累积通行时间作为选择路径的参考指标之一，并未考虑搜索过程的时空化的研究更接近于二维的搜索过程，无法反映时空搜索的本质。
2) 实现手段过于简单或理想化。将道路交通状态进行划分或通过车辆瞬时信息计算的方法，前者限制了路径的优化程度，而后者则由于预测技术的限制无法有效开展全程路径规划。
3) 能耗最优的路径规划研究尚待进一步深入。尤其对混合动力汽车，现有研究中能耗的计算缺少对控制策略的说明，无法判断搜索的能耗是否最优。
本文基于宏观交通信息对道路的通行时间以及最优能耗的影响因素进行了分析。建立了路径的通行时间与PHEV 最优能耗回归算法模型。以改进的并行A*算法为基础构建了城市交通时空联合的路径搜索方法。该算法能够在搜索过程中根据已搜索路径的累积耗时
与各道路交通特征及时更新后续道路的交通状态，从而实现时空动态搜索过程。为了方便对交通本质
进行更加深入的分析，本文研究数据是通过城市交通仿真软件SUMO 对来源于开源地图数据库OpenStreetMap 的地图数据进行仿真得到[17-19]。
1 基于回归拟合的通行时间计算
三部门联合发布9个新职业
1.1 搜索过程的时空特征
道路的行程时间与能耗则是与道路结构（空间）以及其承载的交通（时变）同时有关的动态变量。仅仅基于距离或者交通费用最优的路径搜索实际上是一个无关时间变化的二维空间搜索过程，如图1a 所示。而当考虑到达时间与能耗时，其搜索过程实际上应是在三维时空领域展开的，如图1b 所示。图1中坐标轴X 和Y 代表道路空间坐标，坐标Z 代表时间。
起点
终点
(a)二维
(b) 三维
1.2 通行时间的计算
搜索的路径的累积消耗时间一般计算如下：
(1)
其中： τi, t 为道路 i 在时间 t 时车辆的通行时间； n 为道路 i 在整个路径中的序号； N 为路径中道路的个数； l i 为道路 i
为车辆在时间 t 时通过道路 i 的平均车速，在实际应用中常使用可预测的宏观交通数据来进行计算。然而，仅仅依据平均车速的方式无法保证其计算精度。
本文基于交通仿真软件SUMO 对截取的上海某一区域路网进行了交通仿真计算。以1 min 为单位时间整理得到了宏观交通数据。依式 (1) 计算道路的通行时间，其与车辆的实际通行时间平均百分比误差为36.1%。由
图2 简化交通环境示意图
此可见，式 (1) 的计算误差较大。其根本原因是仅仅依靠平均车速进行计算忽略了其它因素对车辆通行时间的影响。因此，本文简化常见的交通环境如图2所示。
5) 下一道路 j 的交通状态，包括：平均车速
以
及密度 。其中：
(4)
上述影响因素与车辆在该道路上的通行时间之间
的关联性计算如表1所示。
表1 通行时间与各影响因素之间的关联性
从表1来看，单独每个影响因素与通行时间之间的关联性都不是特别强。因此，为了增加计算的准确性，本文考虑同时采用多个影响因素来对道路的通行时间进行拟合。以径向基函数神经网络(radical basis function ，RBF)和线性神经元组合成的广义回归神经网络（general regression neural network ，GRNN ）具有很强的非线性映射能力和学习速度。径向基核函数的
高维投射能力也使得GRNN 更适合于处理多维输入的回归问题。因此，本文采用GRNN 网络来处理不同影响因素组合带来的对通行时间的回归效果。
表2为8种计算方案 （ID ）以及每种方案计算结果（相对误差RE 以及绝对误差MAE ）。由表2可知：由于涉及到更多瞬时车速信息的计算，平均功率的加入能够使模型获得更好的计算精度。
由于在实际的宏观交通系统中，不可能获得某一道路未来具体的车速情况，平均功率ēi,t 无法直接计算得到；因此，以方案8所选因素作为GRNN 网络输入，构建了计算车辆通行时间的计算模型，即：
其中： ∆t i,j,t 为车辆在时刻 t 通过道路 i 到达道路 j 的通行时间；函数 f T 为搭建的GRNN 网络。式(5)与式(1) 的计算差异见图3（截取第950~1 000算例的结果）。由图3可见：利用本文模型对不同计算样本所计算的通行时间，均与真实值一致；能将误差RE 从利用式 (1) 所计算的36%，减小至9%。
由图2可见：车辆在行驶过程中会受到当前道路（空间信息）其它车辆状态（交通信息）以及红绿灯状态等因素的直接影响。而当前道路的交通状态又会收到其邻接道路交通状态的影响，进而影响目标车辆的行驶状况。影响因素有：
1) 当前道路 i 在第 t 个采样周期的交通信息，包括平均车速
以及单位长度上车辆密度 ρi, t ：
其中： v k 为第k 辆车经过道路（或指定位置）的车速；α(t )为道路 i 在第 t 个采样周期内运行的车辆数量； l i 为道路 i 的长度。
2) 当前道路 i 的主要属性，包括通行道路长度 l i 、路口长度γi 。
3) 道路预估通行时长 τi, t （见式(1)），以及道路的通行功率 ēi, t ：
(3)
其中： F k,i 1与 v k,i 1分别为第 k 辆车在i 1时刻的驱动力和
车速。
n (i 1)为时间i 1时刻在道路 i 上运行的车辆数量，∆t 为采样时长。
4) 当前道路 i 与下一道路 j 之间的红绿灯的状态，包括：在时间 t 时剩余一个周期内绿灯时长 g i, t 以及非绿灯的时长 r i, t 。
2 全局最优能耗模型
路径的全局能耗计算模型应符合以下特点： 1) 全局能耗具有最优性。从理论上保证计算的全局能耗最优（或者接近最优）是能耗最优路径搜索的基础。也是为出行车辆提供最具有节油潜力的路线的基础。
2) 输入参数具有可获取性。由于是时空领域的全局搜索，必须要考虑模型输入参数在未来能够预测或
黑龙江生态工程职业学院者有效获取。
基于此，本文提出一种基于宏观交通信息来计算未来规划的路径的全局能耗的方法。为了能够减少其它因素（例如驾驶习惯不同、能量管理策略）对节能效果带来的影响，依据动态规划（dynamic programming ，DP ）方法对车辆的全程最优油耗进行了计算。具体车型参数及计算方法见文献[20]中的双离合并联汽车。由于车辆的DP 油耗为全程指标，路径上每一个道路的交通状态都会对其产生影响；因此，本文选取了能够反映路径全局特征信息的8个参数：
参数1 行程距离。路径的累积行驶距离为
(6)
其中： 为道路编号， I 为路网中道路的数量。
参数2 总能耗。路径中所有道路的通行能耗的和为
(7)
其中： ēi,t 为道路的通行功率。 ∆t i,j,t 为在时间 t 时通过
道路 i 到达道路 j 的通行时间。
参数3 平均能耗。路径通行能耗的平均值为
参数4 总功率。路径中所有通行功率的和为
参数5 平均功率。路径通行功率的平均值为
参数6 总耗时。路径通行时间累积值为
(11)
参数7 平均耗时。路径通行时间的平均值为
参数8 平均车速。车辆经过路径上所有道路时
的道路车速的平均值为
(13)
上述参数以及DP 油耗之间的关联性计算结果如表4所示。
表2 不同影响因素搭配方案
050
100
通行时间 / s
预测样本
图3 路段通行时间计算对比
由表4可知：各个参数与DP油耗之间的关联性比较明显，且不同的参数之间又存在一定的关联性。为了简化影响因素的表征，本文引入了因子分析法（factor analysis, FA）来对这些变量之间的内部关系进行分析。经过分析，各个参数在不同的公共因子上的载荷分布具有明显的差异性。依据结果，得到3个主要公共因子：时间因子、距离因子、速度因子。鉴于多因子回归的方式，本文同样以GRNN网络
为基础，依据各个参数在3个公共因子上载荷分布大小，组成3种方案，进行仿真计算；结果如表5所示。
表5 3proxyfox
中菲关系种参数组合方案计算结果
由表5可知：随着输入参数数量的增加，准确度缓慢降低。这表明：增加在相同公共因子上同样具有较高载荷分布的参数的个数，并不能够为回归模型带来更高的计算精度，反而对回归计算带来了更多的干扰。考虑计算精度以及模型的复杂性，采用方案1的参数，搭建GRNN网络，对DP油耗进行回归拟合处理，计算如下：
其中：F k为拟合得到的路径的全局DP油耗；函数f E为GRNN网络。
3 基于并行A*的时空全局搜索算法
在得到道路的通行时间以及全程最优能耗计算方法后，基于路径搜索算法即可进行最优路径的搜索。在常用的搜索算法中，A*算法由于启发项的加入使其具有结构简单、计算速度快等优点，且从理论上其能够得到最优搜索结果；因此，该算法在众多领域得到了广泛的应用。针对出行车辆的最优路径规划，假设道路个数为k的路径的当前道路为i，下一搜索道路为j，则A*算法的惩罚函数可以定义为：
(15)
其中：α1、α2、α3、α4分别为行程时间、行程距离、DP 油耗、启发项等指标的惩罚系数；η0 = 0，L0 = 0，F k = 0；
h i为启发项，为当前搜索道路i与终点道路之间的距离；函数g(x)为归一化函数；X max与X min分别为参数样本的最大与最小值。
DP油耗计算需要引入全局因素（例如整条路径的平均车速），这将导致整个搜索过程变得更为复杂。
除距离外的其它参数均无法参与启发值h i的计算，这些参数的计算过程更接近于Dijstrla算法。而Dijstrla搜索算法的遍历本质属性会影响算法的搜索效率。假如启发项的惩罚系数过小，那么计算耗时将非常长；而假如启发项的惩罚系数过大，那么搜索得到的路径效果可能会无法得到有效保证。本文提出以距离为基础指标，同时搜索多条路径的搜索方法。具体步骤为：步骤1 以累积距离与启发距离的加权和计算代价函数：
(16)其中，β为启发距离权重。
步骤2 根据当前道路的到达时间ηk更新其交通状态，包括道路车速、密度、红绿灯信息。
表4 各参数以及DP
油耗之间的关联性
