摘要
提出了基于节点的交通网络拓扑关系模型,描述交通网络的物理连通性以及逻辑连通性;根据对偶图的思想,定义搜索节点结构,处理交叉口转向限制和延误;改进传统的Dijkstra算法,提出了基于搜索节点的双向启发式A*算法,使用二叉堆优先级队列存储扩展节点,RB-tree存储标记节点。实验表明,本算法在效率和结果两方面都能满足车辆导航系统路径规划的要求。
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.
出处
《武汉大学学报（信息科学版）》
EI
CSCD
北大核心
2006年第3期256-259,共4页
Geomatics and Information Science of Wuhan University
基金
国家自然科学基金资助项目(4027109340401051)
武汉市科技计划资助项目(20021002044)
关键词
车辆导航系统
路径规划
最短路径算法
交通网络
转向限制和延误
vehicle navigation system
route planning
shortest path algorithm
transportnetwork
turn prohibitions and delays
