Robust Shortest Path Problems

Gabrel, Virginie; Murat, Cécile

Gabrel, Virginie; Murat, Cécile (2010), Robust Shortest Path Problems, in Paschos, Vangelis, Paradigms of Combinatorial Optimization, Wiley-VCH, p. 615-639

Type

Chapitre d'ouvrage

External document link

http://hal.archives-ouvertes.fr/hal-00179975/en/

Date

2010

Book title

Paradigms of Combinatorial Optimization

Book author

Paschos, Vangelis

Publisher

Wiley-VCH

ISBN

978-1-84821-148-3

Number of pages

704

Pages

615-639

Metadata

Show full item record

Author(s)

Gabrel, Virginie
Murat, Cécile

Abstract (FR)

Cet article constitue un état de l’art sur les problèmes de plus courts chemins pour lesquels il existe des éléments d’incertitude et d’indétermination sur les valeurs des arcs. Deux modèles d’incertitude sont distingués : celui dit par intervalle et celui dit par scénarios. Différentes mesures et approches de la robustesse sont présentées : celles issues de la théorie de la décison, celles issues de l’analyse multicritère et celles issues de la programmation mathématique. Elles donnent lieu à plusieurs versions distinctes du problème de plus court chemin robuste dont les complexités et les résolutions sont présentées.

Abstract (EN)

This paper is a state of the art on the shortest path problems for which it exists uncertainty and inaccuracy factors on arc values. Two uncertainty models are distinguished: the so-called interval model and the discrete set of scenarios model. Different measures and approaches of robustness are presented: those coming from decision theory, those coming from multicriteria analysis and those coming from mathematical programming. Each one leads to a particular version of robust shortest path problem for which complexity and resolution are studied.

Subjects / Keywords

Programming by constraints; Dynamical Programming; Linear Programming; ombinatorial Optimization