基于Bi-A*的ACO算法的最快路径推荐

郑永玲 白宇 杨楠 蒋顺英

摘  要：文章针对ACO算法收敛速度慢和容易陷入局部最优等问题，利用Bi-A*算法的代价估计函数优化ACO算法的启发式函数，增强算法全局搜索能力;再通过引入每次循环得出的最快路径优化ACO算法的信息素更新规则，加快算法收敛速度;基于Spark结合真实的大规模出租车轨迹数据，将Bi-A*-ACO算法应用于最快路径推荐，实验结果表明，Bi-A*-ACO算法比传统ACO算法更具有有效性和准确性。

关键词：Bi-A*;ACO算法;载客路线;信息素;Spark

中图分类号：TP301.6;TP18      文献标识码：A 文章编号：2096-4706（2020）22-0074-08

The Fastest Path Recommendation of ACO Algorithm Based on Bi-A*

ZHENG Yongling，BAI Yu，YANG Nan，JIANG Shunying

（School of Data Science and Information Engineering，Guizhou Minzu University，Guiyang  550025，China）

Abstract：Aiming at the problems of slow convergence of the ACO algorithm and easy to fall into local optimality，the article uses the cost estimation function of the Bi-A* algorithm to optimize the heuristic function of the ACO algorithm to enhance the algorithms global search ability;and then optimize the pheromone update rule of the ACO algorithm by introducing the fastest path obtained in each cycle to speed up the algorithm convergence speed;based on Spark combined with real large-scale taxi trajectory data，the Bi-A*-ACO algorithm is applied to the fastest route recommendation. The experimental results show that the Bi-A*-ACO algorithm is more effective and accurate than the traditional ACO algorithm.

Keywords：Bi-A*;ACO algorithm;passenger route;pheromone;Spark

0  引  言

隨着智慧城市和智慧交通不断发展，出租车成为居民日常生活中不可或缺的重要出行工具，由于车辆需求不断增加，导致城市交通拥堵、事故频发等诸多情况[1]，熟悉城市路网的出租车司机可以快速通过最快路径找到乘客，而缺乏经验的出租车司机却难以找到搭载乘客的最快路线，导致了空载出租车在盲目巡航过程中成本增加、交通拥堵和能源浪费等问题，因此，通过结合真实路网构建算法帮助出租车推荐最快路径变得十分迫切。就目前来看，全球定位系统（GPS）相关技术已经趋于成熟并成为路径规划的重要支撑，通过出租车配备的GPS传感器，可以向数据中心实时发送出租车的地理信息及运营状况，保证了数据的真实性和可靠性。

在路径推荐方面，经验丰富的出租车驾驶员能快速准确地找到抵达下一个目标地点的最快路径，甚至能在高峰时段有效避开拥堵路段，因此其运营成本也相对较低。但是，对于缺乏经验的驾驶员来说不能及时找到快速到达目标点的最快路径，将导致其单位时间成本高和盈利低等问题。针对上述问题，本文通过结合历史轨迹数据和真实路网进行建模，准确实现最快路径推荐，有效帮助出租车快速抵达乘客位置，可以解决城市规划和缓解交通拥堵等问题。

近年来，现有的最快路径推荐研究主要集中在：（1）贪心算法：如Dijkstra算法、Floyd算法和A*算法等;（2）启发式算法：如ACO算法，遗传算法等;（3）神经网络：如PCNN等。

上述研究大部分主要运用在机器人路径规划、AGV路径规划和TSP问题等方面，在出租车最快路径推荐应用相对较少。为此，作者基于贵州民族大学海量数据统计与分析方向的研究，针对传统ACO算法的缺陷，提出利用Bi-A*算法改进传统的ACO算法，由于单机环境下处理大规模轨迹数据存在“内存消耗高、I/O开销大、数据传输耗时、计算性能低”等诸多弊端，作者便结合Spark平台进行最快路径推荐，通过并行算法有效弥补单机环境缺陷;数据来源于北京市GPS数据和真实路网节点数据（谷歌地图）。

