基于转向限制和延误的双向启发式最短路径算法

被引：33

作者：

郑年波 ^{[1
]}

李清泉 ^{[1
]}

徐敬海 ^{[2
]}

宋莺 ^{[1
]}

机构：

[1] 武汉大学空间信息与网络通信技术研究中心

[2] 武汉大学测绘遥感信息工程国家重点实验室

来源：

武汉大学学报(信息科学版) | 2006年 / 03期

关键词：

车辆导航系统; 路径规划; 最短路径算法; 交通网络; 转向限制和延误;

D O I：

10.13203/j.whugis2006.03.017

中图分类号：

U495 [电子计算机在公路运输和公路工程中的应用];

学科分类号：

0838 ;

摘要：

提出了基于节点的交通网络拓扑关系模型,描述交通网络的物理连通性以及逻辑连通性;根据对偶图的思想,定义搜索节点结构,处理交叉口转向限制和延误;改进传统的Dijkstra算法,提出了基于搜索节点的双向启发式A*算法,使用二叉堆优先级队列存储扩展节点,RB-tree存储标记节点。实验表明,本算法在效率和结果两方面都能满足车辆导航系统路径规划的要求。

引用

页码：256 / 259

页数：4

共 7 条

[1] 带转向延误和限制的最短路径问题及其求解方法 [J].