Study Of Pre-computation And Query Technique For Shortest Path Problem On Road Network

Finding the shortest path on graph is a classic problem on algorithm design. Also it plays an important role in the fields of route scheduling, GPS navigation and LBS service. Shortest path problem on road networks is specific because of massive nodes, frequent computation request and strong demand for real-time query. Traditional algorithms for shortest path problem cannot meet these requirements above.The model of "pre-processing and query" is a two-phase method for the problem of shortest-path on road networks. On the first phase, original data is pre-processed to get the intermediate data; On the second phase, given the source node and terminal node, every query will be answered quickly using the intermediate data. The thought of two phases comes from the fact that road networks are static. The first phase only needs to be computed once.The main work involved in this paper includes:1, Performance analysis for main algorithms of the shortest-path problem based on the model of "pre-processing and query";In this paper we focus on the two main strategies based on the model of "pre-processing and query":spatial-coherence-based methods and vertex-importance-based approaches. We pick the representative algorithms to compare the pre-processing time, memory consumption and query efficiency.2, Representative nodes picking strategy based on an efficient pre-computation technique for approximation distance query in road networksThe accuracy of the technique is determined by representative nodes picking strategy, so how to divide regions on graph and how to allocate representatives will influent the efficiency a lot. In this paper we propose a new strategy for dividing regions and allocating representatives, then analyze its influence on accuracy of query.3, Estimation strategy for the length of shortest-path by simulating the real-time queries on real road networks.In this paper we simulate the real scene of objects moving in road networks and propose a better strategy for computing the approximated distance between two nodes. Then we compare the distance error and time consumption by using different strategy on the simulation system.