1  相关工作

本小节简要介绍路径推荐的相关工作，并分析所存在的问题。车辆路径推荐是城市规划和资源配置的重要支撑，通过对车辆进行最快路径推荐可以解决城市路网规划、交通路线确定等问题。

贪心算法：汤红杰等人利用邻接表来存储Dijkstra算法中的路网图，并使用二叉堆存储未到达节点得到一种优化的Dijkstra算法[2]，邹益民等人利用几何方法得出了移动机器人在弯道运行过程中移动时间与过渡圆弧圆心之间的数学关系，通过这个关系来改进Dijkstra算法以解决机器人避障问题的路径规划[3]，程林等人通过利用SuperMap GIS平台的网络编辑功能来改进传统的Dijkstra算法[4]。李大东等人通过可视化Dijkstra单向最快路径规划算法将飞行轨迹视为一系列直线和圆弧，利用转弯终点与起点构建三圆弧组合实现避障转弯，在Dijkstra算法中成功引入最小转弯的半径约束[5]。朱永强等人通过利用双向A*算法搜索一条最快路径作为ACO算法的初始解，然后使用该路径经过的节点为中心，线性更新信息素以提高较优解路径ACO算法的信息素浓度，通过改进传统ACO算法以解决物流机器人的路径规划[6]。衣麟卓等人利用ACO算法优化Dijkstra方法，求解多条件约束下海上搜救最快路径的全局最优解[7]。陈建宏等人考虑了应急行动过程中路径规划的目标条件和约束条件，通过在Dijkstra算法和A*算法中设计不同目标条件下的代价函数，并使用PostGIS数据库构建开发了机动路径规划计算软件[8]。陈敏等人将满足车辆运动学约束的最快路径作为距离度量引入RRT算法，这样便于求解最近邻搜索中的最快路径[9]。王磊等人通过寻找最快路径必经节点对A*算法的搜索方向进行约束，然后再对最快路径段进行组合得到最终的最快路径推荐[10]。张丹红等人为了获取两节点间更快的可行路径，使用多方位A*算法的搜索结果构建出任意两个巡逻点间的最快路径网络，其次，利用最快路径网络构建多点巡逻路径规划的目标函数，并使用ACO算法求解目标函数的全局最优解[11]。

启发式算法：张丽杰等人通过优化自适应果蝇算法，实现节点和路径容量受限的动态疏散路径规划[12]。王宇等人提出一种适用于复杂多边形边界与内部障碍物的三维作业区域的ACO算法的植保无人机路径规划方法[13]。李嘉伟等人通过利用广度优先搜索枚举SRIO网络中的节点构建网络拓扑信息，将路由跳数作为路由的成本，提出一种负载均衡最快路径路由算法[14]。王杰等人结合考虑交通状况、服务人口和现有公交线网布局等因素提出了一种公交线路规划约束模型[15]，袁佳泉等人通过使用Dijkstra算法获得巡检点间的最快路径，然后通过该算法得到的路径构建无向图，最后利用模拟退火ACO双层启发式算法求解全局最优解[16]。刘建仁通过分析城市物流配送过程中路径规划的影响因子，然后建立相关的约束条件，结合影响因子和约束条件构建路径规划的目标函数，最后利用ACO算法寻找目标函数的最优路径[17]。张强等人通过利用障碍物检测算法识别有效路径中间点的障碍物，然后结合引力场和边界条件推荐起点到中间点的局部路径，通过将中间点作为新的起点，进行反复迭代，直到起点与终点重合[18]。杜玉红等人对粒子群算法的动态惯性权重调整策略和改进的ACO算法的信息素更新规则进行了一个有机融合[19]。李宪强等人通过结合ACO算法与人工势场算法，提出了一种新的航迹规划寻优算法[20]。胡春阳等人引入头尾搜索机制和奖惩因子与信息素最大最小阈值信息素进行奖励，然后在ACO算法中使用遗传算法变异因子，有效解决了ACO算法的陷入局部最优和收敛速度慢等问题[21]。

