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 stgraph 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 worstcase 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 speedup the Divide and Conquer of Theta. The bound is based on carefully using previous shortest path computations. We combine the approach with nonpreprocessing 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:15:21},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {9783959770965},
ISSN = {21906807},
year = {2018},
volume = {65},
editor = {Ralf Bornd{\"o}rfer and Sabine Storandt},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9710},
URN = {urn:nbn:de:0030drops97100},
doi = {10.4230/OASIcs.ATMOS.2018.5},
annote = {Keywords: Graph Algorithms, Shortest Paths, Robust Optimization}
}
2018
Keywords: 

Graph Algorithms, Shortest Paths, Robust Optimization 
Seminar: 

18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018)

Issue date: 

2018 
Date of publication: 

2018 