2026-07-21T14:13:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2751 2024-03-06T10:28:43Z ddc:004 open_access

Engineering Time-Dependent Many-to-Many Shortest Paths Computation Geisberger, Robert Sanders, Peter time-dependent travel time table algorithm engineering vrp 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Robert Geisberger and Peter Sanders 2010 Is Part Of OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2010.74 urn:nbn:de:0030-drops-27511 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.74 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode