En optimisation, les sources d’incertitude et d’imprécision sont nombreuses et rendent souvent difficiles l’affectation d’une unique valeur plausible à chacun des paramètres du modèle. Il peut alors être plus pertinent de retenir un ensemble de valeurs possibles pour chacun des paramètres. Un scénario est défini en choisissant une unique valeur dans chacun des ensembles. Dans ce contexte, une solution robuste doit être aussi bonne que possible dans une grande majorité de scénarios et jamais trop mauvaise. Cette caractérisation donne lieu à de nombreuses interprétations possibles qui justifient différentes approches de la robustesse. Ces approches se distinguent par les différents modèles utilisés pour représenter les facteurs d’incertitude, par les méthodologies utilisées pour mesurer la robustesse, et finalement par la conception et l’analyse des méthodes de résolution. Dans ce papier, nous nous focalisons sur l’application de nouveaux critères pour le plus court chemin avec des valeurs incertaines sur les arcs. Nous commençons par rappeler deux modèles d’incertitude habituellement considérés : le modèle par intervalle et le modèle par ensemble discret de scénarios. Pour chacun d’entre eux, nous appliquons les nouveaux critères de robustesse appelés bw-robustesse et bw-déviation (proposés initialement par B. Roy) qui généralisent respectivement les critères du pire cas et du regret maximum. Dans chacun des cas, nous avons à résoudre des programmes linéaires en nombres entiers de très grandes tailles. Nos expérimentations numériques sur des graphes de grandes tailles montrent qu’un solveur standard de type Cplex est capable de résoudre ces nouveaux problèmes, ce qui est très prometteur du point de vue de l’analyse de robustesse.
Keywords: Robustness analysis; Shortest path problem; Worst case criterion; Integer linear programming.
Virginie Gabrel, Cécile Murat, Lei Wu
1314total visits.