• search hit 28 of 153
Back to Result List

Recoverable Robust Shortest Path Problems

Please always quote using this URN:urn:nbn:de:0296-matheon-10225
  • In this paper we investigate two different recoverable robust models to deal with cost uncertainties in a shortest path problem. Recoverable robustness extends the classical concept of robustness to deal with uncertainties by incorporating limited recovery actions after the full data are revealed. Our first model focuses on the case where the recovery actions are quite restricted: after a simple path is fixed in the first stage, in the second stage, after all data are revealed, any path containing at most k new arcs may be chosen. Thus, the parameter k can be interpreted as a mediator between robust optimization - no changes allowed - and optimization on the fly - an arbitrary solution can be chosen. Considering three classical scenario sets, which model uncertainties in the cost function, we show that this new problem is strongly NP-hard in all these cases and is not approximable, unless P=NP. This is in contrast to the robust shortest path problem, where, for example, an optimal solution can be computed efficiently for interval and Gamma-scenarios. For series-parallel graphs and interval scenarios, we present a polynomial time algorithm for this recoverable robust setting. In our second model the recovery set, i.e., the set of paths selectable in the second stage is not limited, but deviating from the previous choice comes at extra cost. Thus, a path chosen in the first stage produces renting costs modeled as an alpha-fraction of the scenario cost. For an arc taken in the second stage the remaining cost needs to be paid in addition to some extra inflation cost modeled by a beta-fraction of the scenario cost, if the arc was not reserved beforehand. The complexity status of this problem is similar to the robust case. Yet, for Gamma-scenarios the problem is again strongly NP-hard, but can be approximated.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christina Büsing
URN:urn:nbn:de:0296-matheon-10225
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/01/25
Release Date:2012/01/25
Tag:Recovery; Robust Optimization; Shortest Paths
Institute:Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05-06 Proceedings, conferences, collections, etc.
Preprint Number:873
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.