Abstract
This paper evaluates the performance of shortest-path algorithms for large-scale metropolitan simulations within the TRANSIMS (TRansportation ANalysis and SIMulation System) project. While classical Dijkstra’s algorithm serves as a robust baseline, we demonstrate that a "Modified A*" heuristic, which leverages the Euclidean geometry of real-world road networks, can achieve up to a 40x speedup in routing queries. Our analysis of the Dallas Fort-Worth metropolitan network shows that these performance gains come with minimal loss in path accuracy, making such heuristics ideal for processing millions of individual traveler trips in time-dependent, multi-modal environments.
Introduction
In the late 1990s, the TRANSIMS project sought to revolutionize urban planning by simulating the second-by-second movements of millions of travelers across entire cities. A core computational challenge of this system is the "one-to-one" shortest path problem, which must be solved millions of times to generate realistic travel plans.
Traditional academic research often focuses on routing in random graphs or regular grids. However, real-world transportation networks possess unique characteristics: a low average degree (approximately 2.6), non-uniform density, and a roughly Euclidean structure where straight-line distance serves as a reliable proxy for travel time. This study investigates how these properties can be exploited to find algorithms that are fast, extensible to multi-modal transport, and capable of handling time-dependent traffic delays.
Methods
We compared four primary algorithmic approaches implemented in C++ using an object-oriented framework:
- Dijkstra’s Algorithm with Binary Heaps: Used as the gold standard for exact shortest paths.
- A* Search: An extension of Dijkstra that uses a Euclidean distance heuristic to bias the search toward the destination.
- Modified A* ("Overdo" Heuristic): A novel variation where the Euclidean heuristic is multiplied by an "overdo" parameter. This forces a more aggressive, focused search. While technically inadmissible, it aims for significant computational savings.
- Bidirectional Dijkstra: A simultaneous search from both the origin and destination.
The evaluation was conducted on a high-resolution road network of the Dallas Fort-Worth (DFW) metropolitan area, comprising approximately 9,863 nodes and 14,750 links, representing 10.3 million trips over a 24-hour period.
Results and Discussion
Performance and Accuracy Trade-offs
The "Overdo" A* algorithm demonstrated remarkable efficiency. With an overdo parameter of 10, the algorithm achieved a 5x speedup over standard Dijkstra. Increasing the parameter to 99 resulted in a nearly 40x speedup. Crucially, the loss in accuracy was minimal; even at the highest speedup, the maximum relative error was only 16%, with the vast majority of paths remaining within 5% of the optimal length. This "near-optimal" performance is generally sufficient for large-scale urban planning.
Algorithmic Efficiency vs. Data Structures
Our findings suggest that in sparse, real-world networks, the choice of algorithm (i.e., the number of nodes visited) is far more critical than the fine-tuning of underlying data structures. For instance, replacing binary heaps with Fibonacci heaps yielded diminishing returns compared to the gains provided by the A* heuristic.
Constraints and Multi-modality
While the Euclidean heuristic provides a significant advantage in road networks, extending these models to multi-modal systems (e.g., incorporating bus and train schedules) introduces substantial complexity. Our tests showed that multi-modal routing caused a 30x slowdown compared to simple road routing. Furthermore, bidirectional search proved unsuitable for these applications because arrival times at the destination are often unknown in time-dependent networks, making it difficult to initiate the backward search.
Conclusion
The use of Euclidean heuristics in a "Modified A*" framework provides a scalable solution for the massive routing requirements of metropolitan simulations. By trading a small degree of optimality for significant speed gains, researchers can efficiently model complex urban dynamics. Future applications of this work include real-time in-vehicle navigation systems, where personalized, time-sensitive route planning is essential.
Summary updated