智能交通路径规划算法研究综述

2022-11-26卢东祥

电子科技 2022年7期

卢东祥

(盐城师范学院，江苏盐城 224002)

随着国家经济的发展和人民生活水平的提高，我国机动车保有量呈现快速增长的趋势。交通拥堵与安全等问题也逐渐成为严重影响中大城市工作、生活及安全的重要因素之一。按照发达国家的交通发展规律和成功经验，在考虑居民出行需求的前提下，解决交通的拥堵与安全问题主要依赖最新科技的应用，即通过引入人工智能、大数据及导航等科学技术来有效地提高城市交通的路网利用效率。根据这一理念，先进的信息技术、大数据、北斗导航与人工智能技术逐渐被综合运用于城市交通的管理过程中，为缓解城市交通压力和提高居民出行效率提供了切实可行的解决思路，形成了具有高利用效率的智能交通解决方案。路径规划是车辆定位和导航系统的核心功能之一，可分为单车辆路径规划与多车辆路径规划，二者间相辅相成，共同促进着智能交通系统的优化和发展。

为进一步提升城市交通的智能程度及利用率，国内外学者提出了具有借鉴价值和推广意义的研究。文献[1]综合利用蚁群算法(Ant Colony Optimization，ACO)与有限元，提出了具有较高性能的路径选择优化算法。在蚁群算法的基础上，文献[2]提出了最短路径规划算法，但其效率与实时性仍有可提高的空间。文献[3]系统总结了多种传统的路径规划算法，包括A*算法(A-Star)、Floyd算法、Dijkstra算法及蚁群算法等，进而提出多项路径规划算法的核心问题。在上述研究内容与成果的基础上，本文详细分析了智能交通的研究历程，深入探讨当前路径规划算法研究所存在的问题，并展望了其未来发展的方向。

1 路径规划研究

在城市交通领域中，随着基础设施与计算软件的快速发展，智能交通的路径规划算法逐渐由静态转化为动态。通常而言，动态路径规划算法的研究主要可分为实时性、并行性、控制系统及混合类型。

1.1 实时性

在早期研究中，静态规划算法是路径规划的主要研究内容，且产生了大量具有较高实用性的优质算法。然而在交通基础设施快速改善及优化的背景下，路况信息和交通现状随时有可能发生剧烈的变化。换言之，路径规划算法的权值必须及时按照当前的路况进行必要的调整，这便对路径规划算法提出了较高的实时性要求。

1.2 并行性

随着城市机动车保有量的逐渐增加，道路交通拥堵信息量也呈现出指数级的增长，这导致规划算法需考虑海量的数据与信息因素。但当前利用集中式串行性计算方法的设备难以处理规模庞大数据，这意味着利用并行性计算模式的规划算法将成为路径规划研究的重要方向。

1.3 控制系统

在大数据逐渐普及的背景下，智能交通需引入全方位的控制系统，才能够进一步提高其实际利用率。通常而言，智能交通中控制系统需制定交通流量的智能分配策略，包括交通信号灯的智能化控制、车辆转向延误和导航系统的更新等多种问题。但当前该系统的研究仍处于起步阶段，存在较大的提升和优化空间。

1.4 混合类型

在智能交通研究中，多种传统规划算法具有明显的优势，例如Dijkstra算法、Floyd算法及A*算法等，均已在路径规划领域得到了广泛的普及与应用。然而，这些优异的算法各自存在着不可忽视的缺点：Dijkstra算法的运行和实现速度较快，但其无法处理负权值；而Floyd算法可轻松计算节点间的最短距离，但其算法的时间复杂度较高，难以适应海量数据的计算；A*算法则融合Dijkstra算法及最佳优先算法(Best FS)的优点，但该算法不一定能获取最优解。总之，综合利用传统路径规划、深度学习(Deep Learning，DL)、人脸识别与图形拼接等多种算法，逐渐成为了路径规划研究的重要发展方向。

2 智能算法

人工智能的快速发展为计算机技术的研究引入了生物学启发式计算。基于这一现状，具有随机性、通用性和特定性的智能算法被应用于路径规划的研究中，并逐渐获得了广泛关注。

