Article ID: | iaor20133909 |
Volume: | 207 |
Issue: | 1 |
Start Page Number: | 97 |
End Page Number: | 120 |
Publication Date: | Aug 2013 |
Journal: | Annals of Operations Research |
Authors: | Gabrel Virginie, Murat Ccile, Wu Lei |
Keywords: | robustness, shortest path |
In optimization, it is common to deal with uncertain and inaccurate factors which make it difficult to assign a single value to each parameter in the model. It may be more suitable to assign a set of values to each uncertain parameter. A scenario is defined as a realization of the uncertain parameters. In this context, a robust solution has to be as good as possible on a majority of scenarios and never be too bad. Such characterization admits numerous possible interpretations and therefore gives rise to various approaches of robustness. These approaches differ from each other depending on models used to represent uncertain factors, on methodology used to measure robustness, and finally on analysis and design of solution methods. In this paper, we focus on the application of a recent criterion for the shortest path problem with uncertain arc lengths. We first present two usual uncertainty models: the interval model and the discrete scenario set model. For each model, we then apply a criterion, called