最后简单阐述神经网络在路径规划上的相关应用。徐炜等人根据三维地形，将地势和障碍物进行几何化，并根据流场控制方程构建地形函数算法;将地形函数算法与Hopfield神经网络进行了有机结合[22]。孙艺彬等人基于脉冲耦合神经网络，将拓扑地图与PCNN网络进行结合，并由此设计距离和角度约束得出一种基于定向约束的PCNN网络的路径规划方法[23]。陈志军等人通过结合模糊神经网络和遗传算法建立了一种新的三维路径规划方法[24]。金飞虎等人提出利用ACO算法优化Hopfield神经网络来解决空间机器人多空间站访问问题[25]。卫玉梁等人针对智能小车全局路径规划和路障规避问题，采用RBF（Radial Basis Function）网络对Q学习算法的动作值函数进行逼近[26]。

综上所述，贪心算法的结构较为简单，但在大数据集下算法效率较低;而启发式算法能有效地提高弥补贪心算法的运行效率，准确实现最快路径推荐，但存在容易受到参数影响而陷入局部最优、收敛速度较慢等缺点;神经网络受网络的深度和复杂程度的影响，计算代价也比传统算法高。贪心算法是最早运用于路径推荐的算法，但启发式算法的发展逐渐取代了贪心算法，因此，就目前来看，在路径推荐方面启发式算法运用较多，但都是运用在机器人、AGV和TSP问题，在出租车路径推荐方面运用较少。因此，通过利用Bi-A*算法和最快路径更新规则有效弥补ACO算法的缺陷。最快路径推荐主要是通过历史数据获取空车位置和乘客位置，然后将空车位置和乘客位置加入路网节点，然后对节点进行路径推荐。针对ACO算法容收敛速度慢和容易陷入局部最优等问题，使用Bi-A*算法的代价估计函数优传统化ACO算法的启发式函数，增强ACO算法的全局搜索能力，最后利用本次循环得到的最快路径改进信息素的更新规则，加快了ACO算法收敛速度，由实验结果可得，Bi-A*-ACO算法比传统ACO算法在最快路径推荐具有更好的准确性。

2  Bi-A*-ACO算法

本节中，提出Bi-A*算法改进ACO算法寻找最快路径，以提高出租车在最短距离内快速寻找乘客路径推荐的准确性和有效性;并结合真实路网进行最快路径推荐。

2.1  算法概述

如图1所示，基于Bi-A*算法改进ACO算法的最快路径推荐方法主要包含数据预处理、数据建模和算法实现三个步骤，在数据预处理中，通过现有的移动轨迹大数据提取出乘客位置和空车位置;在数据建模中，Bi-A*算法优化ACO算法的启发式函数;在模型实现中，通过结合真实北京路网进行最快路径推荐，以验证最快路径推荐的有效性和准确性。

2.2  数据处理

在进行最快路径推荐前，需要构建路网，并对出租车轨迹数据进行过滤无关数据。路网主要是由节点（交叉路口）和路径组成，本文利用图论中的带权无向图表示路网，本小节先介绍带权的无向图，再进行数据处理和路网介绍。

2.2.1  带权的无向图

图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，用二元组G=（V，E）表示。无向图G如图2所示。

顶点集V=（v1，v2，v3，v4），边集E=（e12，e13，e14，e21，e23，e24，e31，e32，e34，e41，e42，e43）。

图的边给出相关的数据统称为权重;权重可以用一个节点和节点间的距离表示，带有权重的图称为网。带有权重的无向图如图3所示，图中数字表示两节点之间的权重。

2.2.2  路网

