- Fast robust shortest path computations Christoph Hansknecht(c.hansknechttu-braunschweig.de) Alexander Richter(a.richtertu-braunschweig.de) Sebastian Stiller(sebastian.stillertu-braunschweig.de) 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 $\sum_{a\in A}\frac{\bar{d}(a)}{d (a)} \leq \Gamma$. Each path is measured by the length in its worst-case scenario. A classic result 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(1 + \epsilon)^{-1})$ computations of the nominal problem. Keywords: Graph Algorithms, Shortest Paths, Robust Optimization Category 1: Network Optimization Citation: Download: [PDF]Entry Submitted: 07/02/2018Entry Accepted: 07/02/2018Entry Last Modified: 07/02/2018Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.