KIT | KIT-Bibliothek | Impressum | Datenschutz

Space-efficient, fast and exact routing in time-dependent road networks

Strasser, Ben; Wagner, Dorothea; Zeitz, Tim

Abstract:
We study the problem of computing shortest paths in massive road networks with traffic predictions. Incorporating traffic predictions into routing allows, for example, to avoid commuter traffic congestions. Existing techniques follow a two-phase approach: In a preprocessing step, an index is built. The index depends on the road network and the traffic patterns but not on the path start and end. The latter are the input of the query phase, in which shortest paths are computed. All existing techniques have either large index size, slow query running times, or may compute suboptimal paths. In this work, we introduce CATCHUp (Customizable Approximated Time-dependent Contraction Hierarchies through Unpacking), the first algorithm that simultaneously achieves all three objectives. The core idea of CATCHUp is to store paths instead of travel times at shortcuts. Shortcut travel times are derived lazily from the stored paths. We perform an experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves the fastest preprocessing, competitive query running times and up to 30 times smaller indexes than competing approaches.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000125767
Veröffentlicht am 06.11.2020
Originalveröffentlichung
DOI: 10.4230/LIPIcs.ESA.2020.81
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2020
Sprache Englisch
Identifikator ISBN: 978-3-9597716-2-7
ISSN: 1868-8969
KITopen-ID: 1000125767
Erschienen in 28th Annual European Symposium on Algorithms (ESA 2020). Ed.: F. Grandoni
Veranstaltung 28th Annual European Symposium on Algorithms (ESA 2020), Online, 07.09.2020 – 09.09.2020
Verlag Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Dagstuhl
Seiten Art.-Nr.: 81
Serie Leibniz International Proceedings in Informatics (LIPIcs) ; 173
Bemerkung zur Veröffentlichung Die Veranstaltung fand wegen der Corona-Pandemie als Online-Event statt
Schlagwörter realistic road networks, time-dependent route planning, shortest paths
Nachgewiesen in Scopus
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page