<  Retour au portail Polytechnique Montréal

Solutions initiales du problème de rotations d’équipages avec un modèle de programmation linéaire

Martin Turcotte

Mémoire de maîtrise (2010)

[img]
Affichage préliminaire
Télécharger (13MB)
Citer ce document: Turcotte, M. (2010). Solutions initiales du problème de rotations d’équipages avec un modèle de programmation linéaire (Mémoire de maîtrise, École Polytechnique de Montréal). Tiré de https://publications.polymtl.ca/490/
Afficher le résumé Cacher le résumé

Résumé

Résumé Ce mémoire traite du problème de rotations d’équipages d’une compagnie aérienne. Le problème de rotations d’équipages est important pour les transporteurs aériens, car il doit être résolu lors de la confection des horaires mensuels des membres d’équipages. En effet, la masse salariale constitue le plus gros chapitre des dépenses après celui des coûts du carburant. De surcroît, il s’agit d’un problème majeur qui est également très difficile à résoudre. Le projet porte sur le problème de rotations d’équipages affectant le personnel technique. Pour les exemplaires étudiés, ce problème concerne environ 2000 vols par semaine, réalisés par de court et moyen-courrier. L’objectif principal du projet est de trouver une solution initiale de qualité au problème de rotations d’équipages. L’objectif secondaire du projet est de définir les vols qui ont de fortes chances de se trouver dans une même rotation d’équipage de la solution optimale, et ce, afin de les regrouper. On cherchera donc les meilleures agrégations de l’ensemble des segments de vol à couvrir, ce qui permettra de guider les algorithmes de résolution du problème de rotations d’équipages de notre partenaire industriel afin de trouver plus rapidement des solutions proches de l’optimum. Dans un premier temps, le problème de rotations d’équipages est modélisé à l’aide d’un programme linéaire, lequel a été développé en tenant compte des contraintes imposées par le problème de rotations d’équipages. Le programme linéaire est similaire `a un problème de flot ce qui permettra de tirer avantage de la forte structure de flot du problème de rotations d’équipages. Pour obtenir des temps de calcul raisonnables, le programme linéaire est résolu en nombres réels et la résolution de ce programme est réalisée avec CPLEX. Dans un deuxième temps, la solution optimale du programme linéaire en nombres réels est utilisée pour trouver de bonnes solutions initiales au problème de rotations d’équipages ainsi qu’une agrégation de l’ensemble des segments de vol à couvrir.----------Abstract This masters’ project is about crew scheduling in the airline industry. More specifically, the problem at hand is the crew pairing problem, which is of crucial importance for the airline industry as the payroll expenses are second only to fuel cost. Additionally, the crew pairing problem is a huge and extremely complex problem to solve. The project is about solving weekly crew pairing instances. The instances come from the airline industry and deal more precisely with the technical crews. There are on average 2000 flight segments in the different instances and they are composed of short and medium haul flights. The main objective is to find a good initial solution to the crew pairing problem. The secondary objective is to find legs that are likely to be found in the same rotation in the optimal solution, in order to find an aggregation that is as close as possible to those clusters. Both the initial solution and the aggregation will be used to speed up our industrial partner algorithm used to solve the crew pairing problem. First, the crew pairing problem is modeled as a linear program. This program takes into account the main constraints of the crew pairing problem and is close to a network flow problem in order to take advantage of the strong underlying network structure of the crew pairing problem. In order to have low computation times, the linear program is solved without the integer constraints on the variables and CPLEX is used to solve the linear program. Second, the linear program optimal solution is used to compute an initial solution for the crew pairing problem as well as an aggregation of the flight legs to cover

Document en libre accès dans PolyPublie
Département: Département de mathématiques et de génie industriel
Directeur de mémoire/thèse: François Soumis et ssmail Elhallaoui
Date du dépôt: 21 mars 2011 13:56
Dernière modification: 24 oct. 2018 16:10
Adresse URL de PolyPublie: https://publications.polymtl.ca/490/

Statistiques

Total des téléchargements à partir de PolyPublie

Téléchargements par année

Provenance des téléchargements

Actions réservées au personnel