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

G-99-02

L'agrégation des contraintes de ressources 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 n ressources sur un vecteur de dimension inférieure, puis d'ajuster dynamiquement la matrice de projection donnant la meilleure approximation de la solution optimale. Le but de ce rapport est de présenter un travail préliminaire pour améliorer la compréhension de ce problème. On se propose de formuler mathématiquement la procédure de sélection des étiquettes efficaces pour mieux comprendre ce que représente la dominance par rapport à un sous-ensemble de ressources, et d'étudier ainsi les propriétés des solutions induites. Afin de contourner les difficultés liées aux approches directes de construction de solutions primales réalisables, nous proposons une alternative basée sur les relaxations lagrangienne et "surrogate" combinée à un algorithme de réoptimisation pour construire des solutions primales réalisables.

, 21 pages