Finding a path in the hierarchical road networks

摘要

In a hierarchical road network, all roads can be classified into two groups according to their attributes such as their speed limit and number of lane. By splitting the whole network into the high-level and low-level subnetworks, the size of the road network to be searched can be reduced, and more human-oriented paths can be obtained. In this work, we define a convenient path in the hierarchical road network and propose an algorithm for finding the path. The proposed algorithm produces a convenient and approximately shortest path with less computational efforts by reducing the number of nodes to be considered. The differences of the length of the paths produced by the proposed algorithm and existing algorithms and that of the shortest path of the whole network are discussed. Some experimental results are given to show the efficiency of the proposed algorithm.