计及路网权值时变特性的全局最优路径规划

黎万洪，胡明辉,b，陈 龙，饶 坤

(重庆大学 a.汽车工程学院；b.机械传动国家重点实验室, 重庆 400044)

路径规划作为智能汽车的决策层，对于提高驾驶人出行效率、缓解城市拥堵具有重要作用。起讫点行程时间是人们出行普遍较为关心之处，因此也成为了路径规划的首要需求[1]，其评价指标是路段行程时间的累加值。根据路段行程时间是否变化，可以将路径规划划分为静态路径规划(static path planning，SPP)和滚动路径规划(rolling path planning，RPP)。

SPP主要研究起讫点的累积最小权值，如最短路程或最短静态行程时间，较经典的研究方法有Dijkstra算法、A*算法、蚁群算法等[2]，但都各有缺陷。近年来，国内外学者针对上述算法提出了对应的改进策略，以提高算法的运行效率和规划精度。如针对A*算法易陷入局部最优、搜索速度较慢的缺陷，顾青等[3]设计了新的启发式估计能源成本函数以改善A*算法；Fu等[4]通过改进当前节点与目标节点的搜索策略提高了A*算法的搜索成功率；王维等[5]对估计路径代价进行指数衰减的方式加权，使得A*算法自适应地搜索目标点。蚁群算法同样存在收敛速度慢、容易陷入局部最优的缺点，王志中等[6]提出了蚂蚁相遇和蚂蚁回退策略，并改进了信息素残留方法。此外，文献[7-8]也都对蚁群算法进行了相应的改进。A*算法、蚁群算法等都属于智能启发式算法，无论如何改进算法，其包含的随机因子总有可能使路径搜索陷入局部最优，因而也就无法保证所得路径是全局最优解。尽管经典的Dijkstra算法冗余度较高，但当前计算机技术和网络通信技术的巨大发展有效地弥补了这一不足，考虑到该算法能保证找到全局最优解，仍不失为一种较好的方法。

RPP伴随着城市交通的发展而受到广泛关注，主要研究交通信息的获取及改进路径搜索算法的性能。在获取交通信息方面，Chai等[9]提出了自适应信号控制网络中的动态交通路径规划策略；El-Wakeel等[10]提出了一种基于人群感知的动态路线规划系统；李军[11]提出通过预测道路未来时刻交通信息，不断调用内嵌算法，从而实现了多阶段的RPP；Zhao等[12]通过信息中心网络中的大数据获取和分析架构，不断滚动规划智能车的行驶路线。在改进路径搜索算法随机性方面，Tilk等[13]在有界双向动态规划约束的最短路径问题求解变量加速技术的基础上，引入动态中途点来减少最短路径问题求解整体计算量。随裕猛等[14]在分析A*和D*Lite算法的不足之后，提出了D*Lite Label算法。刘琳等[15]依托车联网平台，通过查找车辆当前位置节点实时获取路网权值并进行动态路径规划。上述RPP的核心思想可以归纳为通过反复调用路径规划算法，不断更新汽车行驶路线，因此汽车实际行驶路线是由多阶段规划的局部最优路径拼接而成，而局部最优的叠加并不能推导出全局最优。另外，文献[16]详细阐述了城市交通流具有周期相似性，文献[17]研究了交通流与路段权值的定量关系，路段行程时间作为路段权值的一种评价指标，也顺理成章地体现了周期相似性特征，这一研究成果为时变权值路网的全局最优路径规划开辟了新颖的研究思路。

随着人们对准时到达目的地、缩短出行时间的需求的日益增加，传统的SPP和RPP方法已不再适用。基于此，首先系统分析了现有路径规划方法的不足之处，随后推导了时变权值路网的临界周期路段的实际权值，并基于Dijkstra算法提出了GOPP方法。在验证经典Dijkstra算法能实现全局最优解和运算时间低的基础上，分别利用SPP、RPP和GOPP三种方法规划路径。结果表明，GOPP可以实现时变权值路网的累积行程时间最小，该方法对于有效缩短交通出行时间和智能交通系统的发展具有一定的理论指导意义。

1 传统路径规划的缺陷

为了引出GOPP算法，首先探讨当前最常见的两种路径规划方法的缺陷。如图1所示是一个路段行程时间动态更新的示例路网，在时段1和时段2的路段行程时间如表1所示，两个时段相邻。假设当前车辆位于交叉口2，当前时刻t0处于时段1，目标交叉口为11，现探讨起讫点为(2，11)的传统路径规划方法。

图1 示例路网及3种路径规划方法比较Fig. 1 Example road network and comparison of three path planning methods

表1 示例路网的时变路段行程时间