2.1 蚁群算法

20世纪90年代，文献[4～5]通过观察蚂蚁觅食的行为，首次提出了蚁群系统理论，以尝试解决经典的旅行商问题，得到了具有较高质量的结果。

基于通用蚁群算法，国内众多学者均曾尝试在路径规划研究中引入蚁群算法，并做出了一些值得借鉴的成果。文献[6]在蚁群算法的基础上，制定了最近邻居策略及目标引导函数，从而较好地解决了复杂地理环境下机器人的最优路径规划问题。文献[7]通过修改目标引导函数，进一步提高了蚁群算法的收敛速度，进而充分改进并优化了移动机器人的动态路径规划问题。文献[8]利用蚁群数量、启发因子与信息素挥发系统等参数调整的方法，对不同环境下的移动机器人进行了全局性仿真实验，并获得了全面的最佳匹配参数。以上工作的研究对象主要是具有移动功能的机器人，但其研究结果仍对智能交通的路径规划算法具有较高的实用性与可移植性。

此外，在同一时期内，诸多国外学者也通过蚁群算法及其改进算法，做出一系列具有较高参考意义的工作。文献[9]首次将强化蚁群算法应用于移动机器人路径规划问题中，对包含约束条件的连续函数优化问题提出了有效的解决思路，并进一步促进了特定条件下路径规划算法的改进与求解。文献[10]充分地考虑城市交通的负荷，提出了基于蚁群优化技术的最短路径规划算法。该算法在提高性能的同时，还兼顾了算法的性能及灵活性。文献[11]分别考虑车辆路径规划和商品配送问题，提出了救灾场景下基于蚁群算法的商品和车辆路径规划问题。该算法的运行效率和执行结果均达到了较为优秀的状态。文献[12]证明了有向无环图上单目标最短路径问题的蚁群优化算法多项式运行时间界，并首次从算法理论角度对蚁群算法的性能与运行效率给出了精确的评估。文献[13]通过扩展容量约束车辆路径问题，提出带回程的车辆路径问题，并利用改进蚁群算法实现了该问题的组合优化，具有较强的实用性与有效性。文献[14]在启发式蚁群算法的基础上，设计出具有应急疏散功能的多目标优化模型，解决了紧急情况下大型公共建筑撤离过程中的路径规划问题，并填补了这一应用领域的研究空白。文献[15]通过重新设置全局更新规则、干扰因子和信息素更新算子，提出了基于改进蚁群算法的道路权重模型，从而为城市交通中的机动车辆规划更优的出行路线。文献[16]通过引入实时性的物联网技术，以较大的幅度改进了蚁群算法的性能及效率，从而进一步实现了对导航系统中车辆路径规划的优化。文献[17]对比了蚁群算法和遗传算法(Genetic Algorithm，GA)在路径规划问题中的应用，并实现了此类算法中多项参数的调试与优化，从而给出了适用于云计算的分布式计算方法。文献[18]基于改进蚁群算法，提出了考虑信息反馈的车辆路径规划算法，并在垃圾运输和收集系统中得到了成功的应用。2017年，文献[19]通过调整算法步骤和结构，提出了基于改进蚁群算法的多目标优化调度模型，进而解决了路径规划问题在云计算时代的任务调度方法。2019年，文献[20]在改进蚁群算法的基础上，通过结合K-means算法(K-means Clustering Algorithm)与支持向量机技术，建立了智能交通中高速列车的无线定位模型。2020年，文献[21]提出了一种基于网格的交通网络拥挤概率量化模型。同时给出多项式时间之内的路径规划算法，从而实现了智能交通系统中的流量调节和调度。2021年，文献[22]提出了一种基于成对邻近学习的蚁群算法，通过利用用户节点间的接近程度，跟踪机动车辆的动态变化，实现了动态车辆路径规划问题的求解。

2.2 遗传算法

