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.