SPP只考虑路网当前时刻的权值，根据时段1的权值分布计算得到的最优路径为2→6→7→11，如图1绿色路径所示。现假设车辆到达交叉口6的时刻恰好是时段1和时段2的临界时刻，路网权值随即更新为时段2的权值。则车辆在经过6→7→11时所耗费的行程时间应当参考时段2的权值分布，那么在时段1规划的所谓“最优路径”也就无法证明在时段2是否继续保持最优。因此，SPP的路径是特定时域(时段1)的最优路径，无法证明在全时域保持最优。

考虑到SPP的缺陷，研究人员提出了RPP方法。参考SPP在交叉口2规划的绿色路径，当车辆到达交叉口6时，路网权值发生更新。此时RPP根据时段2的权值立即重新规划剩余的道路网络的路径，计算发现黄色路线的累积权值小于绿色路线的累积权值，因此将行驶路线更改为黄色路线。RPP的两次路径规划起点分别为交叉口1和交叉口6，对应的路径分别为2→6和6→10→11，路径规划的空域显然不同。因此，RPP的实际行驶路径是由特定空域中的局部最优路径拼接而成的，局部最优的叠加并非全局最优，故RPP无法证明在全空域保持最优。

实际上，根据表1的权值变化通过计算证明图1的蓝色路径才是最优路径。为更加直观地展示3种路径规划方式的区别，绘制了如图2所示的起讫点直线距离变化示意图。图2中交叉口2和交叉口11的纵坐标之差表示两个交叉口间的空间直线距离，车辆从交叉口2出发，随时间推移到达交叉口11。其中，SPP_1表示车辆在交叉口2利用SPP方法规划路径计算得到的理想直线距离变化曲线，但由于车辆在交叉口6时路网权值更新，车辆继续按照SPP路径行驶的实际直线距离变化曲线如SPP_2所示。值得注意的是，蓝色最优路径在时段1并未体现其优势，进入时段2却率先到达了目标点。

图2 起讫点直线距离变化示意图Fig. 2 Schematic diagram of linear distance change between starting and ending points

以上示例展示了当前两种常见路径规划方式的核心思想，由于其均无法实现全局最优，因此有必要深刻分析图1蓝色最优路径的生成原理，探索一种新的求解复杂城市路网全局最优路径的方法。在此之前，首先介绍城市路网的拓扑结构及交通仿真数据的存储，将其作为路径规划的数据基础。

2 路网的拓扑结构与交通仿真

2.1 路网拓扑结构与数据存储

城市路网是一个权值时变且包含转向限制的有向图[18]，如图3所示。这里的时变性是指因交通流具有一定的周期相似性，导致路网权值(如路段行程时间)也呈现周期相似性规律的特性，权值更新的周期应当视具体路网和交通情况而定。

图3 路网拓扑结构示意图Fig. 3 Schematic diagram of road network topology

路网拓扑结构要素释义如下：1)圆标数字是节点编号，表示路网中的交叉路口(仅考虑十字形和丁字形交叉路口)；2)路段是指两个相邻节点之间的道路，且具有方向性，如6→7表示由节点6指向节点7的路段，并定义节点6为父节点，节点7为子节点；3)黑色数字表示路段权值，用来描述车辆行驶该路段所花费的代价，选取路段行程时间作为权值。4)绿色数字表示转向延误权值，描述车辆在交叉口转向所耗费的时间，如车辆的路径规划为1→2→6，车辆从节点1到达节点2须右转，则右转的延误权值为9，若节点有转向限制，则用无穷大代表转向延误权值。

城市路网的数据存储需要考虑交叉口、转向限制以及路段之间的联通性等，目前关于路网数据存储方面的研究有邻接矩阵、邻接表、十字链表等多种建模存储方法[19]。笔者参考文献[20]提出的前向关联边数据存储结构(后文简称数据存储结构)，并针对路径规划算法的需要做适当改进，以快速方便地访问路网数据，基于图3路网的数据存储结构如图4所示(部分节点数据)。

图4 路网的数据储存结构Fig. 4 Data storage structure of road network

数据存储结构主要由3个矩阵构成：1)路网共有12个节点，构造12×2矩阵ParentNode_Pointer。矩阵的第一列存放路网所有节点(视为父节点)，并按升序排列，第二列存放父子节点指针；2)再分析路网节点之间的联通关系，构造n×2矩阵ChildNode_Weight(n视具体路网而定)。该矩阵的第一列依次存放矩阵ParentNode_Pointer的每一个父节点的所有邻节点(视为子节点)，每一个父节点的若干子节点仍升序排列，第二列存放父节点指向子节点的路段权值。当矩阵ChildNode_Weight唯一确定后，记录每一个父节点的最小子节点所在的行编号，并存放在矩阵ParentNode_Pointer对应的父子节点指针。3)最后分析路网节点间的转向限制及对应权值，构造n×6矩阵TurningNode_Weight。第1至3列存放由父节点指向子节点并转向后的节点编号(只考虑左转、直行及右转)，第4至6列存放对应的转向权值。

