Combining Hierarchical and Landmark-Oriented Speed-Up Techniques for A * Algorithm

摘要

Computing a shortest path from one node to another in a directed graph is a very common task in practice. In order to improve the query efficiency of path planning algorithm for the Large-scale transportation network, We propose a new path planning algorithm. Our approach uses A* search in combination with Hierarchical and Landmark-oriented Speed-Up Techniques. We allow preprocessing the graph using a linear amount of extra space to store auxiliary information, and using this information to answer shortest path queries quickly. The experimental results indicate that it has higher query efficiency and more reasonable results in long-distance road routing.