Search papers, labs, and topics across Lattice.
The paper revisits Dijkstra-based algorithms for public transit routing with unlimited transfers, demonstrating that Time-Dependent Dijkstra (TD-Dijkstra) can outperform RAPTOR-based algorithms like MR. It identifies that TD-Dijkstra's connection filtering is unsound when stops have buffer times, as it fails to distinguish between seated and transferring passengers. To address this, the authors introduce Transfer Aware Dijkstra (TAD), which scans entire trip sequences to correctly handle buffer times, achieving a 2x speed-up over MR while maintaining optimality.
A simple modification to Dijkstra, Transfer Aware Dijkstra (TAD), doubles the speed of public transit routing while correctly handling buffer times, outperforming state-of-the-art RAPTOR-based algorithms.
In recent years, RAPTOR based algorithms have been considered the state-of-the-art for path-finding with unlimited transfers without preprocessing. However, this status largely stems from the evolution of routing research, where Dijkstra-based solutions were superseded by timetable-based algorithms without a systematic comparison. In this work, we revisit classical Dijkstra-based approaches for public transit routing with unlimited transfers and demonstrate that Time-Dependent Dijkstra (TD-Dijkstra) outperforms MR. However, efficient TD-Dijkstra implementations rely on filtering dominated connections during preprocessing, which assumes passengers can always switch to a faster connection. We show that this filtering is unsound when stops have buffer times, as it cannot distinguish between seated passengers who may continue without waiting and transferring passengers who must respect the buffer. To address this limitation, we introduce Transfer Aware Dijkstra (TAD), a modification that scans entire trip sequences rather than individual edges, correctly handling buffer times while maintaining performance advantages over MR. Our experiments on London and Switzerland networks show that we can achieve a greater than two time speed-up over MR while producing optimal results on both networks with and without buffer times.
