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
Go to the corresponding OASIcs Volume Portal

Hansknecht, Christoph ; Richter, Alexander ; Stiller, Sebastian

Fast Robust Shortest Path Computations

OASIcs-ATMOS-2018-5.pdf (0.5 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI