基于局域降维Dijkstra算法的校园送餐机器人多目标路径规划

宫金良，牛作硕，张彦斐

(1. 山东理工大学 机械工程学院, 山东 淄博 255049；2.山东理工大学 农业工程与食品科学学院，山东 淄博 255049)

智能时代的到来为人们生活带来了极大方便，近年来同城即时配送行业开始兴起[1]。校园作为一种特殊的室外送餐环境，其运行路段相对社会交通比较简单，但人口流动性大，尤其在课间休息时间，道路上行人更为密集。同时，校园居住人口较多，用餐时间相对集中，所以对送餐效率有较高的要求，因此送餐路径的规划和选择起到决定性作用。

目前路径规划常用的算法有Dijkstra算法、Johnson算法、Floyd-Warshall算法和A*算法等。Dijkstra算法作为一种贪心算法，通过搜索局部最优解求出全局最优解，在很多领域得到广泛应用。李泽文等[2]提出一种基于Dijkstra算法的电网故障行波定位方法，解决了电网故障定位解网复杂的问题。王乙斐等[3]使用Dijkstra算法建立了一种最优解列断面搜索方法。Wongso等[4]使用Dijkstra算法对城市公交运行最短路径求解方法进行了分析。

本文通过环境建模，对校园送餐过程中存在的道路状况进行分析，实现多目标优化，通过创建邻接矩阵对传统Dijkstra算法迭代过程中存在的数据冗余现象进行优化，并使用改进后的Dijkstra算法对校园送餐路径进行规划。

1 校园送餐环境模型搭建

1.1 校园送餐环境模型搭建与路径分析

相对城市错综复杂的道路交通而言，校园送餐路径仅包括校园主干路和穿插公寓之间的辅助路段，布局相对规则。根据实际需求和道路环境，将送餐道路交叉点和取餐点定义为路径节点，节点之间的路径定义为路段。以山东理工大学西校北公寓区为例，建立校园送餐拓扑地图，如图1所示。

图1 校园送餐路径图Fig.1 Campus food delivery route map

本文在搭建送餐环境的过程中，使用一款基于北斗系统进行定位的智能小车执行配送餐任务。通过GPS/北斗结合IMU对任务车辆进行定位是当前的主流做法[5]，与使用激光雷达或者视觉建模进行定位相比，该定位方式可以减小数据处理量，同时降低了控制算法复杂性，在保证满足定位需求的同时可大大降低开发成本。在定位和导航过程中，需对运行路段进行坐标采集，获得送餐地理路线，从而结合环境特点从中选取合适的送餐路径。忽略路径的垂直落差，将采集到的送餐路段地理坐标信息转化为直观路径长度信息，得到节点之间的距离权值。

1.2 多目标问题转化

多目标优化问题[6-7]往往涉及到一个或多个冲突，对某一目标的优化，往往会影响其它目标的优化。本文将对送餐的路径长短、实时路况、路径简繁、突发情况以及能耗等影响因子进行综合考虑，对校园路径规划进行多目标优化。

将时间消耗作为单一目标函数，替代传统的距离加权函数进行路径规划。建立路径耗时函数G=min{∑path_costi(state_Tx)}，其中G为餐车运行总耗时。路段i的耗时用path_costi表示，state_Tx为该路段影响因子x的时间消耗值。特别地，在传统路径规划中，两个节点之间的实际弧段距离L为非负值，经过等价转换后的state_Tx仍为正值。下面对state_Tx的5种优化目标进行转化分析。

1)路程长短state_Tlength与实时路况state_Tcrowd

作为影响整个配送消耗的主导因素，路径长度最短是首要考虑的目标。使用两节点之间的欧氏距离作为路段长度，即

state_Tlength=length/average_speed，

(1)

式中average_speed为预设速度，其值由当前道路通畅程度决定。道路的实时情况可以通过步行人群稠密度和车辆通行状况进行分析。高校学生主要交通方式为步行且易集群，根据不同路段的人口通行量，将路段进行经验性等级划分，设置为拥挤、正常、通畅3个等级。根据车流量大小对路段添加交通警示标记，以此对车辆通行状况进行分析。针对不同路况的路段设置合适的运行速度，可以提高配送效率。上述两种影响因素可统一表述为

