Improved Highway Hierarchical Algorithm Based on Contracted Network Strategy

Abstract:

In the pretreatment process, Highway Hierarchical(HH) algorithm faces such problems as the compressing of network into a ring road, the storage way of pretreatment data and a complete calculation of the optimal route. Non cycle compressing, tiered storage and local shortest path storage are introduced to improve the efficiency of the algorithm. The test of the road network of Guangdong Province of China shows that with the improved HH algorithm, the computational efficiency increases by 5 times, and the search space reduces by 4 times.

Key words:contracted network; Highway Hierarchical algorithm; path planning