  


Fast robust shortest path computations
Christoph Hansknecht(c.hansknechttubraunschweig.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 worstcase 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 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(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/2018 Modify/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  