(2)

行人稠密度density与车流量信息vehicle_flow作为平均速度的临时变化系数，反映不同路段的道路状况对预设速度的影响，即

(3)

通过引入人口密度ρ(单位为：人/m2)的概念对density分析赋值[8-9]。根据校园路段人口稠密度调查，将路况划分为3个等级，并设定对应的人口密度为：通畅、正常、拥挤，参数设置见表1。vehicle_flow根据有无警示标记取系数0.8或1。

表1 人口密度及相应的参数设定Tab.1 Population density and corresponding parameter setting

加入路况信息后的路径图如图2所示。

图2 校园送餐路况图Fig.2 Campus food delivery road traffic map

2)路径简繁state_Tcomplexity

路径简繁是指行驶路径中相关影响因素的繁杂程度。如在实际的驾驶过程中，人们更倾向于选择转弯次数少、红绿灯路口少的路径，以提高驾驶体验。这种决策方式可以避免因过多考虑道路路况等原因而造成路径过于复杂，从而保证运送效率。路径简繁主要体现在路过的节点个数和节点处转弯的次数，考虑到通过节点和转弯都会造成额外的时间消耗，因此有

(4)

式中turning_factor是转弯耗时Tturn_cost的布尔型参数，根据当前路段的前节点是否执行过转弯取值1或0。节点耗时Tnode为常量值，根据路过节点个数进行累加，对规划路径的复杂度进行控制。

3)突发情况state_Tsudden_situation

校园内突发情况包括道路的施工、活动占用等情况，该路段会呈临时阻断状态，此时添加标记量block进行调整规划，即

state_Tsudden_situation=situation·block，

(5)

式中路况通行状态situation为布尔型变量，设置block为无穷大值，当该道路不能通行时，situation置1，此时路段权值为无穷大，不加入路径规划。

4)能源消耗state_Tenergy

能耗控制可以延长配送车辆的运行时间，保证送餐过程的可持续性。当规划出耗时相近的多条路径时，选择路程短的路径执行任务，以减小能源消耗。此过程为附加判断，不加入单条路段权值计算。

通过对5种因素进行目标归一化处理，得到目标函数表达式为

(6)

2 校园送餐机器人多节点路径规划

2.1 基于传统Dijkstra算法的路径规划迭代过程

基于传统Dijkstra算法[10]的路径规划迭代过程如下：

1)确定路径规划节点，根据路段长度进行路段节点距离权值的赋值，同一节点之间距离为0、非相邻节点之间距离为∞，以此为依据创建距离权值邻接矩阵。

2)创建标记节点集合M={start_node}与未标记节点集合U(包含start_node以外的所有节点)，以start_node作为第一次迭代初始点开始从U中搜索距离start_node最近节点nearest_node，并记录对应最近节点的节点值。

3)将nearest_node节点作为下一次迭代初始点，设置start_node为last_node，并从U中取出，放入标记集合M中，对U中各个节点与起始点的距离值进行更新。

4)进行再一轮迭代，直至搜索到目标点，结束计算。

传统的Dijkstra算法过程简洁，但具有一定的冗余计算，当数据量较大时，多余的搜索和更新时间会使路径规划效率急剧下降。本文提出一种创建节点邻点集合N的方式，将实时搜索域和更新范围进行缩小，从而提高路径规划效率。

2.2 Dijkstra算法降维改进

根据校园送餐场景，以a1点为初始点、e2点为送餐点为例，提出改进的Dijkstra算法路径规划方案。

步骤1 将节点按照图1从上到下和从右到左的顺序赋予ID值并排序，分别以距离和时间作为路径权值创建邻接矩阵，结果如图3(单位:m)和图4(单位:s)所示。

图3 距离权值邻接矩阵 Fig.3 Adjacent weight matrix of distance

图4 时间权值邻接矩阵Fig.4 Adjacent weight matrix of time

通过不同权值的邻接矩阵可以看出，与单一考虑路径长短的规划相比，在多目标优化后，路径权值的排序因为实时路况的不同而发生变化，从而解决了受路况影响无法选择最优送餐路线的问题。该方法的路段权值大小优先顺序更符合实际，有利于提升路径规划的时效性，证明了多目标优化的必要性。

