Optimization Online


Fast robust shortest path computations

Christoph Hansknecht(c.hansknecht***at***tu-braunschweig.de)
Alexander Richter(a.richter***at***tu-braunschweig.de)
Sebastian Stiller(sebastian.stiller***at***tu-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


Download: [PDF]

Entry Submitted: 07/02/2018
Entry Accepted: 07/02/2018
Entry Last Modified: 07/02/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society