车载导航系统中顾及道路转向限制的弧段Dijkstra算法

摘要

路径规划作为组成车载导航系统的核心模块,其效率对整个系统有着至关重要的影响.传统路径规划常用的Dijkstra算法是根据道路"有向图"中的节点进行计算,相关的交通属性附加在道路节点上.事实上,道路转向限制不仅与节点(交叉口)有关,而且与相连的2条道路弧段有关.若要用节点表达道路转向限制,需要把2条弧段间的转向关系转换为相邻的3个节点之间的关系.这种转换增大存储空间和转换时间的开销,还增加了搜索的复杂度.为了解决这一问题,提出将原来附属于节点上的转向关系转移到相应的弧段上,用节点-弧段关系表达网络的连通性,用弧段-弧段转向关系表达交叉路口的转向限制.在此基础上,提出了一种顾及导航转向限制的弧段Dijkstra算法.试验表明,该算法能够有效地进行顾及道路转向限制的路径规划.