The shortest path problem on large-scale real-road networks
The computation of shortest paths between different locations on a road network appears to be a key problem in many applications. Often, a shortest path is required in a very short time. In this article, we try to find an answer to the question of which shortest path algorithm for the one-to-one shortest path problem runs fastest on a large real-road network. An extensive computational study is presented, in which six existing algorithms and a new label correcting algorithm are implemented in several variants and compared on the real-road network of The Netherlands. In total, 168 versions are implemented, of which 18 versions are variants of the new algorithm and 60 versions are new by the application of bidirectional search. In the first part of the article we present a mathematical framework and a review of existing algorithms. We then describe combinations of existing algorithms with bidirectional search and heuristic-estimate techniques based on Euclidean distance and landmarks. We also present some useful static reduction techniques. In the final part of the article we present results from computational tests on The Netherlands road network. The new algorithm, which combines concepts from previous work on buckets and label-correcting techniques, has generally the shortest running times of any of the tested algorithms. (C) 2006 Wiley Periodicals, Inc.
shortest path problem real-road network label correcting bidirectional search landmarks label setting heuristic estimate graph reduction preprocessing