一种基于道路网络层次拓扑结构的分层路径规划算法

鉴于平面最短路径算法应用于大规模网络规划中的效率不高,而分层算法引入"分而治之"策略,则能有效解决此难题。为了利用分层算法进行路径规划,首先研究了分层算法的数据基础——道路网络层次拓扑结构,其涉及基于道路等级的路网分层抽象、道路数据分区组织、以区域为单位的路网层次拓扑关系模型;接着提出了一种适用于LBS(基于位置的服务)的分层路径规划算法。该算法先通过距离值判断是否切换到上一层;然后利用启发式A*算法搜索入口和出口;最后使用双向策略搜索层内两点之间的最短路径。利用现实道路网络进行的实验分析结果表明,该算法能从本质上提高大规模网络中路径规划的效率。

A Hierarchical Route Planning Algorithm Based on Multi-level Topological Structure of Road Network

The efficiencies of planar shortest path algorithms deteriorate sharply with the expansion of the network size.However,this puzzle can be well resolved by hierarchical route planning algorithms which use "decompose and conquer" strategy to reduce search space essentially.Firstly,the paper studies the underlying data background of hierarchical algorithms,namely,the multi-level topological structure of road network,which covers road-class-specific level abstraction method region partition of road map data and intra-region hierarchical topological relationship model.Secondly,a hierarchical route planning algorithm is proposed for the optimal route calculation in location-based services(LBS).In detail,line distances between start nodes and goal nodes are applied to judge whether the node need to be switched to higher level.A modified heuristic A* algorithm is devised to search for the entrances to a higher level or the exits to a lower level.And a bidirectional strategy is adopted for intra-level optimal path computation.At last,some experiments using real road networks show that the proposed algorithm can largely improve the efficiency of route planning,especially for those cases with large-scale road network.