Méthodes algébriques pour le problème de plus court chemin sous-contraintes et application à un problème d’Air France

Session : PJC-2 / Prix Jeune Chercheur
Mercredi 10 février 15:00 - 16:00 Salle : Amphi-CI
Axel Parmentier

De nombreuses méthodes de type A∗ ont récemment été développées pour accélérer la résolution des problèmes de plus court chemin. Le principe commun de méthodes des type A∗ est d’utiliser des bornes pour éliminer des solutions partielles dans une énumération de l’ensemble des chemins, et l’originalité des différentes contributions réside dans le choix des bornes. Si l'utilisation de bornes est devenue standard pour les problèmes de plus court chemin, ce n'est pas encore le cas pour les problèmes de plus court chemin sous contraintes, problèmes dont l'importance en Recherche Opérationnelle vient notamment de leur apparition dans les sous-problèmes des méthodes de génération de colonnes. La contribution de cette présentation est d'introduire un formalisme algébrique pour les problèmes de plus court chemin sous contraintes qui soit à la fois suffisamment flexible pour s'appliquer à un large panel de problèmes de plus court chemin sous-contraintes et suffisamment riche pour permettre le développement d'algorithmes standardisés pour la construction de borne et la résolution du problème.

Mots clés : Plus court chemin sous contraintes, Algorithme de bornes, Opérations aériennes