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

An Arc Based Dijkstra Algorithm for Road Turning Penalty in Vehicle Navigation System

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

Vehicle navigation system is a fast developing field of GIS application in recent years, and route planning is one of core modules in the system. The traditional Dijkstra algorithm is based on the nodes relationship of 'directed graph' and transportation attributes is appended on nodes. In fact, the turning penalty is not only related to nodes but also related to arcs in road network. If using the nodes relationship to represent the turning penalty, a transforms must be take from relationship between two links to relationship among three nodes. The transform largely expands the space and time and increases searching complexity. In order to overcome these problems, we present a method that the turn penalty should attach to arcs using node link table to present the connection of network and link link table to represent the turn penalty. An arc based Dijkstra algorithm for turning penalty is presented to take advantage of this method. Test results show that the arcs based algorithm can efficiently implement the route planning in consideration of computing with turn penalty.