The Open Cybernetics & Systemics Journal

2015, 9 : 306-312
Published online 2015 May 29. DOI: 10.2174/1874110X01509010306
Publisher ID: TOCSJ-9-306

A Heuristic Bidirectional Hierarchical Path Planning Algorithm Based on Hierarchical Partitioning

Han Zhi-Heng , Rui Xiaoping , Dong Cheng-wei , Song Xian-Feng and Wang Jing
College of Resources &Environment, University of Chinese Academy of Sciences, Beijing, 100049, P.R. China.

ABSTRACT

This paper proposes an improvement in the efficiency of the use of a path planning algorithm in large scale road networks. This was achieved by addressing three aspects: hierarchical layers of road networks with sub areas in each layer, selection of the layer entrance point, and the use of bidirectional search technology. This led to a new heuristic bidirectional hierarchical path planning algorithm. The algorithm was tested using Beijing road data, which showed that the time and space efficiency of the new algorithm improved significantly compared to classical algorithms. It also proved that it is reasonable to combine different kinds of path planning algorithm acceleration technologies, and that their effects can be superimposed.

Keywords:

Bidirectional, heuristic function, hierarchical, path planning.