当GPS设备故障、出租车司机出现错误操作或信号延迟等情况时，可能造成出租车GPS信息错误，例如：当出租车途经隧道时信号较弱，导致了出租车发送消息延迟，出租车经纬度出现偏差等情况，一些駕驶员为了在休息时免受打扰，故意将GPS运营状态设为载客状态，但出租车实际为空载状态。因此，为了提高模型的准确性和可靠性，需要实施数据预处理剔除无效和错误数据。具体流程如图4（a）、图4（b）所示。

数据预处理主要包括数据过滤、数据提取和路网无向图。数据过滤是为了过滤GPS数据中的无效数据;数据提取是为了提取空车位置和乘客位置;路网无向图主要标注出道路交叉点作为无向图的节点。数据预处理步骤为：

Step1：数据过滤。通过读取HDFS文件中的数据，将数据转换为Spark中的弹性分布数据集（RDD），再对RDD进行分片，过滤掉无效数据，然后提取出所需要的字段（出租车ID、运营状态、时间、经度、纬度），按照出租车ID排序。

Step2：数据提取。根据Step1得出的结果寻找出相同出租车ID，分别提取运营状态连续为0（空车）、1（载客）、1（载客）的数据序列（运营状态连续为011表示一个载客事件发生）和运营状态连续为1（载客）、1（载客）、0（空车）的数据序列（运营状态连续为110表示一个下客事件发生），本文保留第二个运营状态为1（乘客位置）和第二个运营状态为0（空车位置）的出租车ID、运营状态、时间、经度、纬度，得出乘客坐标和空车坐标。

通过数据预处理得出乘客位置和空车位置，我们在路网中将乘客位置和空车位置作为一个道路节点。如图5所示。

图5中圆点为交叉路口，将乘客位置和空车位置添加在带权的有向图的节点集中并将其看为一个节点，权重主要是利用两个相连节点间的球面坐标距离作为带权有向图的权重。

Step3：路网无向图。通过Step2得到乘客位置和空车位置结合真实路网构建带权的无向图G=（V，E），如图5所示。

2.3  算法设计

ACO算法由Dorigo等人于1991年在第一届欧洲人工生命会议上提出，是一种用来寻找优化路径的概率型算法[27]。ACO算法本质上是一种启发式全局优化，该算法具有分布计算、信息正反馈和启发式搜索的特征。

传统ACO算法主要是通过移动概率来发现下一个移动对象，该算法的移动概率主要由当前节点到下一节点的启发式函数和信息素表示，如式（1）所示：

其中，ηie（t）为当前节点i与终点e之间的启发函数，是利用A*算法的代价估计函数代替原始的启发式函数;dij为当前节点i和下一节点j之间的球面距离，且dij=Rθ= Rarccos[cos（xi1-xj1）cos（xi2）cos（xj2）+sin（xi2）sin（xj2）];allowk（k=1，2，…，n）为蚂蚁k待访问路网节点的集合;τij（t）为从路网节点i转移到路网节点j的信息素浓度;α为信息素的重要程度，其值越大，信息素的浓度在概率转移中起的占比越大;β为启发函数的重要程度，其值越大，启发函数在概率转移中的占比越大，即蚂蚁会以最近的路网节点为最佳转移节点。

释放信息素的同时，路网节点间的信息素浓度也在逐渐散发，因此，当蚂蚁完成一次循环后，需要实时更新路径上的信息素浓度，如式（3）所示：

其中，参数ρ（0<ρ<1）为信息素挥发因子;n为蚂蚁数量。 为第k只蚂蚁在本次循环中的最快距离，作为信息素的更新规则;Δτij为所有蚂蚁在当前节点i转到下一节点j连接路径上释放信息素浓度之和，如式（4）所示：

其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量;dbest为第k只蚂蚁本次循环得出的最佳距离长度。

Bi-A*-ACO算法流程图如图5所示，本流程中利用雙向的A*算法主要是为了增强算法运行效率。

如图5所示，Bi-A*-ACO算法的实现过程主要由以下三个步骤组成：

Step1：通过Bi-A*算法获取最小代价函数作为ACO算法的启发式函数。

