Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGabrel, Virginie*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMurat, Cécile*
hal.structure.identifier
dc.contributor.authorWu, Lei*
dc.date.accessioned2011-11-02T16:03:34Z
dc.date.available2011-11-02T16:03:34Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/7373
dc.language.isoenen
dc.subjectRobustness analysisen
dc.subjectShortest path problemen
dc.subjectWorst case criterionen
dc.subjectInteger linear programmingen
dc.subject.ddc003en
dc.titleNew models for the robust shortest path problem: complexity, resolution and generalizationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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.en
dc.relation.isversionofjnlnameAnnals of Operations Research
dc.relation.isversionofjnlvol207
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages97-120
dc.relation.isversionofdoi10.1007/s10479-011-1004-2en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01495342*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record