 | The ACM Journal of Experimental Algorithmics |
Volume 4, Article 6, 1999
A Computational Study of Routing Algorithms for Realistic
Transportation Networks
by
and
and
http://www.jea.acm.org/1999/JacobRouting/
Abstract:
We carry out an experimental analysis of a number of shortest
path (routing) algorithms investigated in the context of the TRANSIMS
(TRansportation ANalysis and SIMulation System) project.
The main focus of the paper is to study how various heuristic
as well as exact solutions and associated data structures affect the
computational performance of the software developed
for realistic transportation networks. For this purpose we have
used a road network representing with a
high degree of resolution the Dallas -- Fort Worth urban area.
We discuss and experimentally analyze
various one-to-one shortest path algorithms.
These include classical exact algorithms studied in the literature as well
as heuristic solutions that are designed to take into account the
geometric structure of the input instances.
Computational results are provided to empirically compare the efficiency
of various algorithms. Our studies indicate that a modified
Dijkstra's algorithm is computationally fast and an excellent candidate
for use in various transportation planning applications
as well as ITS related technologies.
- Keywords: Experimental Analysis, Transportation Planning,
Design and Analysis of Algorithms, Network Design, Shortest Paths Algorithms
- CR Categories:
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
April 1, 1999
|
February 3, 2000
|
February 4, 2000
|
May 10, 2000
|
Last updated and validated May 10, 2000, by editor@jea.acm.org