Dijkstra Beats RAPTOR for Transit Routing with Buffer Times
Researchers revisit classical Dijkstra-based algorithms for public transit routing and demonstrate that Time-Dependent Dijkstra (TD-Dijkstra) outperforms the state-of-the-art RAPTOR-based approach (MR) for unlimited transfers without preprocessing. They identify a critical flaw in existing TD-Dijkstra implementations: preprocessing that filters dominated connections is unsound when stops have buffer times, since it cannot distinguish between seated passengers continuing without delay and transferring passengers who must wait. The authors introduce Transfer Aware Dijkstra (TAD), which scans entire trip sequences rather than individual edges to correctly handle buffer times while maintaining over 2x speed improvements on London and Switzerland networks.
TL;DR
- TD-Dijkstra outperforms RAPTOR-based MR algorithm for public transit routing with unlimited transfers, contrary to recent algorithmic evolution in the field
- Existing TD-Dijkstra preprocessing filters are mathematically unsound for networks with buffer times at stops, creating correctness issues
- Transfer Aware Dijkstra (TAD) fixes the buffer time problem by processing full trip sequences instead of individual edges while preserving performance gains
- Experiments show greater than 2x speedup over MR with optimal results on real networks both with and without buffer constraints
Why It Matters
This work challenges the assumption that newer RAPTOR-based algorithms are categorically superior to classical approaches for transit routing, revealing that systematic re-examination of foundational algorithms can yield both correctness improvements and performance gains. For the broader AI and optimization community, it demonstrates the importance of rigorous algorithmic analysis when assumptions about real-world constraints like buffer times are embedded in preprocessing steps.
Business Impact
Transit routing powers navigation apps, trip planning services, and logistics optimization for millions of users daily. A 2x speedup with correct handling of real-world buffer constraints directly improves user experience and reduces infrastructure costs for mapping platforms, transit agencies, and mobility services that rely on fast, accurate routing.
Key Implications
- Classical algorithms deserve systematic re-evaluation against newer approaches rather than assumption-based dismissal, potentially unlocking performance and correctness gains in other domains
- Real-world constraints like buffer times must be explicitly modeled in algorithm design and preprocessing, not assumed away, to avoid subtle correctness bugs in production systems
- RAPTOR-based methods may not be optimal for all transit routing scenarios, particularly those with complex transfer rules or buffer requirements common in European networks
What to Watch
Monitor adoption of TAD in commercial routing engines and whether other transit networks with buffer constraints report similar speedups and correctness improvements. Watch for whether this work prompts broader re-examination of preprocessing assumptions in other graph algorithms used in logistics, navigation, and network optimization.
Subscribe to the newsletter
The latest stories and analysis, delivered to your inbox.
Free. No spam. Unsubscribe any time.
