Comparative Study of Route Planning Algorithms Based on Hierarchical Strategy
Zhou Xing · Journal of Transport Information and Safety · 2012
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.