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

G-2000-47(F)

Agrégation des contraintes de ressources en chaque noeud dans un problème de plus court chemin

et

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 et respectant les contraintes sur les consommations de ressources. La complexité d'un algorithme de type programmation dynamique augmente avec le nombre de ressources. Afin d'obtenir rapidement une bonne solution heuristique, nous proposons la réduction de l'espace des états par agrégation des ressources. Il s'agit de projeter les ressources sur un vecteur de dimension inférieure, puis d'ajuster dynamiquement la matrice de projection pour obtenir la meilleure approximation de la solution optimale. Nous proposons une procédure d'ajustement basée sur les relaxations lagrangienne et surrogate dans le cadre de la génération de colonnes où les sous-problèmes sont des plus court chemins avec contraintes de ressources.

, 22 pages