Robust shortest path problems with uncertain costs

Data coming from real-world applications are very often affected by uncertainty. On theother hand, it is difficult to translate uncertainty in terms of combinatorial optimization. Inthis paper we study a combinatorial optimization model to deal with uncertainty in arc costsin shortest path problems. We consider a model where feasible arc cost scenarios are describedvia a convex polytope. We present a computational complexity result and we discuss exactalgorithms for two different robust optimization criteria. We finally present experimentalresults showing that the proposed approaches are suitable to be used on realistic size instances.