2026-07-22T00:15:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9710 2024-03-06T10:30:26Z ddc:004 open_access

Fast Robust Shortest Path Computations Hansknecht, Christoph Richter, Alexander Stiller, Sebastian Graph Algorithms Shortest Paths Robust Optimization We develop a fast method to compute an optimal robust shortest path in large networks like road networks, a fundamental problem in traffic and logistics under uncertainty. In the robust shortest path problem we are given an s-t-graph D(V,A) and for each arc a nominal length c(a) and a maximal increase d(a) of its length. We consider all scenarios in which for the increased lengths c(a) + bar{d}(a) we have bar{d}(a) <= d(a) and sum_{a in A} (bar{d}(a)/d(a)) <= Gamma. Each path is measured by the length in its worst-case scenario. A classic result [Bertsimas and Sim, 2003] minimizes this path length by solving (|A| + 1)-many shortest path problems. Easily, (|A| + 1) can be replaced by |Theta|, where Theta is the set of all different values d(a) and 0. Still, the approach remains impractical for large graphs. Using the monotonicity of a part of the objective we devise a Divide and Conquer method to evaluate significantly fewer values of Theta. This methods generalizes to binary linear robust problems. Specifically for shortest paths we derive a lower bound to speed-up the Divide and Conquer of Theta. The bound is based on carefully using previous shortest path computations. We combine the approach with non-preprocessing based acceleration techniques for Dijkstra adapted to the robust case. In a computational study we document the value of different accelerations tried in the algorithm engineering process. We also give an approximation scheme for the robust shortest path problem which computes a (1 + epsilon)-approximate solution requiring O(log(d^ / (1 + epsilon))) computations of the nominal problem where d^ := max d(A) / min (d(A)\{0}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christoph Hansknecht and Alexander Richter and Sebastian Stiller 2018 Is Part Of OASIcs, Volume 65, 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2018.5 urn:nbn:de:0030-drops-97100 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode