基于A*算法的定制化无人驾驶公交路径规划方法

叶德超，谢振东，董志国，于洁涵，徐华全

（1.广东工业大学自动化学院，广州 510000；2.广州市公共交通集团有限公司，广州 510000；3.广州羊城通有限公司，广州 510000）

近年来，随着自动驾驶技术的发展，智能交通领域也得到了革命性的发展。为了解决城市交通问题，政府一直以来都在大力倡导公共出行[1]，而定制化无人驾驶公交无疑为市民提供了一种新的公共出行方式[2]。马昌喜等[3]从定制公交线路优化目标、问题场景和求解算法3 个方面对相关文献进行了归类分析。魏晨曦等[4]对定制公交潜在客流识别与选址、线网规划、运营管理3个方面进行了综述，并分析了未来我国定制化公交可能的研究方向。郭嫚[5]结合定制公交线路规划中的满载率、停靠点个数、绕行距离等约束条件，从乘客、企业、社会3 个角度入手建立需求可拆分的目标函数，构建了基于多点对多点开行模式的定制化公交路径规划模型。

路径规划是自动驾驶的一个关键环节，一直以来都是自动驾驶领域的研究重点之一。路径规划主要分为全局路径规划和局部路径规划。张珂、李永丹等[6-8]对无人驾驶车辆路径规划算法进行了综述，分析了各类算法的优缺点。

其中A*（A-Star）算法在路径规划应用中优势较为明显，A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法[9-10]。算法中的距离估算值与实际值越接近，最终搜索速度越快。但A*算法的搜索目标是获得最短路径，而对于定制化无人驾驶公交的运营目标则是行驶尽可能少的距离将尽可能多的乘客送到目的地，以达到降低运营成本，提高乘客出行体验的目标。

本文对A*算法进行改进，使路径规划算法符合定制化无人驾驶公交的运营要求，使企业和乘客的共同利益最大化。

1 定制化无人驾驶公交运营模式

以满载10 人的微型无人驾驶小巴运行在全长5 km的人口密集地区作为运行场景，参考出租车的停靠特点，微型小巴凭借较小的车辆体积可以停靠在有停车条件的公交站或者标志性路口。信息处理中心集中处理乘客的订单，对乘客的出行需求进行整合后，向无人驾驶小巴下达调度指令，提供路径规划方案。

根据整合的出行订单可以将任务分为2 种不同的模式。第一种，每一名乘客的出行起点和终点都不相同，没有重合的起点和目的地；第二种，存在有重合的起点或目的地，即无人驾驶公交可能在某一个地方接送到多名乘客。

第一种，通过多次使用A*算法进行规划路线，每次路径规划都是以获得离当前点的距离最短为目标。

第二种，如果单纯使用A*算法进行路径规划，可能会出现以下3 种情况：①起点A 点离目标点C点2 km，离目标点B 点3 km，无论从A 点到C 点的乘客人数大于还是小于从A 点到B 点的人数，算法均会选择优先到达C 点，这是因为算法的目标就是获得最短距离；②起点A 点离目标点C 和目标点B 的距离相等，但从A 点到C 点的乘客人数少于从A 点到B点的乘客人数，算法仍有可能选择优先到达C 点；③如图1所示，起点A 点离目标点C 点2 km，离下一个起点B点3 km，起点B 点离目标点C 点3 km，A 点和B点均有乘客需要到C 点，算法可能会选择从A 点到C点，C点到B点，B 点再回 C 点，这样总距离为 2 km +3 km+3 km=8 km，但如果能从A 点到B 点，B 点到C点，则总距离为3 km+3 km=6 km。明显后一种方案行驶距离较短。

图1 点A、B、C 分布

无人驾驶公交自动化程度高，尤其微型小巴很适合解决最后一公里的交通问题。路径规划算法在提高运营效率，降低企业的成本，提高乘客的出行体验等方面起着关键性的作用，单纯使用A*算法进行路径规划可能会出现上述路线不够合理的情况，因此根据运营的实际情况对算法进行优化是十分必要的。

2 算法介绍

2.1 A*算法

A*算法于1968年，由Stanford 研究院的Peter Hart，Nils Nilsson 及Bertram Raphael 发表，其被认为是Dijkstra 算法的扩展。A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的启发式算法，启发式探索是利用问题拥有的启发信息来引导搜索，达到减少探索范围，降低问题复杂度的目的。算法中的距离估算值与实际值越接近，最终搜索速度越快。

算法的公式表示为：f*（s）=g*（s）+h*（s），式中：f*（s）为从初始状态经由状态s 到目标状态的最小代价估计，g*（s）为在状态空间中从初始状态到状态s 的最小代价；h*（s）是从状态s 到目标状态的路径的最小估计代价。

算法的主要运行步骤如下：

（1）将初始节点放入到open 列表中。

（2）判断open 列表。如果为空，则搜索失败。如果open 列表中存在目标节点，则搜索成功。

（3）从open 列表中取出f 值最小的节点作为当前节点，并将其加入到close 列表中。

（4）计算当前节点相邻的所有可达节点，然后生成一组子节点。而对于每一个子节点：①如果该节点在close 列表中，则抛弃它。②如果该节点在open 列表中，则检查其通过当前节点计算得到的f 值是否更小。③如果更小则更新其f 值，并将其父节点设置为当前节点。如果该节点不在open 列表中，则将其加入到open 列表，并计算f 值，设置其父节点为当前节点。

（5）转到2 步骤。

2.2 改进A*算法

为了将传统的A*算法更好地应用在定制化无人驾驶公交上，需要对算法进行改进。改进主要如下：

（1）加入乘客人数n 的约束，当出现2 个或者2 个以上离起点距离相等的终点时，应考虑到目标点的乘客人数，即此时优先考虑选择人均距离最短的目标点，将算法考虑的单纯路径距离改为人均距离进行路径规划。

（2）当不存在重合的起点或终点时，假设出现当前点到2 个或2 个以上目标点的距离相同时，优先将先上车的乘客送到对应的终点，以减少乘客的通勤时间。

（3）当存在不同起点的乘客有重合的目标点的情况时，假设当前起点A 点离下一个起点B 点的距离小于到目标点C 点的距离，则优先选择先到B 点，但起点A 点离目标点C 点距离较短时，则需要进行评估，分别考虑先送车上乘客到目标点之后再接下一起点的乘客即A→C→B→C 还是先接下一个起点的乘客之后再统一将乘客送到目标点即A→B→C 的距离较短，如出现2 种方法距离相等时，则应选择先将当前车上乘客先送到目标点，以减少这部分乘客的通勤时间。流程如图2所示。

图2 改进算法流程图

3 仿真验证与分析

3.1 程序运行主要流程

为了测试算法的有效性，使用matlab 仿真软件进行仿真测试，仿真获得路径规划路线，程序主要流程如图3所示。

图3 程序主要流程图

本算法以A*算法为基础，根据乘客的出行需求情况分为2 类，无重合起点和终点及有重合起点或终点2 种模式，不同模式进行路径规划时，进行相关条件的约束，然后使用改进的A*算法进行路径规划，直到将所有的点处理完为止，最终获得完整的路线图。

3.2 仿真的主要参数

仿真主要参数见表1、表2。

表2 实验2 参数表

3.3 实验结果及分析

3.3.1 实验1

实验1 以5 名乘客均有不同的出发点和终点为例，在不同地形下进行路径规划仿真实验（图4—图7）。

图4 实验1 第1 组运行结果图

图5 实验1 第2 组运行结果图

图6 实验1 第3 组运行结果图

图7 实验1 第4 组运行结果图

