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.2018.5
URN: urn:nbn:de:0030-drops-97100
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9710/
Hansknecht, Christoph ;
Richter, Alexander ;
Stiller, Sebastian
Fast Robust Shortest Path Computations
Abstract
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}).
BibTeX - Entry
@InProceedings{hansknecht_et_al:OASIcs:2018:9710,
author = {Christoph Hansknecht and Alexander Richter and Sebastian Stiller},
title = {{Fast Robust Shortest Path Computations}},
booktitle = {18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)},
pages = {5:1--5:21},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-95977-096-5},
ISSN = {2190-6807},
year = {2018},
volume = {65},
editor = {Ralf Bornd{\"o}rfer and Sabine Storandt},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9710},
URN = {urn:nbn:de:0030-drops-97100},
doi = {10.4230/OASIcs.ATMOS.2018.5},
annote = {Keywords: Graph Algorithms, Shortest Paths, Robust Optimization}
}
|
Keywords: |
|
Graph Algorithms, Shortest Paths, Robust Optimization |
|
Collection: |
|
18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
28.08.2018 |
