License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2020.81
URN: urn:nbn:de:0030-drops-129479
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12947/
Go to the corresponding LIPIcs Volume Portal

Strasser, Ben ; Wagner, Dorothea ; Zeitz, Tim

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

pdf-format:
LIPIcs-ESA-2020-81.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{strasser_et_al:LIPIcs:2020:12947,
  author =	{Ben Strasser and Dorothea Wagner and Tim Zeitz},
  title =	{{Space-Efficient, Fast and Exact Routing in Time-Dependent Road Networks}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{81:1--81:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12947},
  URN =		{urn:nbn:de:0030-drops-129479},
  doi =		{10.4230/LIPIcs.ESA.2020.81},
  annote =	{Keywords: realistic road networks, time-dependent route planning, shortest paths}
}

Keywords: realistic road networks, time-dependent route planning, shortest paths
Collection: 28th Annual European Symposium on Algorithms (ESA 2020)
Issue Date: 2020
Date of publication: 26.08.2020
Supplementary Material: https://github.com/kit-algo/catchup

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI