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 computing shortest paths in massive road networks with traffic predictions. Existing techniques follow a two phase approach: In an offline, preprocessing step, a database index is built. The index only depends on the road network and the traffic patterns. The path start and end are the input of the query phase, in which shortest-paths are computed. All existing techniques have a 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. We perform an extensive experimental study on a set of real world instances and compare our approach with state-of-the-art techniques. Our approach achieves up to 30 times smaller indexes than competing approaches. Additionally, our index can be updated within a few minutes if traffic patterns change.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsdatum 28.10.2020
Sprache Englisch
Identifikator KITopen-ID: 1000125774
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page