Groupe d’études et de recherche en analyse des décisions

G-2005-04

Notes sur l'agrégation des contraintes de ressources en chaque noeud dans un problème de plus court chemin

Le problème de plus court chemin avec contraintes de ressources consiste à trouver un chemin d'un point origine à un point destination de coût minimum en respectant les contraintes sur les consommations de ressources. La complexité d'un algorithme de type programmation dynamique augmente avec le nombre de ressources. Une première heuristique couramment utilisée pour produire rapidement des solutions réalisables consiste à dominer uniquement sur un sous-ensemble de ressources. Nagih et Soumis (2005) se proposent l'amélioration de cet heuristique par agrégation des ressources en projetant, en chaque noeud, les ressources sur un vecteur de dimension inférieure en utilisant un algorithme de relaxation lagrangienne pour déterminer les coefficients de la projection.

Ce papier critique la méthode décrite par Nagih et Soumis en prouvant que la méthode de sélection des multiplicateurs de la projection par noeuds ne fournit pas des résultats aussi bons que l'heuristique qu'elle se propose d'améliorer et qu'elle est sensible à des paramètres aléatoires. De plus nous expliquons pourquoi les résultats obtenus sont très instables.

, 13 pages