SHORTEST-PATH ALGORITHMS - AN EVALUATION USING REAL ROAD NETWORKS

The classic problem of finding the shortest path over a network has be en the target of many research efforts over the years. These research efforts have resulted in a number of different algorithms and a consid erable amount of empirical findings with respect to performance. Unfor tunately, prior research does not provide a clear direction for choosi ng an algorithm when one faces the problem of computing shortest paths on. real road networks. Most of the computational testing on shortest path algorithms has been based on randomly generated networks, which may not have the characteristics of real road networks. In this paper, we provide an objective evaluation of 15 shortest path algorithms usi ng a variety of real road networks. Based on the evaluation, a set of recommended algorithms for computing shortest paths on real road netwo rks is identified. This evaluation should be particularly useful to re searchers and practitioners in operations research, management science , transportation, and Geographic Information Systems.