Optimisation intégrée des rotations et des blocs mensuels personnalisés des pilotes et des copilotes simultanément

Le problème de construction des blocs mensuels pour les membres d'équipage consiste à déterminer des horaires mensuels pour les membres d'équipage des compagnies aériennes tels que tous les vols planifiés sur un horizon de planification donné (généralement un mois) sont couverts tout en satisfaisant un certain nombre de contraintes. En raison de sa taille et de sa complexité, ce problème est généralement résolu séquentiellement en deux étapes: la construction des rotations suivie par la construction des blocs mensuels. Une rotation est une séquence de vols, de connexions et de pauses effectuée par un équipage partant et revenant à la même base. Le problème de construction des rotations consiste à déterminer un ensemble de rotations réalisables à un coût minimal, de telle sorte que chaque vol soit couvert exactement une seule fois. Dans le problème d'affectation des membres d'équipage, l'objectif est de construire des horaires mensuels à partir de ces rotations pour un ensemble donné de pilotes et de copilotes. La construction des rotations et des blocs mensuels doit respecter les règles de la sécurité aérienne, les règles d'opération de la compagnie et les règles contenues dans les conventions collectives entre les employés et la compagnie aérienne. Cependant, il peut s'avérer impossible que l'approche séquentielle obtienne une solution globale optimale car le domaine de décision du problème d'affectation des membres d'équipage est réduit par les décisions précédemment prises dans le problème de construction des rotations des membres d'équipage. L'objectif principal de cette thèse est de proposer des modèles intégrés et de nouvelles approches qui permettent de résoudre le problème de planification des membres d'équipage pour un ensemble donné de pilotes et de copilotes simultanément. Tous les tests réalisés dans cette thèse se basent sur des instances réelles fournies par une compagnie aérienne américaine. À part l'introduction, la revue de littérature et la conclusion, cette thèse comprend trois chapitres principaux dont chacun présente les travaux réalisés pour un objectif de recherche bien précis. Dans le premier objectif, nous proposons en premier temps une extension du problème de construction des rotations des membres d'équipage qui intègre les demandes de vacances du pilote et du copilote au stade du couplage des équipages. Deuxièmement, nous présentons un modèle qui intègre complètement les problèmes de construction des rotations et le problème d'affectation des équipes simultanément pour les pilotes et les copilotes. Pour résoudre ce modèle intégré, nous développons une méthode qui combine la décomposition de Benders et la génération de colonnes. Dans un cas plus général concernant le problème de planification des équipages de ligne aérienne, chaque pilote/copilote a la possibilité de choisir chaque mois un ensemble de vols préférés parmi les vols réguliers. Le deuxième objectif de la thèse consiste à étudier la difficulté d'utiliser la méthode proposée dans le premier objectif lorsque nous considérons un ensemble de vols préférés et de demandes de vacances pour chaque pilote et copilote. Quant au troisième objectif de la thèse, nous considérons le problème de planification d'équipage (pilotes et copilotes) dans un contexte personnalisé où chaque pilote/copilote demande un ensemble de préférences pour des vols spécifiques et des vacances par mois. En effet, nous proposons un modèle intégré qui permet de générer des blocs mensuels personnalisés pour les pilotes et les copilotes simultanément en une seule étape où nous gardons les rotations dans les deux problèmes aussi similaires que possible afin de réduire la propagation des perturbations pendant l'opération. Pour résoudre ce modèle intégré, nous développons une méthode qui combine la relaxation lagrangienne, la génération de colonnes et l'agrégation dynamique des contraintes. Le processus de résolution itère entre le modèle intégré des pilotes et le modèle intégré des copilotes en estimant les effets des décisions du premier problème sur le second problème.

Abstract

The airline crew scheduling problem consists of determining crew schedules for airline crew members such that all the scheduled flights over a planning horizon (usually a month) are covered and the constraints are satisfied. Due to its complexity, this problem is usually solved in two phases: the crew pairing followed by the crew assignment. A pairing is a sequence of flights, connections, and rests starting and ending at the same crew base. The crew pairing problem consists of determining a minimum-cost set of feasible pairings such that each flight is covered exactly once. In the crew assignment problem, the goal is to construct monthly schedules from these pairings for airline crew members, while respecting all the safety and collective agreement rules. However, finding an optimal global solution via sequential approach may become impossible because the decision domain of the crew assignment problem is reduced by previously made decisions in the crew pairing problem. The main goal of this dissertation is to propose integrated models and approaches to solving the crew scheduling problem for a given set of pilots and copilots simultaneously. We conduct computational experiments on a set of real instances from a major US carrier. In the first essay of this dissertation, first, we propose an extension of the crew pairing problem that incorporates pilot and copilot vacation requests at the crew pairing stage. Second, we introduce a model that completely integrates the crew pairing and crew assignment problems simultaneously for pilots and copilots. To solve this integrated model, we develop a method that combines Benders decomposition and column generation. In a more general case in the airline crew scheduling problem, each pilot and copilot have the option of choosing a set of preferred flights from the scheduled flights per month. In chapter 5, we study the difficulty of using the proposed method in the first essay when we consider a set of preferred flights and vacation requests for each pilot and copilot. In the third essay of this dissertation, we consider the pilot and copilot crew scheduling problems in a personalized context where each pilot and copilot requests a set of preferences flights and vacations per month. We propose a model that completely integrates the crew pairing and personalized assignment problems to generate personalized monthly schedules for a given set of pilots and copilots simultaneously. The proposed model keeps the pairings in the two problems as similar as possible so the propagation of the perturbations during the operation is reduced. To solve this integrated model, we develop an integrated approach that combines alternating Lagrangian decomposition, column generation, and dynamic constraint aggregation.