Step2：通过使用本次循环的最快路径改进ACO算法的信息素更新规则。

Step3：通过Step1和Step2得到的Bi-A*-ACO算法计算下一个节点的选择概率，详细的算法伪代码为：

Algorithm1  最快路径推荐

Input：路网无向图

1： Bi-A*→f（i）=dij+dje

2：→ACO算法

3：→ACO算法

4： Bi-A*-ACO算法

5：保存模型

Output：最快路径推荐

3  案例研究

通过与传统ACO算法比较，结合真实出租车轨迹数据验证所提出的Bi-A*优化的ACO算法对出租车进行最快载客路径推荐，并对实验结果进行详细分析。

3.1  数据描述

本案例使用的数据来源于2012年11月12 000辆出租车（北京市）所产生的GPS轨迹数据。该数据集由9亿多条GPS记录组成，如图6所示。

本实验使用14、36个路网节点为实验数据集，交叉路口（节点）坐标如表2、表3所示。

3.2  实验结果

通过大量的实验将ACO算法的参数初始化，如表4所示。

其中，n为蚂蚁数量，α为信息素的重要程度，β为启发函数的重要程度，参数ρ（0<ρ<1）为信息素挥发因子，Q为常数，表示蚂蚁循环一次所释放的信息素总量。

下面实验均是利用上述参数作为实验参数。

当数据集为14个路网节点时，Bi-A*-ACO算法和传统ACO算法实验结果如表5所示。

通过表5得出在相同参数下，利用Bi-A*算法优化的ACO算法在效率方面明显高于传统的ACO算法，由于数据集较少，在相同起始点时，Bi-A*-ACO算法虽然和传统ACO算法推荐的最快路径一致，但提出的算法在效率方面比传统ACO算法分别提高了54.573 7%、47.050 8%和61.568 8%。

为了进一步验证算法在路径推荐方面的有效性，通过增加数据集对优化的ACO算法进行有效性验证。

如表6所示当数据集增加至36个节点后，当起始点分别为1、36;20、7;10，27时，本文提出的Bi-A*-ACO算法比传统ACO算法在效率方面分别提高了74.4713%、78.5876%、74.1656%;在最快路径推荐方面，Bi-A*-ACO算法比传统ACO算法推荐的最快距离分别减少了54.874 1 m、56.478 5 m、21.857 8 m，实验结果表明，在效率和最快路径推荐方面Bi-A*-ACO算法明显优于传统ACO算法。

4  结  论

实验研究发现，本文提出的Bi-A*-ACO算法在14个路网节点数据集下，固定相同起始点时，优化算法和传统算法最快路径推荐的准确性一致，但是运行时间上优化算法比传统算法明显减少了一半，当数据集增加至36个路网节点时，Bi-A*-ACO算法不管是在运行效率方面还是最快路径推荐方面明显都比传统ACO算法效率、准确性更高。在未来工作中我们将加入道路好坏、交通状况对最快路径推荐的影响。

参考文献：

[1] 王迎，赵建军，李兴菊，等.基于交通大数据的车辆行驶路径规划综述 [J].软件导刊，2020，19（10）：50-54.

[2] 汤红杰，王鼎，皇攀凌，等.优化Dijkstra算法在工厂内物流AGV路径规划的研究 [J].机械设计与制造，2018（S1）：117-120.

[3] 邹益民，高阳，高碧悦.一种基于Dijkstra算法的机器人避障问题路径规划 [J].数学的实践与认识，2013，43（10）：111-118.

[4] 程林，王美玲，张毅.一种基于SuperMap GIS的改进Dijkstra算法 [J].地球信息科学学报，2010，12（5）：649-654.

[5] 李大东，孙秀霞，彭建亮，等.基于可视图法的改进Dijkstra算法 [J].电光与控制，2010，17（3）：40-43.

[6] 朱永强，孙宗涛.改进蚁群算法在物流机器人路径规划中的应用 [J].科学技术与工程，2020，20（30）：12467-12471.

