Robust Shortest Path Problems
Virginie Gabrel, Cécile Murat · HAL (Le Centre pour la Communication Scientifique Directe) · 2007
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 ver-sions distinctes du problème de plus court chemin robuste dont les complexités et les résolutions sont présentées. Mots-clefs: plus court chemin, optimisation robuste, incertitudes sur les données, scénario du pire cas, regret maximum This paper is a state of the art on the shortest path problems for which it ex-ists 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. Key words: shortest path, robust optimization, data uncertainties, worst case sce-nario, maximal regret