Journal
NETWORKS
Volume 59, Issue 1, Pages 181-189Publisher
WILEY-BLACKWELL
DOI: 10.1002/net.20487
Keywords
uncertainties; robustness; recovery; shortest path problem; NP-hardness; approximation
Funding
- Research Training Group [DFG-GRK 1408]
- Berlin Mathematical School
Ask authors/readers for more resources
In this article, we investigate two different recoverable robust (RR) models to deal with cost uncertainties in a shortest path problem. RR 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 optimizationno changes allowedand optimization on the flyan 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 RR setting. In our second model, the recovery set, that is, 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 with a min{2+beta,1/alpha} factor. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(1), 181-189 2012
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available