License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2010.74
URN: urn:nbn:de:0030-drops-27511
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2751/
Go to the corresponding OASIcs Volume Portal

Geisberger, Robert ; Sanders, Peter

Engineering Time-Dependent Many-to-Many Shortest Paths Computation

pdf-format:
7.pdf (0.5 MB)

Abstract

Computing distance tables is important for many logistics problems like the vehicle routing problem (VRP).
While shortest distances from all source nodes in S to all target nodes in T are time-independent, travel times are not.
We present the first efficient algorithms to compute time-dependent travel time tables in large time-dependent road networks.
Our algorithms are based on time-dependent contraction hierarchies (TCH), currently the fastest time-dependent speed-up technique.
The computation of a table is inherently in Theta(|S|*|T|), and therefore inefficient for large tables.
We provide one particular algorithm using only Theta(|S|+|T|) time and space, being able to answer queries two orders of magnitude faster than the basic TCH implementation.
If small errors are acceptable, approximate versions of our algorithms are further orders of magnitude faster.

BibTeX - Entry

@InProceedings{geisberger_et_al:OASIcs:2010:2751,
  author =	{Robert Geisberger and Peter Sanders},
  title =	{{Engineering Time-Dependent Many-to-Many Shortest Paths Computation}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{74--87},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Thomas Erlebach and Marco L{\"u}bbecke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2751},
  URN =		{urn:nbn:de:0030-drops-27511},
  doi =		{10.4230/OASIcs.ATMOS.2010.74},
  annote =	{Keywords: time-dependent, travel time table, algorithm engineering, vrp}
}

Keywords: time-dependent, travel time table, algorithm engineering, vrp
Collection: 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)
Issue Date: 2010
Date of publication: 01.09.2010

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