首页 | 本学科首页   官方微博 | 高级检索  
     检索      

基于转向限制和延误的双向启发式最短路径算法
引用本文:郑年波,李清泉,徐敬海,宋莺.基于转向限制和延误的双向启发式最短路径算法[J].武汉大学学报(信息科学版),2006,31(3):256-259.
作者姓名:郑年波  李清泉  徐敬海  宋莺
作者单位:1. 武汉大学空间信息与网络通信技术研究中心,武汉市珞喻路129号,430079;武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079
2. 武汉大学测绘遥感信息工程国家重点实验室,武汉市珞喻路129号,430079
3. 武汉大学空间信息与网络通信技术研究中心,武汉市珞喻路129号,430079
基金项目:中国科学院资助项目;湖北省武汉市科技攻关项目
摘    要:提出了基于节点的交通网络拓扑关系模型,描述交通网络的物理连通性以及逻辑连通性;根据对偶图的思想,定义搜索节点结构,处理交叉口转向限制和延误;改进传统的Dijkstra算法,提出了基于搜索节点的双向启发式A^*算法,使用二叉堆优先级队列存储扩展节点,RB-tree存储标记节点。实验表明,本算法在效率和结果两方面都能满足车辆导航系统路径规划的要求。

关 键 词:车辆导航系统  路径规划  最短路径算法  交通网络  转向限制和延误
文章编号:1671-8860(2006)03-0256-04
修稿时间:2005年12月31

A Bidirectional Heuristic Shortest Path Algorithm with Turn Prohibitions and Delays
ZHENG Nianbo,LI Qingquan,XU Jinghai,SONG Ying.A Bidirectional Heuristic Shortest Path Algorithm with Turn Prohibitions and Delays[J].Geomatics and Information Science of Wuhan University,2006,31(3):256-259.
Authors:ZHENG Nianbo  LI Qingquan  XU Jinghai  SONG Ying
Abstract:Firstly,a node-based topology relationship model of transport network is presented,in which the physical connection and the logical connection are described.Secondly,the structure of search node is defined in the sight of dual graph theory as a solution for turn prohibitions and delays in road intersections.At last,a bidirectional heuristic A~(*) algorithm based on search node is examined.
Keywords:vehicle navigation system  route planning  shortest path algorithm  transport network  turn prohibitions and delays
本文献已被 CNKI 维普 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号