[7] 衣麟卓.海上搜救最优路线规划模型设计与仿真 [J].舰船科学技术，2020，42（16）：34-36.

[8] 陳建宏，黄晓明.复杂环境下特种车辆应急机动路径规划研究 [J].计算机仿真，2020，37（7）：159-162.

[9] 陈敏，李笑，武交峰，等.基于距离度量学习的智能车辆路径规划 [J].计算机仿真，2020，37（7）：163-167.

[10] 王磊，孙力帆.引入必经点约束的路径规划算法研究 [J].计算机工程与应用，2020，56（21）：25-29.

[11] 张丹红，陈文文，张华军，等.A*算法与蚁群算法相结合的无人艇巡逻路径规划 [J].华中科技大学学报（自然科学版），2020，48（6）：13-18.

[12] 张丽杰，刘建昌，谭树彬.复杂建筑火灾中的人员疏散路径多目标规划 [J].东北大学学报（自然科学版），2020，41（6）：761-766.

[13] 王宇，王文浩，徐凡，等.基于改进蚁群算法的植保无人机路径规划方法 [J].农业机械学报，2020，51（11）：103-112+92.

[14] 李嘉伟，张激，赵俊才，等.一种SRIO网络负载均衡最短路径路由算法 [J].计算机工程，2020，46（3）：214-221+228.

[15] 王杰，杨坤，孙峰，等.一种基于GIS的公交线路规划方法 [J].广西大学学报（自然科学版），2019，44（5）：1269-1275.

[16] 袁佳泉，李胜，吴益飞，等.基于模拟退火蚁群算法的机器人路径规划方法 [J].计算机仿真，2019，36（10）：329-333.

[17] 刘建仁.考虑交通拥堵的城市物流配送路径规划研究 [J].现代电子技术，2020，43（23）：116-119+123.

[18] 张强，陈兵奎，刘小雍，等.基于改进势场蚁群算法的移动机器人最优路径规划 [J].农业机械学报，2019，50（5）：23-32+42.

[19] 杜玉红，张岩，赵焕峰.基于参数优化蚁群算法的机器人路径规划研究 [J].现代制造工程，2020（9）：7-14.

[20] 李宪强，马戎，张伸，等.蚁群算法的改进设计及在航迹规划中的应用 [J].航空学报，2020，41（S2）：213-219.

[21] 胡春阳，姜平，周根荣.改进蚁群算法在AGV路径规划中的应用 [J].计算机工程与应用，2020，56（8）：270-278.

[22] 徐炜，周兰凤，章民融.三维地形下基于Hopfield神经网络的路径规划算法 [J].计算机应用与软件，2019，36（10）：113-116+144.

[23] 孙艺彬，杨慧珍.基于定向约束的脉冲耦合神经网络路径规划 [J].计算机科学，2019，46（S2）：28-32.

[24] 陈志军，曾蒸.基于模糊神经网络和遗传算法的机器人三维路径规划 [J].重庆师范大学学报（自然科学版），2018，35（1）：93-99.

[25] 金飞虎，郭琦.基于蚁群算法的Hopfield神经网络在多空间站路径规划的应用研究 [J].计算机应用研究，2010，27（1）：51-53.

[26] 卫玉梁，靳伍银.基于神经网络Q-learning算法的智能车路径规划 [J] 火力与指挥控制，2019，44（2）：46-49.

[27] 张军，詹志辉.计算智能 [M].北京：清华大学出版社，2009.

作者简介：郑永玲（1995—），女，汉族，贵州毕节人，硕士研究生，研究方向：海量数据统计与分析;白宇（1994—），女，汉族，贵州仁怀人，硕士研究生，研究方向：海量数据统计与分析;杨楠（1997—），女，汉族，贵州盘县人，硕士研究生，研究方向：海量数据统计与分析;蒋顺英（1996—），女，汉族，贵州兴义人，硕士研究生，研究方向：海量数据统计与分析。