Recoverable Robust Shortest Path Problem Under Interval Budgeted Uncertainty Representations

This article deals with the recoverable robust shortest path problem under interval uncertainty representations. In this problem, a first-stage path is computed, which can be modified to some extent after observing changes in the cost structure. The uncertain second-stage arc costs are modeled by intervals, and the robust min-max criterion is used to compute an optimal solution. The problem is known to be strongly NP-hard and also hard to approximate in general digraphs. However, until now its complexity for acyclic digraphs was unknown. In this article, it is shown that the problem in acyclic digraphs can be solved in polynomial time for the traditional interval uncertainty and all natural neighborhoods known from the literature. More efficient algorithms for layered and arc series-parallel digraphs are constructed. Hardness results for general digraphs are also strengthened. Finally, some exact and approximate methods of solving the problem under interval budgeted uncertainty are proposed.