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

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.