Combiner intelligence artificielle et programmation mathématique pour la planification des horaires des équipages en transport aérien

La recherche opérationnelle est un élément central de l'amélioration des horaires d'équipage. L'objectif est d'appliquer des algorithmes de programmation mathématique pour trouver des solutions optimales. Toutefois, cette approche présente un inconvénient important : les temps d'exécution sont longs et nécessitent souvent plusieurs jours pour converger. Cela réduit la valeur pratique d'une solution optimale puisqu'il n'est pas possible d'effectuer une nouvelle exécution avec de nouveaux réglages de paramètres. Étant donné que les horaires des transporteurs aériens sont fréquemment perturbés par des événements météorologiques pendant toute l'année, il est souhaitable de chercher de nouveaux moyens de réduire les durées d'exécution. Dans le cadre de cette thèse, on s'intéresse au problème de rotations d'équipage aériens ou CPP (Crew Pairing Problem), une des étapes de la planification des horaires d'équipage. Pour chaque catégorie d'équipage et chaque type de flotte d'aéronefs, le CPP consiste à trouver un ensemble de rotations à coût minimal afin que chaque vol actif soit effectué par un équipage, en respectant certaines conditions supplémentaires qui varient selon les applications et qui découlent généralement des accords de travail de chaque compagnie. Ce problème devient difficile à résoudre lorsque le nombre de vols augmente car le nombre de rotations possibles augmente de façon exponentielle (nombre de variables). La méthode la plus répandue depuis les années 1990 a été de résoudre le problème de partitionnement d'ensemble avec génération de colonnes insérée dans un algorithme de séparation et évaluation ou B&B (branch-&-bound). Lorsque le nombre de vols augmente dans un problème de rotations d'équipage, le temps pour le résoudre par génération de colonnes devient important. Le nombre d'itérations de génération de colonnes, le temps par itération pour résoudre le problème maître et le nombre de noeuds de branchement augmentent. La méthode d'agrégation dynamique des contraintes (DCA) accélère le problème maître en réduisant le nombre de contraintes de partitionnement définies dans le problème maître restreint en agrégeant en une seule contrainte chaque groupe de tâches qui devraient être consécutives dans la solution optimale. Ceci correspond à fixer temporairement à 1 des variables de connexion de vol. Ceci permet de remplacer toutes les contraintes de couverture des vols d'une grappe par une contrainte unique. L'algorithme modifie dynamiquement ces grappes pour atteindre la solution optimale si certaines prédictions étaient fausses. L'objectif de cette thèse est donc d'utiliser différentes méthodes d'apprentissage machine pour proposer des grappes de vols ayant une forte probabilité d'être effectués consécutivement par le même équipage, dans une solution optimale. Cette information alimente l'optimiseur de program mation mathématique pour terminer le travail en tenant compte de la fonction de coût exacte et des contraintes complexes. Dans le premier sujet de cette thèse, nous présentons une étude de cas sur l'utilisation d'algorithmes d'apprentissage machine pour initialiser solveur commercial à base de génération de colonnes à grande échelle (GENCOL) dans le contexte d'un problème hebdomadaire de rotations d'équipage aérien, où de petites économies de 1.0 % se traduisent par une augmentation des revenus annuels de dizaines de millions de dollars dans une grande compagnie aérienne. Nous nous concentrons sur le problème de la prédiction du prochain vol de correspondance d'un équipage, défini comme un problème de classification multiclasse formé à partir de données historiques, et nous concevons une approche de réseaux de neurones adaptée qui atteint une grande précision (99.7% au total ou 82.5% sur les cas plus difficiles). Nous démontrons l'utilité de notre approche en utilisant une heuristique simple pour combiner les prédictions de connexion de vols afin de former des grappes initiales de vols qui sont fournis comme information initiale au solveur GENCOL, ce qui donne une amélioration de vitesse 10x et jusqu'à 0.2% d'économie. Dans le second sujet de cette thèse, nous proposons de combiner de multiples méthodes d'optimisation mises en oeuvre, développées et testées sur de petits ensembles de données, afin d'obtenir un nouveau solveur efficace pour le problème de rotations d'équipes à grande échelle. Nous utilisons l'apprentissage machine pour proposer des grappes initiales pour un problème de rotations d'équipage important : des problèmes mensuels comportant jusqu'à 50 000 vols. Nous utilisons l'apprentissage machine, pour produire des grappes de vols ayant une forte probabilité d'être effectués consécutivement par le même équipage, dans une solution optimale. Un nouvel algorithme combinant plusieurs techniques avancées de recherche opérationnelle sera utilisé pour assembler et modifier ces grappes, au besoin, afin de produire une bonne solution. Cette nouvelle approche, en commençant par l'apprentissage machine et en terminant l'optimisation par la programmation mathématique, permettra de résoudre des problèmes globalement plus importants et d'éviter la perte d'optimalité résultant de la décomposition heuristique en petites périodes de temps dans l'approche à horizon fuyant. Nous montrons que les grappes produites par l'heuristique à base d'apprentissage machine sont mieux adaptées aux problèmes de rotations d'équipage, ce qui se traduit par une réduction moyenne du coût de la solution entre 6.8 et 8.52 %, qui est principalement dû à la réduction du coût des contraintes globales entre 69.79 et 78.11 %, par rapport aux rotations obtenus avec une solution initiale standard. Dans l'algorithme de génération de colonnes, une solution initiale réalisable est requise pour assurer la faisabilité du problème primal à chaque itération de génération de colonnes. De plus, il est évident, d'après les résultats expérimentaux dans la littérature, que si la qualité de la solution initiale est meilleure, la convergence de génération de colonnes est également plus rapide. Ainsi, une solution initiale de haute qualité devrait être générée dans un laps de temps plus court. Pour pouvoir proposer une telle solution initiale, on a besoin d'un algorithme d'apprentissage machine capable d'incorporer les contraintes locales dans le processus d'entraînement. Dans le troisième sujet de cette thèse, nous présentons donc les réseaux à noyaux convolutifs structurés (SCKN) qui combinent les propriétés des architectures d'apprentissage profond, la flexibilité non paramétrique des méthodes du noyau et les prédicteurs structurés. Plus précisément, nous montrons que l'utilisation supervisée de cette combinaison surpasse les méthodes de pointe en termes de sous-optimalité primale et de précision du test sur l'ensemble de données OCR. Nous appliquons cette méthode à un ensemble de données de prévision de connexions de vols pour proposer de bonnes solutions initiales à un solveur de planification des horaires d'équipage aérien. Les principaux résultats des calculs montrent que l'utilisation de l'approche proposée aboutit à de meilleures solutions avec des coûts significativement plus faibles, réduisant de 9.51 % le coût de la solution et de 80.25 % le coût des contraintes globales. De plus, l'utilisation de la solution obtenue pour relancer le processus d'optimisation donne de meilleurs résultats, réduisant encore le coût de la solution et fournissant une solution avec un coût très négligeable des contraintes globales et un nombre beaucoup plus réduit de repositionnements.

