基于A*算法的动态路径研究

郑甜丽 任彧

摘要：为了优化拥堵状态的城市路网，对现有车载自主网（VANET， Vehicular Ad-hoc Network）[1]的通信协议进行了相应的改变，设计了交互式的通信策略，克服传统算法的不足，提出了一种基于A*算法的最优路径。首先，基于实时交通信息，对道路属性（道路长度、车辆速度、道路密度）信息进行收集；然后通过车载自组织网络中的路由协议获取道路信息进行拥塞判定，在获得大量的实时道路信息的基础上，利用经典的A*算法优化车辆行驶路径，使得改进后的算法可以在已知某路段拥堵的情况下选择一条最优路径，最大限度地满足驾驶者的驾驶需求。

关键词：车载自组网；路由协议；信息采集；最优路径

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2019）04-0201-03

Abstract： In order to optimize the congested urban road network， the communication protocol of the existing Vehicle Autonomous Network （VANET， Vehicular Ad-hoc Network） [1] has been changed accordingly. An interactive communication strategy has been designed to overcome the shortcomings of the traditional algorithm. An optimal path based on A* algorithm is proposed. Firstly， based on real-time traffic information， road attribute information （road length， vehicle speed， road density） is collected； then road information is obtained through routing protocols in vehicular ad hoc networks for congestion determination. On the basis of obtaining a large amount of real-time road information， the classical A* algorithm is used to optimize vehicle routing， so that the improved algorithm can be used in the already existing one. Choosing an optimal route under the condition of knowing a certain section of road congestion can satisfy the driver's driving demand to the greatest extent.

Key words： Vehicle Ad Hoc Network； routing protocol； information collection； optimal path

智能交通系统是将网络间通信、计算机处理以及控制等应用到智能化系统中来，从而缓解日益凸显的交通拥挤、事故不断等道路交通问题。这个领域的大多数研究越来越集中在开发更为有效的算法。Dijkstra[2]和A*[3]算法是两种熟知的最短路径算法，其他的算法基本就是这两种算法的变体，不同的尝试是为了加快单一来源和单一目标情况下的最短路径搜索。我们在进行理论研究的时候往往把它定义为简单的如何寻找到最短的距离，在现实的交通情况下，对最短路径的选择都可以认为是在计算最优路径的方案。本文的主要内容就是在获知了道路拥堵情况的基础上选择一条由一点到另外一点的最短路径，应用图论原理将城市道路图形化，改进A*算法，使之可以适用于处于拥堵状态的城市路网。

1算法设计

1.1计算参数

在最优路径选择方法中，路径的权值计算也是通过实时路况数据得到，两个过程均以实时路况信息为基础，从而路径选择结果的动态特性。文献中有多种计算动态路径权值的方法。另外也有许多文献改进了许多权值的计算参数：

1.1.1 机动性[4]

1.1.2 绕行指数[5]

1.2改进措施

原始经典的A*算法的估价函数是以距离为标准进行判断的，改进的A*算法将以路段的权值作为标准，并且可以在某些路段存在拥堵的情况下进行最佳路径搜索。这样改进的意义在于：在实际的交通路网中路段出现拥堵的情况非常常见，因此极有可能理论上可以满足距离最短的最佳路径的某处出现拥堵，在这样的情况下，重新探索新的路径以保证车辆能尽快从起点移动至终点，即保证时间上最短。虽然新确定的路径可能会绕远，但在拥堵时使车辆运行的时间最短比距离最短更有意义。

1.3 算法流程

通过比较图6和图7可知，道路畅通时的最佳路径P0为S→3→7→11→12→16→D，这条路径的权值为11。而当路况出现拥堵情况时选择的最佳路径Ps为S→1→4→5→9→13→D，这条路径的权值为18。虽然权值较大，但是在拥堵情况下这种路径的选择可以帮助驾驶者避开拥堵路线，较快的抵达目的地。

3 结束语

对城市的实际交通路网进行了等效，将其近似为一个加权的有向图，在拥堵情况下，在该有向图中再加入一项拥堵路线集作为寻找路径时的依据。接下来说明了交通路段的权值确定方法，最后改进了A*算法，使得其可以在道路拥堵时避开拥堵的交叉口进行路径选择从而确定最佳路径。由于在车载自组网的路由协议来获取信息时，没有考虑到每个节点的信息存储能力与处理过程。改进的A*算法只实现了部分仿真，没有做出全部结果，此算法许多局限性和不足之处，所以还需要通过以后的学习和研究使其不斷完善。

参考文献：

[1] Hyun Yu， Joon Yoo， Sanghyun Ahn. A VANET Routing based on the real-time road vehicle density in the city environment[D]. Seoul：University of Seoul

[2] 潘若愚，褚伟，杨善林. 基于Dijkstra-PD-ACO算法的大城市公交线路优化与评价方法研究[J]. 中国管理科学，2015，23（9）：106-115.

[3] 熊壬浩，刘羽. A*算法的改进及并行化[J].计算机应用，2015，35（7）：1843-1848.

[4] 白尘. 交通路网中最优路径算法的道路权重选择[J]. 中国管理信息化，2009，12（15）：54-56.

[5] 张征. 面向功能的支路设计与单向交通组织评价[D]. 郑州：郑州大学，2016.

[6] 雷东升，诸彤宇. 一种基于实时路况信息的动态路径规划算法[J]. 计算机科学，2008，35（4）：28-30.

【通联编辑：谢媛媛】