道德焦虑的化解也需要进一步完善村民的民主意识和政治自觉，包括拓展制度化参与渠道、 充分地掌握信息、拥有更多的政治参与权和知情权。同时，在实地调研中还发现，进一步完善“村民理事会”等自治组织，能够从制度建设方面充分保障村务公开和村民自治。搭建一个可以交流、处置、落实的工作平台，确保村民话有地方说、理有地方讲、困有人帮、惑有人解，能够有力推动基层村民政治诉求和生活需求的解决，让制度创新和信息公开成为道德文化的一个减压器。

2.2 路网建模及交通仿真

环境建模方面，基于Vissim建立重庆大学城局部路网，主要工作包括路段的建立、红绿灯及交通配时的设置、路口交通分流策略的设置等。该路网共有230个节点，778条路段，总面积近70 km2，如图5所示。图中，节点82周围的蓝色节点表示子节点，绿色数字表示子节点的邻近节点。

图5 基于Vissim软件的重庆大学城路网建模Fig. 5 Road network modeling of Chongqing University Town based on Vissim software

交通仿真方面，结合重庆大学城实际交通情况和路网建模环境，在路网边沿若干重要节点设置两组车流量，分别模拟早高峰期间8:17—8:30与8:30—8:43(以下分别称为时段1和时段2，并设路网权值时变周期为780 s)两个时段的车流输入。同时为每个路段设置行程时间采集器，采集结果作为路段权值。另外为了让车流充分融入路网内部以体现不同路段的交通特性，在1 800 s后再开始记录行程时间。最后对仿真所得数据做统计分析，得到大学城路网行程时间数据库，以此作为路径规划的数据来源。以节点82作为父节点的部分仿真行程时间数据如表2所示。

表2 部分仿真行程时间数据

3 GOPP算法及仿真分析

路径规划算法笔者在经典Dijkstra算法基础上，新增跨时段路段实际权值计算环节，提出了GOPP算法，如图6所示。

图6 GOPP算法流程Fig. 6 Flow chart of GOPP algorithm

以图1示例路网为例，介绍GOPP算法的5个步骤：

2)遍历未知节点集。进入循环，在U中搜索距源点s权值最小的节点k，将该点从U移到S中，同时将该点k的权值和对应的路径分别存放到dk和pk中。在第1)步基础上，设集合U中节点2具有最小累计权值d2，故S={1,2}，U={3,4,5,6,7,8,9,10,11,12}。

3)比较更新邻近节点权值。设节点k至邻近子节点j的路段权值与转向权值之和为w(k,j)，判断dk+w(k,j)与dj的大小，更新s至j的最小权值dj和对应路径pj。在第2)步基础上，节点2的邻近节点包括3和6，由于节点3和6的累积权值为无穷大，故此时应当更新d3和d6。传统Dijkstra算法从第1)步至第3)步不断循环，直至U=∅便结束算法。笔者所提出的GOPP算法新增跨时段路段的实际权值计算环节，该环节将判断路网权值是否更新并计算跨时段路段的实际权值，如图6虚线框所示，具体步骤如下第4)、5)步。

5)计算临界节点对的实际累计权值。在第4)步基础上，设临界路段6→10在时段1和时段2的权值分别为ω6_10_1和ω6_10_2，车辆在路段6→10于时段1的行驶路程比例r为：

(1)

则路径1→2→6→10的实际累计权值为：

(2)

据此将集合S中的所有临界父节点构成集合Sc，将集合U中的所有临界子节点构成集合Uc，进而组成临界节点对集C。参照式(1)与式(2)，可以计算临界节点对集的所有跨时段路段实际权值。之后更新时段编号Tnum，然后循环第2)步到第5)步，直到U=∅。

4 仿真验证及分析

仿真实验所用的硬件平台是Win10 @64 bit + Intel Core i5-4590 @3.3 GHz +RAM @ 8G，软件平台是MATLAB 2018a。

4.1 经典Dijkstra算法与蚁群算法的比较

首先，为了体现经典Dijkstra算法在静态权值路网中的全局最优计算能力，基于预先建立的重庆大学城局部路网和时段1(8:17—8:30)的路段行程时间数据库，将智能启发式算法代表之一的蚁群算法作为对照[6]，不失一般性地设定了3组起讫点进行仿真实验。路径规划结果及累积路段行程时间如图7和表3所示，图7中的蓝色、紫色、绿色分别代表起讫点(1，229)(4，224)(12，209)，实线与虚线分别代表Dijkstra算法和蚁群算法。

