New models for the robust shortest path problem: complexity, resolution and generalization

Virginie Gabrel (), Cécile Murat () and Lei Wu ()

Annals of Operations Research, 2013, vol. 207, issue 1, 97-120

Abstract: 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 bw-robustness (originally proposed by B. Roy) which defines a new measure of robustness. According to each uncertainty model, we propose a formulation in terms of large scale integer linear program. Furthermore, we analyze the theoretical complexity of the resulting problems. Our computational experiments perform on a set of large scale graphs. By observing the results, we can conclude that the approved solvers, e.g. Cplex, are able to solve the mathematical models proposed which are promising for robustness analysis. In the end, we show that our formulations can be applied to the general linear program in which the objective function includes uncertain coefficients. Copyright Springer Science+Business Media, LLC 2013

Keywords: Robustness analysis; Shortest path problem; Worst case criterion; Integer linear programming (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-011-1004-2 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:207:y:2013:i:1:p:97-120:10.1007/s10479-011-1004-2

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-011-1004-2

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().