实验在20×20 的地图下进行路径规划，黑色部分为障碍物，4 组图的地形均不相同，程序平均运行时间约4.32 s。从实验结果可以看出，第1 组的路径规划为：AB→BE→EF→FI→IH→HJ→JD→DC→CG，而第2,3,4组的路径规划均为：AB→BE→EF→FH→HI→IJ→JD→DC→CG。可以看出在这种情况下多次调用A*算法可以实现多点路径规划功能，第1 组和其余3 组的路径规划情况略有不同，这是因为该算法考虑障碍物的影响，以实际可行路线的距离为准，搜索最短的行驶距离，并且算法规定必须先到起点，才能把起点对应的终点添加到路径规划线路中，符合定制化无人驾驶公交的实际运营情况。

3.3.2 实验2

实验2 以6 名乘客存在有相同的出发点或终点的情况为例，进行路径规划仿真实验（图8—图9）。

实验在20×20 的地图下进行路径规划，黑色部分为障碍物，从实验结果可以看出，第1 组和第2 组的路径规划为：AC→CE→ED→DB→BI→IF→FH→HG，即S1（S2、S3）→S4→G1→G2（G4）→S6→G6→S5→G3，第1组S1（4，5）到G1（4，3）的距离大于S1（4，5）到S4（6，6）的距离，但图中选择了先到S4（6，6），第2 组S1（4，5）到G1（4，3）的距离小于S1（4，5）到S4（6，6）的距离，图中仍选择了先到S4（6，6）。这是因为改进的算法在遇到这种情况时需要进行分析判断，在路径规划前，对各坐标点进行了分类，分为起点和终点，如图8所示，当前点到最近的起点的距离小于最近的终点时，优先选择了先到最近的起点，但当前点到最近的起点的距离大于最近的终点时，如图9所示，则需要进行判断，图9实验结果所示，dis（S1→G1）＜dis（S1→S4），S1（4，5）和S4（6，6）分别有一名乘客的目标点为（4，3），此时计算可知dis（S1→G1）+dis（G1→S4）+dis（S4→G1）＞dis（S1→S4）+dis（S4→G1），所以优先选择了S1（S2、S3）→S4→G1的路线。

图8 实验2 第1 组运行结果图

图9 实验2 第2 组运行结果图

4 结论与展望

4.1 结论

定制化无人驾驶公交是自动驾驶技术和定制化公交运营模式相结合的成果。无人驾驶公交自动化程度高，其路径规划方法关系着其运行的效率和安全性。同时，微型无人驾驶小巴车辆体积小，停靠的位置更加灵活，不限于停靠公交站点，比较适合解决最后一公里的交通问题。定制化公交作为一种新的运营模式，其目标是满足乘客的个性化出行需求且有通勤效率更高，通勤成本更低的优势，同时也能降低企业的运营成本，提高公共交通行业的竞争力。所以，对乘客的需求进行整合，做好路径规划尤其重要。传统A*算法的目标是获得最短路径，如果直接应用到定制化无人驾驶公交上可能会出现路径虽然可行但不够合理的问题，本文针对这个问题对A*算法进行了改进，加入乘客数量和重合点的约束，优化了调用算法的条件，使其更符合定制化无人驾驶公交的实际运营特点，从仿真结果来看，改进的算法能够实现多点路径规划功能，并且能够根据实际情况进行方案调整，减少了行驶的距离，能够为定制化无人驾驶公交的实际运营提供参考方案。

4.2 展望

从仿真结果来看，本文论述的方法虽然能够有效地应用在定制化无人驾驶公交的路径规划上，且能达到较为满意的效果，但在算法运算效率方面仍有提升的空间，本人希望后续继续探索算法的改进以及与其他算法的优势互补。同时，在实际路况中，可能会有更多本文没有考虑到的因素，本文论述的路径规划方法仅在仿真软件做了仿真实验，而在实际路段上能否安全有效且稳定地应用在无人驾驶公交车上仍需做更多的实际运营测试和调研。不但如此，本文的研究是基于理想状态下把行驶距离作为运行成本，没有考虑到实际道路拥堵情况、能源以及其他管理成本，后续应考虑更多其他的相关因素来作进一步优化。除此之外，如何平衡企业的利益和乘客的利益仍需要作更多的研究。