Fast and Delay-Robust Multimodal Journey Planning

We study journey planning in multimodal networks consisting of public transit plus an unrestricted transfer mode (e.g., walking or cycling). In order to provide good results in practice, algorithms must account for vehicle delays. Delay-responsive algorithms receive a continuous stream of delay updates and must return optimal journeys in the currently known delay scenario. Updates are incorporated in an update phase, which must be fast (e.g., a few seconds). The fastest known approach for multimodal journey planning is ULTRA, which precomputes shortcuts representing transfers between vehicles. This allows query algorithms to find Pareto-optimal journeys regarding arrival time and the number of public transit trips without any performance loss compared to pure public transit networks. However, the precomputation phase does not account for delays and is too slow to rerun during the update phase. We present Delay-ULTRA, a delay-responsive variant of ULTRA. Since accounting for all theoretically possible delays would yield an impractically large set of shortcuts, our approach precomputes shortcuts that are provably sufficient as long as delays do not exceed a configurable limit (e.g., 5 minutes). To handle delays above the limit (which are less frequent in practice), we propose a heuristic search for missing shortcuts that is fast enough to be run during the update phase. Our experimental evaluation on real-world data shows that Delay-ULTRA fails to find less than 0.02% of optimal journeys on metropolitan and mid-sized country networks, and 0.16% on the much larger Germany network. Considering that the available delay information in realistic applications is never perfectly accurate, these error rates are negligible. Query speed is at most twice as slow as ULTRA without delay information, and up to 8 times faster than the fastest exact algorithm, which does not require a preprocessing phase.