一种基于道路网络层次拓扑结构的分层路径规划算法
李清泉1, 郑年波2, 徐敬海2, 宋莺2(1.[1]武汉大学测绘遥感信息工程国家重点实验室，武汉 430079，[2]武汉大学交通研究中心，武汉 430079;2.[1]武汉 大学测绘遥感信息工程国家重点实验室，武汉 430079，[2]武汉 大学交通研究中心，武汉 430079) 摘 要
鉴于平面最短路径算法应用于大规模网络规划中的效率不高，而分层算法引入“分而治之”策略，则能有效解决此难题。为了利用分层算法进行路径规划，首先研究了分层算法的数据基础——道路网络层次拓扑结构，其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型；接着提出了一种适用于LBS（基于位置的服务）的分层路径规划算法。该算法先通过距离值判断是否切换到上一层；然后利用启发式A^＊算法搜索入口和出口；最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明。该算法能从本质上提高大规模网络中路径规划的效率。
关键词
A Hierarchical Route Planning Algorithm Based on Multi-level Topological Structure of Road Network
() Abstract
Keywords
location-based services route planning shortest path algorithms multi-level topological structure hierarchical algorithms
|
中国图象图形学报 │ 京ICP备05080539号-4 │ 本系统由