20世纪60年代，受生物遗传中变异、交叉和选择等行为的启发，文献[23～25]总结并提出了遗传算法。由此，该算法逐渐被应用于组合优化、图像处理及机器学习等诸多领域内。

2000年，文献[26]首次在模糊控制与导航系统中引入了通用遗传算法，并获取了优于随机决策表的规划路径。2001年，文献[27]汽车和运输技术大会上，利用常见的遗传算法，提出了智能交通系统中的路径优化方法，且从算法理论方向证明了遗传算法在路径规划研究中的重要作用，具有较强的原创性。在文献[26～27]的启发下，众多研究者开始考察遗传算法在路径规划研究中的应用。文献[28]有机结合禁忌搜索算法(Tabu Search)和遗传算法的优点，提出了具有智能化特征的混合遗传算法。该算法有效改善了公交车辆的动态运营决策效率，提升了服务质量。文献[29]在地理信息系统的基础上，通过引入遗传算法，增强了算法求解的随机性，并以更大概率接近复杂规划问题的最优解，改善了公路线性优化最终解的质量。文献[30]在机器学习及控制论的国际会议上，利用遗传算法和人工智能技术，提出了城市公共交通系统的调度算法与执行程序。该研究致力于提高公交系统的运行效率，具有非常强的前瞻性与参考性。文献[31]通过引入UMTS技术，提出了基于遗传算法的城市轨道交通优化网络规划设计工具，实现了路径规划与信号传输的同步设计和优化。在文献[30]的基础上，文献[32]综合利用有向图理论和遗传算法，提出了满足时间、成本及任务分配要求的路径规划算法，从而实现了路径规划问题的全新解决思路。与传统基于图的算法相比，文献[32]中的算法具有更为简单的实现方法和更高的效率。在同一时期，文献[33]在进化计算会议上，基于遗传算法的主要计算步骤，利用增加进化算子及更新表示环境的方法，提出了适用于静态和动态障碍物环境的分布路径规划算法。其进一步优化了路径规划算法的计算速度与鲁棒性能。此后，学界对于路径规划算法的研究进入高峰。文献[34]通过修改编码、交叉和变异等计算步骤，得到了适用于最优路径规划的改进遗传算法，为图论中最短路径问题提供了切实可行的解决方法，具有较高的学术价值及参考意义。文献[35]在地理空间信息系统中引入启发式的遗传算法，提出了具有并行计算功能的改进遗传算法，为路径规划问题的快速求解提供了一定的参考。此外，文献[36]通过改变遗传算法的计算方法和步骤，在智能运输系统中提出了具有自适应功能的平滑参数概率神经网络算法。该算法提供了企业级的解决方案，进一步提高了智能交通系统的利用率，并具有较强的实用性。在小型手持计算设备的快速发展背景下，文献[37]提出基于遗传算法的路线引导系统，其鲁棒性、准确性与计算效率均达到了较高水平。文献[38]在可行解空间中引入全局采样功能，并在遗传算法中融合传统的Dijkstra算法和A*算法，从而给出了具有决策功能的路径规划算法。在2010～2016年间，大多数学者的关注点逐渐转移至路径规划算法的系统性与实时性。文献[39～41]重点对智能交通系统中的路径规划算法进行了系统化的改造，扫除了遗传算法在地理空间信息系统中的实用性障碍。文献[42]则着重提高了智能交通系统中遗传算法的计算速度与效率，优化了路径规划算法的实时性。2017年后，在大数据、云计算和人工智能技术快速发展的背景下，由于算法效果的优化空间不断减少，路径规划算法的研究成果数量呈现了下降趋势，但仍出现不少值得借鉴的研究成果。文献[43]提出了基于改进遗传算法的车辆导航系统多目标规划算法，大幅缩短了机动车辆的路径距离。文献[44]通过开发遗传算法的框架，对高速公路的拥挤情况及行程时间做出较为精确的校准和评估。文献[45]在无线传感器网络中引入自适应克隆遗传算法，有效提高了算法的全局搜索能力，为复杂的交通环境提供一种有效的任务分配策略，并进一步提升了物联网时代下智能交通的通行效率。