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

G-2016-47

A new heuristic branching scheme for the crew pairing problem with base constraints

, et

La création d’horaires de personnel aériens est généralement effectuée en deux étapes : la création de rotations d’équipage, suivie par la création d’horaires personnalisés. Le but du problème de rotations d’équipage est de déterminer un ensemble de rotations (séquences de vols séparés par des connections ou repos, débutant et se terminant à une même base), qui couvre un ensemble de vols à coût minimum. Le problème d’horaires personnalisés consiste à assigner ces rotations aux membres d’équipage afin de créer leurs horaires individuels. L’inconvénient principal de cette approche séquentielle est que les rotations générées lors de la première étape sont parfois peu adaptées à la seconde étape. Cela peut résulter en des solutions de faible qualité. Cet article étudie une extension du problème de rotations d’équipage qui inclut des contraintes additionnelles limitant le temps de travail disponible à chaque base. Ce problème, nommé le problème de rotations avec contraintes de bases, a pour but l’amélioration du couplage entre les deux phases. Pour résoudre ce problème, nous développons quatre heuristiques de branch-and-price. Trois de celles-ci sont basées sur des méthodes de branchement heuristiques connues. Une autre méthode, appelée branchement rétrospectif (retrospective branching), est élaborée dans le but de détecter et d’éliminer les mauvaises décisions de branchement prises plus haut dans l’arbre de branchement, et ceci sans avoir à effectuer de retours en arrière. Nous testons et comparons ces quatre heuristiques sur des données provenant de l’industrie. Nos résultats montrent que le branchement rétrospectif permet de trouver, dans la plupart des cas, des solutions de meilleures qualité qu’avec les autres méthodes testées.

, 25 pages