KIT | KIT-Bibliothek | Impressum | Datenschutz

An efficient solution for one-to-many multi-modal journey planning

Sauer, Jonas; Wagner, Dorothea; Zündorf, Tobias

We study the one-to-many journey planning problem in multi-modal transportation networks consisting of a public transit network and an additional, non-schedule-based mode of transport. Given a departure time and a single source vertex, we aim to compute optimal journeys to all vertices in a set of targets, optimizing both travel time and the number of transfers used. Solving this problem yields a crucial component in many other problems, such as efficient point-of-interest queries, computation of isochrones, or multi-modal traffic assignments. While many algorithms for multi-modal journey planning exist, none of them are applicable to one-to-many scenarios. Our solution is based on the combination of two state-of-the-art approaches: ULTRA, which enables efficient journey planning in multi-modal networks, but only for one-to-one queries, and (R)PHAST, which enables efficient one-to-many queries, but only in time-independent networks. Similarly to ULTRA, our new approach can be combined with any existing public transit algorithm that allows a search to all stops, which we demonstrate for CSA and RAPTOR. For small to moderately sized target sets, the resulting algorithms are nearly as fast as the pure public transit algorithms they are based on. ... mehr

Verlagsausgabe §
DOI: 10.5445/IR/1000138880
Veröffentlicht am 14.10.2021
DOI: 10.4230/OASIcs.ATMOS.2020.1
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsdatum 10.11.2020
Sprache Englisch
Identifikator ISBN: 978-3-9597717-0-2
ISSN: 2190-6807
KITopen-ID: 1000138880
Erschienen in 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Ed.: D. Huisman
Veranstaltung Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), Online, 07.09.2020 – 08.09.2020
Verlag Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH (LZI)
Seiten Art.-Nr.: 1
Serie OpenAccess Series in Informatics (OASIcs) ; 85
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page