图7 Dijkstra算法与蚁群算法的3组路径规划结果Fig. 7 Three groups of path planning results of Dijkstra algorithm and ant colony algorithm

表3 Dijkstra算法与蚁群算法的3组路径规划的累计行程时间

由表3可知，Dijkstra算法的累积行程时间均小于蚁群算法。以图7的起讫点(12,209)为例，蚁群算法所规划的路径与Dijkstra算法部分重合，表明具有一定的路径寻优能力，但中途有两次与Dijkstra算法路径分离，这是由于蚁群算法本身自带随机因子，在从源节点至目标节点的搜索过程中受随机因素影响较大，尽管在蚂蚁信息素的引导下可以加快收敛，但同时也增大了陷入局部最优的概率。

图8为蚁群算法的行程时间随迭代次数的变化图，由图可知当迭代次数达到22次后，蚁群算法便已陷入了局部最优，极不利于对全局最优路径的求解，而作为广度优先搜索算法的Dijkstra算法则避免了局部最优的缺陷。另外，蚁群算法和Dijkstra算法的运行时间大约分别在1 s和1.5 s左右，Dijkstra算法以额外较小的运行时间成本获得了更满意的最优路径。综上所述，选择Dijkstra算法作为静态权值路网的全局最优路径规划方法是可行且有效的，在时变权值路网中则采用改进之后的GOPP算法。

图8 蚁群算法行程时间随迭代次数的变化Fig. 8 The change of the travel time of ant colony algorithm with the number of iterations

4.2 GOPP算法与SPP、RPP的比较

为了验证所提出的GOPP算法在时变权值路网求解全局最优路径的优越性，需要合理设定起讫点及路径规划时刻，否则可能因累积行程时间小于本时段周期，或者部分路段的行程时间在相邻时段变化不大，而出现GOPP和RPP、SPP的路径规划结果相同的情况。基于此，笔者在细致分析所建路网及行程时间特点基础上，选取了起讫点(12,209)作为仿真实验节点。设车辆位于源节点12的时刻为早上8:17(即时段1起始时刻)，路网的权值将在8:30更新，利用Dijkstra算法分别采用SPP、RPP和GOPP 3种思想进行路径规划，3种路径规划结果见表4和图9。

图9 3种路径规划仿真结果比较Fig. 9 Comparison of simulation results of three path planning methods

表4 3种路径规划结果累计权值比较

3种路径规划方式的起讫点直线距离变化曲线如图10所示。

图10 3种路径规划方式的起讫点直线距离变化曲线Fig. 10 Straight line distance curves of starting and ending points of three path planning methods

综合分析图9和图10，并结合重庆大学城实际交通情况，可以看出：

1)3种算法制定的3条路径在节点12至节点49重合，然后GOPP方法出现分离；算法SPP和RPP沿路段49→48朝西延伸至节点107，之后再次出现分离；而算法GOPP沿49→72朝南延伸直至目标节点；

2)节点107南向路段(大学城中路)分布有重庆大学、重庆一中等学校，北向路段分布有重庆师范大学、大学城地铁站，仿真结果表明算法SPP和RPP到达节点107的时刻为8:30:11，此时正是早高峰拥堵时段，路网权值已经更新。因此，RPP在节点107基于时段2的路网权值重新规划剩余路径，规划结果表明节点107沿西(大学城南路)行驶可以有效避免拥堵；

3)节点184东西路段(大学城南路)是大学城路网的骨干路段，南北路段分布有华润微电园、固废流转中心等企业，在时段1交通较为拥堵，进入时段2逐渐缓解，因此图10蓝色曲线在经过了节点184后便较快到达了终点。故GOPP规划路径累计权值为仅为1 158.7 s，相比SPP和RPP分别减少了212.7 s和57.6 s，证明了GOPP在缩短出行规划时间上的优越性。

5 结 论

首先分析了现有路径规划方法的不足，随后推导了跨时段路段的实际权值，界定了路径规划领域的局部最优叠加值与全局最优值的区别，并基于Dijkstra算法提出了一种全局最优路径规划方法。仿真结果表明，GOPP相比SPP和RPP具有最小的累积权值，有效地验证了GOPP在面向时变权值路网求解全局最优路径的优越性。有如下结论：

1)SPP和RPP两类常见路径规划方式在面对具有权值时变特性的交通路网时，无法求解全局最优路径；

2)经典的Dijkstra算法尽管算法冗余度较高，却以广度优先比智能启发式算法更能求得全局最优解；

3)基于Dijkstra算法的GOPP路径规划方法能够实现权值时变路网的时间最短全局最优路径的求解，可以有效缩短驾驶员的交通出行时间，对今后智能网联汽车和智能交通系统的发展具有一定的理论指导意义。