License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2017.3
URN: urn:nbn:de:0030-drops-78972
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7897/
Go to the corresponding OASIcs Volume Portal

Strasser, Ben

Dynamic Time-Dependent Routing in Road Networks Through Sampling

pdf-format:
OASIcs-ATMOS-2017-3.pdf (1 MB)

Abstract

We study the earliest arrival and profile problems in road networks with time-dependent functions as arc weights and dynamic updates. We present and experimentally evaluate simple, sampling-based, heuristic algorithms. Our evaluation is performed on large, current, production-grade road graph data with time-dependent arc weights. It clearly shows that the proposed algorithms are fast and compute paths with a sufficiently small error for most practical applications. We experimentally compare our algorithm against the current state-of-the-art. Our experiments reveal, that the memory consumption of existing algorithms is prohibitive on large instances. Our approach does not suffer from this limitation. Further, our algorithm is the only competitor able to answer profile queries on all test instances below 50ms. As our algorithm is simple to implement, we believe that it is a good fit for many realworld applications.

BibTeX - Entry

@InProceedings{strasser:OASIcs:2017:7897,
  author =	{Ben Strasser},
  title =	{{Dynamic Time-Dependent Routing in Road Networks Through Sampling}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{3:1--3:17},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{Gianlorenzo D'Angelo and Twan Dollevoet},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7897},
  URN =		{urn:nbn:de:0030-drops-78972},
  doi =		{10.4230/OASIcs.ATMOS.2017.3},
  annote =	{Keywords: shortest path, time-dependent, road graphs, preprocessing}
}

Keywords: shortest path, time-dependent, road graphs, preprocessing
Collection: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Issue Date: 2017
Date of publication: 04.09.2017

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