2026-08-04T09:25:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13140 2024-03-06T10:31:07Z ddc:004 open_access

Integrating ULTRA and Trip-Based Routing Sauer, Jonas Wagner, Dorothea Zündorf, Tobias Algorithms Journey Planning Multi-Modal Public Transportation We study a bi-modal journey planning scenario consisting of a public transit network and a transfer graph representing a secondary transportation mode (e.g., walking or cycling). Given a pair of source and target locations, the objective is to find a Pareto set of journeys optimizing arrival time and the number of required transfers. For public transit networks with a restricted, transitively closed transfer graph, one of the fastest known algorithms solving this bi-criteria problem is Trip-Based Routing [Witt, 2015]. However, this algorithm cannot be trivially extended to unrestricted transfer graphs. In this work, we combine Trip-Based Routing with ULTRA [Baum et al., 2019], a preprocessing technique that allows any public transit algorithm that requires transitive transfers to handle an unrestricted transfer graph. Since both ULTRA and Trip-Based Routing precompute transfer shortcuts in a preprocessing phase, a naive combination of the two leads to a three-phase algorithm that performs redundant work and produces superfluous shortcuts. We therefore propose a new, integrated preprocessing phase that combines the advantages of both and reduces the number of computed shortcuts by up to a factor of 9 compared to a naive combination. The resulting query algorithm, ULTRA-Trip-Based is the fastest known algorithm for the considered problem setting, achieving a speedup of up to 4 compared to the fastest previously known approach, ULTRA-RAPTOR. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jonas Sauer and Dorothea Wagner and Tobias Zündorf 2020 Is Part Of OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2020.4 urn:nbn:de:0030-drops-131408 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.4 eng https://creativecommons.org/licenses/by/3.0/legalcode