KIT | KIT-Bibliothek | Impressum | Datenschutz

Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks

Strasser, Ben; Wagner, Dorothea; Zeitz, Tim

We study the problem of quickly computing point-to-point 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 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 38 times smaller indexes than competing approaches.

Open Access Logo

Verlagsausgabe §
DOI: 10.5445/IR/1000131432
Veröffentlicht am 13.04.2021
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2021
Sprache Englisch
Identifikator ISSN: 1999-4893
KITopen-ID: 1000131432
Erschienen in Algorithms
Verlag MDPI
Band 14
Heft 3
Seiten Art.-Nr.: 90
Vorab online veröffentlicht am 16.03.2021
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