Abstract

A focal point for improving crew scheduling is the study of operations research methods, in order to find optimal solutions. However, this approach has a major drawback. While optimal solutions are possible to achieve, the run times are lengthy, often requiring days for convergence. This reduces the practical value of an optimal solution because there is limited ability to complete a re-run with new parameter settings. Given that air carrier schedules experience frequent year-round disruption from weather events, it is desirable to look for new ways to reduce run times thus making schedule re-generation quicker and more interactive. For each crew category and aircraft fleet type, the crew pairing problem (CPP) consists of finding a set of minimum-cost rotations so that each active flight is performed by a crew, under certain additional conditions that vary according to the applications and that generally result from the work agreements of each airline. This problem becomes difficult to solve when the number of flights increases because the number of possible rotations increases exponentially (number of variables). The most prevalent method since the 1990s has been the set partitioning problem with column generation inserted in branch-&-bound. When the number of flights increases in a CPP, the time to solve it by column generation becomes important. Specifically, the number of iterations and the time per iteration to solve the master problem and the number of branching nodes increase. The dynamic constraint aggregation (DCA) method accelerates the master problem by reducing the number of partitioning constraints defined in the restricted master problem by aggregating into a single constraint each group of tasks that should be consecutive in the optimal solution. This corresponds to temporarily fixing to one the flight-connection variables. This allows all flightcovering constraints for flights in a cluster to be replaced by a single constraint. The algorithm modifies the clusters dynamically to reach an optimal solution if some predictions were wrong. The objective of this thesis is therefore to use various machine learning methods to propose clusters of flights with a high probability of being performed consecutively by the same crew, in an optimal solution. This information feeds into the mathematical programming optimizer to complete the work taking into account the exact cost function and complex CPP constraints. In the first subject of this thesis, we present a case study of using machine learning classification algorithms to initialize a large-scale commercial operations research solver (GENCOL) in the context of a weekly airline CPP, where small savings of as little as 1% translate to increasing annual revenue by dozens of millions of dollars in a large airline. We focus on the problem of predicting the next connecting flight of a crew, framed as a multiclass classification problem trained from historical data, and design an adapted neural network approach that achieves high accuracy (99.7%) overall or 82.5% on harder instances). We demonstrate the utility of our approach by using simple heuristics to combine the flight-connection predictions to form initial crew-pairing clusters that are provided as initial information to the GENCOL solver, yielding a 10x speed improvement and up to 0.2% cost saving. In the second subject of this thesis, we propose to combine multiple optimization methods implemented, developed and tested on small datasets, in order to obtain an efficient new solver for large-scale CPPs. We use Machine Learning (ML) to propose a good initial partition for a large CPP: monthly problems with up to 50 000 flights. We use ML to produce clusters of flights having a high probability of being performed consecutively by the same crew, in an optimal solution. A new algorithm combining several advanced Operations Research techniques will be used to assemble and modify these clusters, when necessary, to produce a good solution. This new approach, starting with Machine Learning and finishing the optimization with Mathematical Programming will permit to solve globally larger problems and will avoid the loss of optimality resulting of heuristic decomposition in small time slices in the rolling horizon approach. We show that the clusters produced by ML-based heuristics are better suited for CPPs, resulting in an average reduction of solution cost between 6.8% and 8.52%, which is mainly due to the reduction in the cost of global constraints between 69.79% and 78.11%, when compared to pairings obtained with a standard initial solution. In the column generation algorithm, an initial feasible solution is required to ensure the feasibility of the primal problem at each iteration of column generation. Moreover, it is clear from the computational experiments in the literature that if the quality of the initial solution is better, the convergence of column generation is also faster. Thus, a high quality initial solution should be generated in a shorter period of time. To be able to propose such an initial solution, we need a Machine Learning algorithm that is able to integrate local constraints into the training process. In the third subject of this thesis, we therefore introduce a Structured Convolutional Kernel Network, or SCKN, which combines the properties of deep learning architectures, the non-parametric flexibility of kernel methods and the structured predictors. More precisely, we show that using this combination in a supervised fashion outperforms state of the art methods in terms of the primal sub-optimality as well as on the test accuracy on the OCR dataset. We apply this method on a Next-Flight-Prediction dataset to propose good initial solutions to an airline crew scheduling solver. The main computational results show that using our proposed approach yields better results with significantly smaller costs, reducing by 9.51% the solution cost and by 80.25% the cost of global constraints. Furthermore, using the obtained solution to re-launch the optimization process yields better results, further reducing the solution cost and providing a solution with a very negligible cost of global constraints and a much smaller number of deadheads.