Round-Based Public Transit Routing

We study the problem of computing all Pareto-optimal journeys in a dynamic public transit network for two criteria: arrival time and number of transfers. Exist-ing algorithms consider this as a graph problem, and solve it using variants of Dijkstra’s algorithm. Unfortu-nately, this leads to either high query times or subop-timal solutions. We take a different approach. We in-troduce RAPTOR, our novel round-based public transit router. Unlike previous algorithms, it is not Dijkstra-based, looks at each route (such as a bus line) in the network at most once per round, and can be made even faster with simple pruning rules and parallelization us-ing multiple cores. Because it does not rely on pre-processing, RAPTOR works in fully dynamic scenarios. Moreover, it can be easily extended to handle flexible departure times or arbitrary additional criteria, such as fare zones. When run on London’s complex public transportation network, RAPTOR computes all Pareto-optimal journeys between two random locations an or-der of magnitude faster than previous approaches, which easily enables interactive applications.