步骤2 将节点1至21放入整体节点集合W中，并添加节点属性值(P(ni),li)。其中，P(ni)表示节点ni距离出发点start_node所需要的时间，li为前一次的迭代节点last_node，通过记录last_node即可获得最终的规划路径。根据时间权值邻接矩阵为所有节点创建邻点集合Nx，例如节点a1的邻接集合为Na1={a2,b1}。

步骤3 创建标记节点集合M={a1}与未标记节点集合U={a2,a3,...,e3}，以a1作为start_node开始规划。传统Dijkstra算法将从U中搜索距离a1最近的节点，过程中会对U中所有节点进行遍历，遍历对象包含大量与a1距离为∞的节点。优化后算法通过节点的邻接集合Nx创建局部域Z=∑Nx-U，x∈U，即当前所有标记点邻点集合的并集去除标记点后的点集。以局部域Z作为搜索域，此时由图2可以看出，与a1相邻的节点只有a2与b1，即只需要从两相邻节点中搜索即可。

步骤4 此时a2为当前nearest_node，设置a2为start_node，a1为last_node，则M={a1，a2}。传统Dijkstra算法将对U中所有元素的P(ni)值进行更新，同样需要对U中所有节点的P(ni)值进行遍历更新。此时对M中节点的非相邻节点进行P(ni)值更新并无意义，因此使用当前局部域Z作为更新域进行更新，可以缩小更新域范围，提高更新速度。传统Dijkstra算法与改进Dijkstra算法第一次迭代过程使用的局部域对比见表2。

表2 算法局部域对比Tab.2 Local domain comparison of two algorithms

步骤5 重复步骤3—步骤4，直至将目的节点e2放入集合M。

在后续搜索过程中，节点的相邻节点不超过4个，设此时Z中元素个数为n，则每次迭代的搜索和更新的次数皆小于4n，从而通过创建邻点集合，使用局部域Z将计算由n2的二维运算量转化为一维运算量，实现了降维计算。

3 实验仿真结果与分析

在Linux操作系统环境下，使用C++图形用户界面开发软件QT编写程序，分别使用传统Dijkstra算法和局域降维Dijkstra算法进行路径规划仿真，并使用高精度运行计数器频率采样函数QueryPerformanceFrequenc(&a)，对路径规划过程进行耗时统计。QT规划界面如图5所示。

图5 QT规划界面Fig.5 QT programming interface

通过设置不同送餐点进行多次模拟规划,对规划耗时取均值后的规划结果见表3，路径规划耗时变化曲线如图6所示。分析表3和图6可知：在路径选择方面，两种算法最终规划的路径相同；耗时方面，当参与规划的路径点较少时，传统算法的耗时与改进后算法的耗时相近，但随着路径点的增多，改进后算法耗时与传统算法耗时相比大大减小。因此，改进后的Dijkstra算法能够通过缩小迭代的搜索域和更新域，针对规划路径逐渐复杂的情况，使该模拟路径规划耗时由1～2 ms指数增长为7～10 ms变为1～2 ms倍数增长为2～4 ms，耗时优化效果更佳。

表3 路径规划结果Tab.3 Path planning results

图6 路径规划耗时变化曲线Fig.6 The change curve of path planning time

4 结论

1)针对校园特殊环境进行路径分析建模，将路径规划中的传统距离权值转化为时间权值。通过多目标优化分析，使用路径耗时函数对路径规划中的多影响因素进行统一转化，使转化后路段的权值在添加实际路况后更贴切反应真实的路况，使其更适合实际应用，整体提高了路径规划的可行性和针对性。

2)使用局域降维Dijkstra算法对校园送餐实例进行路径规划，在传统算法的基础上，提出创建节点邻接集合的方法，缩小了迭代过程中的最小路径搜索域和最优路径更新域。使用软件进行算法仿真，得出规划路径的同时，其算法时间复杂度由传统的O(n2)降为O(n)，随着规划路径复杂程度的增加，改进后算法能够将规划耗时变化控制在小浮动范围内。模拟实验结果表明，改进的Dijkstra算法大大减小了路径规划的耗时，提高了路径规划效率，具有很强的实用性。