A Multilevel Design for Scalable Pareto-Optimal Public Transit Queries

This thesis investigates routing algorithms for public transit networks. Especially in the context of countrywide or continental-sized transit networks, current state-of-the-art algorithms reach their limits: Fast query times can usually only be achieved through time-consuming preprocessing and high memory overhead. Until now, no algorithm has been able to efficiently compute Pareto-optimal journeys with respect to minimal arrival time and minimal number of transfers with both low memory consumption and minimal preprocessing effort on large networks.

We present T-REX (Transfer-Ranked EXploration), a new algorithm that narrows this gap by combining the state-of-the-art Trip-Based Public Transit Routing Algorithm with multilevel partitioning techniques. The underlying idea is to partition stops into multilevel cells and identify relevant trans-
fers for long-distance travel during a short precomputation phase. T-REX then uses this precomputed information to restrict the search space during a query, effectively pruning unnecessary local transfers. Unlike previous partition-based approaches, T-REX has two key advantages. Firstly, the query phase operates directly on the existing graph structure, without the need to build any additional data structures. ... mehrSecondly, as T-REX focuses on transfers rather than lines or trips,
it can directly determine which events are worth exploring next, avoiding the overhead of computing the next reachable events. In this work, T-REX is described in detail, compared with existing methods, and evaluated in extensive experiments on real public transit data.

The algorithm is able to handle even large networks such as the whole of Europe with preprocessing times of a few minutes. At the same time, it allows for query times with an average runtime of around 18 ms, compared to 222 ms achieved by previous state-of-the-art algorithms, and requires only 515 MB additional memory compared to TB. These properties make T-REX particularly suitable for use in interactive real-time applications, e.g., in mobile navigation services.