Retour aux résultats
Articles (1999), Cahiers du Lamsade (Laboratoire d'Analyse et de Modélisation de Systèmes d'Aide), pp. 1-10

The Greedy Approach for the Crew Pairing Problem: Some Cases of Polynomial Subproblems

Le problème de Crew Pairing dans le transport aérien consiste à construire des rotations d'équipages (pilotes et personnel de cabine) couvrant l'ensemble des vols de la compagnie et minimisant, par exemple, la somme globale des temps de pause entre deux vols. Ce problème d'optimisation sous contraintes peut se modéliser comme un programme linéaire en nombres entiers de très grande taille, et se résoud classiquement par des techniques dites de "génération de colonnes ". Nous formalisons quelques cas pour lesquels le sous-problème associé à l'approche gloutonne est soluble en temps polynomial.

ALFANDARI, L. (1999). The Greedy Approach for the Crew Pairing Problem: Some Cases of Polynomial Subproblems. Cahiers du Lamsade (Laboratoire d'Analyse et de Modélisation de Systèmes d'Aide), pp. 1-10.