刘 斌，陈贤富，程 政

(中国科学技术大学 信息科学技术学院，安徽 合肥 230027)

一种基于A*算法的动态多路径规划算法

刘 斌，陈贤富，程 政

(中国科学技术大学 信息科学技术学院，安徽 合肥 230027)

车载导航系统中最重要的功能是路径规划，传统车载导航设备大多采用静态算法，没有采用实时交通信息规划出的路径可能不是最优路径。结合一种动态行程时间表对传统A*算法进行调整，可以有效利用路网实时交通数据规避拥堵路线，从而实现动态路径规划。另外，实际应用中，单一的优化路径往往不能满足需求，对此提出重复路径惩罚因子的概念，构造出了一种多路径规划算法，可以在路径相似度与路径通行代价之间取得平衡，避免了传统K最短路径(K Shortest Paths, KSP)算法路径相似度过高的缺点。

动态路径规划；A*算法；动态行程时间表；重复路径惩罚因子；KSP

0 引言

路径规划算法是智能交通系统(Intelligent Transportation Systems, ITS)的重要组成部分之一，尽管现实世界的实时交通信息在不断变化，但目前大部分车载导航系统采用的仍是静态的路径规划算法[1]，如A*算法[2]、Dijkstra算法[3]。此类算法假定道路通行代价不会改变，大多采用道路长度、宽度等静态属性作为路权计算方式，不能反映实时动态路况。

针对动态路径规划算法，参考文献[4]采用D*star算法对A*算法进行了改进；参考文献[5]针对道路的动态通行时间计算问题，提出了一种路网中道路动态通行时间表，表中记录了每个路段每个时间段的行程时间，由此得出了车辆经过路段的通行时间计算方法。……