Anytime Algorithm For Point-to-Point Shortest Path Problem On Large-scale Road Network

Finding shortest path on graph is a fundamental problem, which has been widely applied in many fields. Among these applications, traffic navigation on road network has become increasingly important. But with the rapid development of information technology, road network tends to contain more details, which means the number of vertexes and arcs in road network is very large. For example, the New York City road map we used in experiments contains264,346nodes and733,846edges. For this new feature of problem, the traditional shortest path algorithm takes a long time to find a shortest path in large-scale road network, therefore fails to meet the practical needs.Anytime algorithm is an algorithm which can return a valid solution to a problem even if it’s interrupted before it ends. The algorithm is expected to find better solution when there is more time to run. For the point to point shortest path problem, an anytime algorithm can be interrupted at any time and return a path. If the algorithm can run longer, then it should find a shorter path. Since this anytime algorithm can find a relatively short path quickly, and can also return a shortest path if there is enough time to run. This algorithm gets a balance between running time and length of path.The main work involved in this paper are:1, Analyzing and comparing the preprocessing algorithms on graph through experiments.In this paper we describe several preprocessing algorithms on graph, and analyze the results of experiment on each map from preprocessing time, proportion of covered edges and speed ratio to Dijkstra algorithm. Then we point out the characteristics of each algorithm. We also propose a preprocessing algorithm called Scatter in this paper.2, Analyzing and comparing the existing anytime algorithms on point to point shortest path problem.We introduce three anytime algorithms, which can be used to solve point to point shortest path problem. We compare these algorithms and explain the difference of each algorithm. The results of the experiment show that using calculation information from last round may mislead the current searching.3, Proposing an anytime algorithm called APWA*(asynchronous parallel weighted A*).To make a good use of redundant resources in modern computer, APWA*runs several weighted A*algorithms simultaneously. Since each weighted A*has different parameter, they will finish their searching at different time and find different path. When APWA*is interrupted, it will select a shortest path to return. We say this algorithm is an anytime algorithm because it finds shorter path if it has more time to run.