KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Geisberger, Robert; Sanders, Peter

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.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000097650
Veröffentlicht am 20.08.2019
Originalveröffentlichung
DOI: 10.4230/OASIcs.ATMOS.2010.74
Scopus
Zitationen: 6
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Proceedingsbeitrag
Jahr 2010
Sprache Englisch
Identifikator ISBN: 978-3-939897-20-0
ISSN: 2190-6807
KITopen-ID: 1000097650
Erschienen in 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS’10) Hrsg.: Thomas Erlebach; Marco Lübbecke
Verlag Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl
Seiten 74–87
Serie OpenAccess Series in Informatics ; 14
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page