Closing the Performance Gap Between Multimodal and Public Transit Journey Planning

This thesis studies the design of journey planning algorithms for multimodal passenger transport networks. In particular, we consider the combination of public transit (e.g., trains, buses, trams) with one or several transfer modes that represent road-based individual transport (e.g., walking, cycling, e-scooters). Currently, there is a significant performance gap between multimodal journey planning algorithms and their unimodal counterparts. One major reason for this is that state-of-the-art multimodal algorithms combine existing techniques for exploring the individual network parts, but the fastest available techniques for road networks are not usable within this context. The second major reason is that multimodal journey planning requires the simultaneous optimization of multiple criteria. However, existing approaches can only efficiently handle Pareto optimization for two criteria: the arrival time and the number of used trips. With additional criteria, the number of Pareto-optimal solutions becomes excessively large, which slows down the algorithms and causes an overwhelming amount of different choices to be presented to the user.
... mehr

This thesis employs the Algorithm Engineering methodology to develop techniques that close this performance gap. The first major contribution is ULTRA (UnLimited TRAnsfers), a speedup technique that allows any public transit algorithm to operate on multimodal networks without incurring a performance loss. It is based on the shortcut hypothesis, which states that the number of paths in the transfer graph that are required to bridge the gap between two public transit vehicles in at least one optimal journey is small. ULTRA exploits this by precomputing these paths and condensing them into a set of shortcut edges. We first present ULTRA for a basic scenario with one transfer mode and two optimization criteria: arrival time and number of trips. Afterward, we extend it to a variety of extended scenarios to show that the shortcut hypothesis still holds in them. The extensions include queries with multiple target locations, additional criteria, multiple transfer modes, and vehicle delays.

The second focus of this thesis is on designing new, efficient query algorithms for multimodal scenarios. Currently, the fastest public transit algorithm that does not require expensive preprocessing is Trip-Based Routing (TB), which achieves its good performance by operating on the level of individual events (i.e., departures and arrivals of public transit vehicles at stations) rather than vehicle routes and stations. Already in a public transit context, TB requires a short preprocessing step that computes relevant transfers between vehicles. We show that ULTRA can replace this preprocessing step in a multimodal context. Starting from there, we extend the event-based concept of TB to scenarios with additional criteria. We show that under certain conditions, Pareto-optimizing a third criterion in addition to the arrival time and the number of trips can be done in polynomial time. In particular, we demonstrate that considering the time spent in the transfer modes as the third criterion is crucial in order to achieve a good solution quality. Our approach yields the new query algorithms McTB (Multicriteria Trip-Based Routing) and HydRA (Hybrid Routing Algorithm), which can efficiently handle scenarios with three or more criteria, respectively. Furthermore, we integrate our algorithms with restricted Pareto sets, a state-of-the-art approach for reducing the size of the Pareto sets in a methodical manner.

The combination of ULTRA with the event-based query algorithms and restricted Pareto sets closes the performance gap in all considered scenarios, which we show through extensive experiments on real-world networks representing metropolitan areas and countries of varying sizes. On all networks, our algorithms are fast enough for interactive applications. Depending on the scenario, they outperform the state of the art by one to three orders of magnitude.