2026-08-11T06:20:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12947 2024-03-06T10:51:09Z ddc:004 open_access

Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks Strasser, Ben Wagner, Dorothea Zeitz, Tim realistic road networks time-dependent route planning shortest paths 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ben Strasser and Dorothea Wagner and Tim Zeitz 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.81 urn:nbn:de:0030-drops-129479 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.81 eng https://creativecommons.org/licenses/by/3.0/legalcode