2026-08-25T18:47:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27145 2026-08-25T13:18:15Z ddc:004 open_access

T-REX: Fast and Dynamic Journey Planning for Continental-Scale Public Transit Networks Sauer, Jonas Steil, Patrick Witt, Sascha Public transit routing graph algorithms algorithm engineering We present T-REX (Transfer-Ranked EXploration), a new algorithm for journey planning in public transit networks on the country and continental scale. Our algorithm applies the principles of multi-level overlays to Trip-Based Public Transit Routing (TB). Using a multi-level partition of the network, T-REX identifies transfers between trips that are relevant for long-distance travel in a short precomputation phase. This information is then used to prune irrelevant local transfers during a query. Like other state-of-the-art algorithms, T-REX Pareto-optimizes arrival time and the number of used trips. T-REX dramatically outperforms previous overlay-based algorithms for three key reasons: (1) a better partition, (2) reducing the search space by focusing on transfers rather than trips, and (3) a redesigned query algorithm with improved memory efficiency and throughput. As a result, T-REX answers queries in less than 10ms on a network of Europe, including local and long-distance transit. This constitutes a speedup of 20 compared to TB and 80 compared to algorithms without preprocessing. The memory footprint is moderate and the precomputation takes only two minutes, while real-time schedule updates can be incorporated in a few seconds. These properties make T-REX the first public transit journey planning algorithm that fulfills the requirements of interactive real-time applications on the continental scale. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonas Sauer and Patrick Steil and Sascha Witt 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.9 urn:nbn:de:0030-drops-271458 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode