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

Analyse des différents types de plus court chemin

Charles Gauvin HEC Montréal, Canada

Les problèmes de plus courts chemins (PCC) relèvent d’une grande importance dans plusieurs domaines tels le transfert de paquets de données, la gestion de projets et la conception de circuits imprimés. Les PCC sont également fondamentaux pour plusieurs types de problèmes pouvant être modélisés à l’aide de graphes et résolus par génération de colonnes. Les problèmes de plus courts chemins jouent alors le rôle de sous-problème et servent à identifier dynamiquement des colonnes de coût réduit négatif qui sont ensuite introduites dans un problème maître restreint.

Alors qu’il existe des algorithmes très efficaces pour résoudre les PCC dans plusieurs cas, ces problèmes deviennent très complexes dans la quasi-totalité des situations lorsqu’imbriqués dans un algorithme de génération de colonnes. Ce séminaire vise à dresser un portrait des principaux types de problèmes de plus court chemin. La présentation tentera également de bien identifier les propriétés rendant ces problèmes plus ou moins difficiles.