<  Back to the Polytechnique Montréal portal

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

Martin Turcotte

Masters thesis (2010)

[img]
Preview
Download (13MB)
Cite this document: Turcotte, M. (2010). Solutions initiales du problème de rotations d’équipages avec un modèle de programmation linéaire (Masters thesis, École Polytechnique de Montréal). Retrieved from https://publications.polymtl.ca/490/
Show abstract Hide abstract

Abstract

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

Open Access document in PolyPublie
Department: Département de mathématiques et de génie industriel
Academic/Research Directors: François Soumis and ssmail Elhallaoui
Date Deposited: 21 Mar 2011 13:56
Last Modified: 27 Jun 2019 16:49
PolyPublie URL: https://publications.polymtl.ca/490/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only