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.2020.8
URN: urn:nbn:de:0030-drops-131441
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13144/
Go to the corresponding OASIcs Volume Portal

Kontogiannis, Spyros ; Paraskevopoulos, Andreas ; Zaroliagis, Christos D.

Time-Dependent Alternative Route Planning

pdf-format:
OASIcs-ATMOS-2020-8.pdf (1 MB)

Abstract

We present a new method for computing a set of alternative origin-to-destination routes in road networks with an underlying time-dependent metric. The resulting set is aggregated in the form of a time-dependent alternative graph and is characterized by minimum route overlap, small stretch factor, small size and low complexity. To our knowledge, this is the first work that deals with the time-dependent setting in the framework of alternative routes. Based on preprocessed minimum travel-time information between a small set of nodes and all other nodes in the graph, our algorithm carries out a collection phase for candidate alternative routes, followed by a pruning phase that cautiously discards uninteresting or low-quality routes from the candidate set. Our experimental evaluation on real time-dependent road networks demonstrates that the new algorithm performs much better (by one or two orders of magnitude) than existing baseline approaches. In particular, the entire alternative graph can be computed in less than 0.384sec for the road network of Germany, and in less than 1.24sec for that of Europe. Our approach provides also "quick-and-dirty" results of decent quality, in about 1/300 of the above mentioned query times for continental-size instances.

BibTeX - Entry

@InProceedings{kontogiannis_et_al:OASIcs:2020:13144,
  author =	{Spyros Kontogiannis and Andreas Paraskevopoulos and Christos D. Zaroliagis},
  title =	{{Time-Dependent Alternative Route Planning}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{8:1--8:14},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Dennis Huisman and Christos D. Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13144},
  URN =		{urn:nbn:de:0030-drops-131441},
  doi =		{10.4230/OASIcs.ATMOS.2020.8},
  annote =	{Keywords: time-dependent shortest path, alternative routes, travel-time oracle, plateau and penalty methods}
}

Keywords: time-dependent shortest path, alternative routes, travel-time oracle, plateau and penalty methods
Collection: 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Issue Date: 2020
Date of publication: 10.11.2020

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