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

被引：32

作者：

韩刚

蒋捷

陈军

曹元大

机构：

[1] 国家基础地理信息中心,国家基础地理信息中心,国家基础地理信息中心,北京理工大学计算机科学工程系北京,北京理工大学计算机科学工程系,北京,北京,北京,北京

来源：

测绘学报 | 2002年 / 04期

关键词：

弧段; 交通网络; 转向限制; Dijkstra算法;

D O I：

暂无

中图分类号：

P208 [测绘数据库与信息系统];

学科分类号：

070503 ; 081603 ; 0818 ; 081802 ;

摘要：

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

引用

页码：366 / 368

页数：3

共 7 条

[1]

The Development and Industrialization of GPS Vehicle Navigation Systems. ZHOU Chun-ping. . 1998

[2]

On Finding Minimum Routes in a Network with Turn Penalties. CALDWELL T. Communications of the ACM . 1961

[3]

Shortest Route Algorithm with Movement Prohibition. EASA S M. Transportation Research . 1985

[4]

Improved Shortest Path Algorithms for Transport Networks. VLIET D V. Transportation Research . 1977

[5]

Vehicle Location and Navigation Systems. ZHAO Yi-lin. . 1999

[6]

Expected Performance of Dijkstra’s Shortest Path Algorithm. GOLDBERG A V,TARJAN R E. . 1996

[7]

The Minimum Route Problem for Networks with Turn Penalties and Prohibitions. KIRBY R F,POTTS R B. Transportation Research . 1969

← 1 →