基于层次策略的路径规划算法对比研究

为比较路径规划中基于层次策略的分层算法的计算效率和规划结果的合理性,选取基于预计算的分层算法和基于道路等级的分层分区算法这2类典型的分层路径规划算法,通过对2类算法基本原理的分析,并引入新分区算法和＂虚拟边＂等方法改进现有基于道路等级的分层分区算法以适应实际路网下的路径规划。选取广东省路网数据进行大规模测试,通过寻找＂最短路＂和＂最快路＂进行算法效率和路径规划结果的比较分析。测试结果表明改进的基于道路等级的分层分区算法计算效率更高,规划结果更符合出行偏好。

Comparative Study of Route Planning Algorithms Based on Hierarchical Strategy

Hierarchical strategy is widely used in route planning algorithms to improve the computing efficiency.Two classical algorithms including pre-computation-based hierarchical algorithm and classified-road-based hierarchical algorithm,are selected to compare the computing efficiency and planning rationality.Firstly,the basic ideas of the two algorithms were illustrated and then some improvements such as new partition algorithm and virtual link are taken to make the classified-road-based hierarchical algorithm more suitable for real road network.A large scale random test is taken on the road network of Guangdong Province.Both shortest path and fastest paths are computed.Experiment results prove that the classified-road-based hierarchical algorithm is more efficient and the planning result is more reasonable.