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.
Montemanni, Roberto e M, Gambardella Luca. "Robust shortest path problems with uncertain costs" Working paper, 2008.
Robust shortest path problems with uncertain costs
Montemanni Roberto;
2008
Abstract
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.Pubblicazioni consigliate
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris