Conditions d'interaction entre apprentissage machine du prétraitement rapide et le problème des blocs mensuels personnalisés

Le problème de la création de blocs mensuels personnalisés pour pilotes (CRP) s’inscrit dans la famille des problèmes de création d’horaires d’équipage aérien. À partir de rotations, soit des séquences de quelques vols et repos commençant et se terminant à la même base, le problème exige de créer des horaires mensuels complets pour les pilotes disponibles de sorte que chaque rotation soit assignée à exactement un pilote. Ceci doit être fait en tenant compte de différentes contraintes portant pour certaines sur l’ensemble du bloc mensuel, et pour d’autres sur les horaires des pilotes individuels. Chaque pilote émet des préférences tant sur des vols spécifiques que sur des périodes de congé, et l’objectif à maximiser porte alors sur la satisfaction totale apportée aux pilotes par les horaires qui leur sont fournis. La création de blocs mensuels personnalisés étant complexe, de nombreuses méthodes ont été développées afin d’en accélérer la résolution avec le moins d’impact possible sur l’objectif du modèle d’optimisation. Plusieurs de ces méthodes se basent sur la génération de colonnes. Cette technique permet de résoudre un problème restreint à chaque itération de l’algorithme d’optimisation. Le modèle est graduellement agrandi en résolvant un sous-problème par pilote représenté par un graphe et où trouver un horaire réalisable revient à résoudre un problème de plus court chemin avec contraintes de ressources. Cette forme de génération de colonnes a déjà été implantée commercialement à l’intérieur de solveurs performants. De plus, au cours des dernières années et avec l’essor de l’apprentissage machine (ML), de nouveaux types d’algorithmes d’apprentissage et métaheuristiques ont été considérés tant pour suppléer ou assister les solveurs de recherche opérationnelle (RO) traditionnels. Ces innovations ont simultanément connu des succès intéressants et rencontré des limites. Toutefois, peu d’analyses systématiques ont été réalisées pour déterminer clairement dans quels contextes l’interaction ML-RO a du potentiel, et quel type d’algorithme devrait être utilisé le cas échéant. La présente thèse aborde donc tant l’enjeu d’accélérer la résolution du CRP que celui d’évaluer le potentiel des méthodes d’apprentissage pour ce problème. Pour ce faire, nous créons une procédure d’affectation successive qui construit un bloc mensuel un jour à la fois. Chaque problème d’affectation est représenté par un graphe où les coûts des arcs indiquent la valeur d’affecter une rotation à un pilote. Ces coûts sont calculés à l’aide de poids appris par ML au travers d’un algorithme d’évolution. À l’aide de la solution obtenue, cette dernière est utilisée pour mieux anticiper ou améliorer le fonctionnement d’un solveur CRP correspondant à l’état de l’art. L’apprentissage réalisé fait donc partie de la famille des applications dites par apprentissage du prétraitement et qui visent à fournir de l’information utile au solveur avant que l’optimisation ne soit entamée. Un avantage de cette approche est que l’information fournie en entrée peut être la même pour différentes formes de prétraitement visant à améliorer la génération de colonnes. Puisque la qualité de ce qui est fourni en entrée reste inchangée également, il devient possible de mettre en lumière les types d’interaction ML-RO pouvant tirer parti d’une information supplémentaire même limitée. Ainsi, dans un premier temps, nous considérons la planification du CRP. Avant le début de chaque mois, les employés de la compagnie aérienne doivent déterminer combien de pilotes doivent être rendus disponibles, gardés en réserve, ou assignés à des activités spéciales (formations, congés). Nous mesurons ensuite si la qualité des solutions obtenues par affectation successive permet de prédire celle obtenue par le solveur standard. Nous trouvons une relation solide entre la qualité de ces solutions qui dépasse ce que d’autres méthodes rapides obtiennent. Les planificateurs peuvent alors anticiper si la configuration actuelle du problème permet d’obtenir de bonnes solutions dans le solveur et modifier la planification en quelques secondes au besoin. Ensuite, nous implantons une méthode de résolution du CRP par fenêtrage, où chaque partie de la solution fournie en entrée est réoptimisée à tour de rôle en gardant le reste du bloc mensuel fixé. Nous avons comparé l’utilisation du fenêtrage avec et sans solution ML initiale à d’autres heuristiques rapides ou naïves. Bien que dans les deux formes de fenêtrage, une accélération dépassant un facteur 10 ait été observée, les solutions de l’affectation successive obtenues grâce à l’apprentissage ML ont permis d’obtenir un objectif en moyenne à seulement 1% de l’optimalité pour deux grandes instances avec différents niveaux de productivité moyen attendue par pilote. Ces résultats dépassent également ceux obtenus par les autres méthodes testées. Enfin, nous évaluons la capacité des solutions ML à maximiser les bénéfices associés à l’agrégation dynamique de contraintes (DCA). Ce but requiert d’apprendre quelles séquences de rotations sont susceptibles de se retrouver dans le bloc mensuel optimal. Nous considérons différentes méthodes afin de rehausser les solutions fournies à l’algorithme DCA, telles que varier le choix de l’algorithme ML, la création de variables ML supplémentaires et riches en information potentielle, et une affectation successive moins myope. Face à l’absence de résultats générés par ces techniques supplémentaires, nous concluons que prédire le contenu d’une solution optimale est un défi souvent peu réaliste par rapport au fait de générer des solutions contenant de l’information utile plus générale et à raffiner ensuite par un solveur traditionnel. En conclusion, cette thèse permet de traiter en profondeur l’utilisation de méthodes ML pour le problème des blocs mensuels personnalisés. En comparant les succès et les difficultés rencontrés au cours de ce processus, nous avons trouvé de meilleures façons de résoudre le CRP. Nous avons également amorcé une démarche d’analyse structurée des interactions de type ML/RO, dans ce cas-ci pour le CRP avec l’apprentissage du prétraitement, qui a le potentiel de s’étendre à d’autres problèmes.

Abstract

The crew rostering problem for pilots (CRP) is part of the family of airline crew scheduling problems. Starting from pairings, or sequences of a few flights starting and ending at the same base, the problem requires creating monthly rosters for the pilots available to work such that each pairing is assigned to exactly one pilot. This must be done while taking into account various constraints related to the entire roster, and others related to the individual schedules of the pilots. Each pilot states preferences over both specific flights and vacations, and the objective is to maximize the sum of the total satisfaction brought to the pilots by their schedules. The creation of rosters being a complex task, many methods have been developed to speed up its resolution while limiting the impact of this acceleration on the quality of the optimization model’s objective. Many of these methods build upon column generation, which has made large scheduling problems tractable. This technique makes it possible to solve a restricted problem at each iteration of the optimization algorithm. The model for each subsequent restricted problem is gradually expanded by solving one subproblem per pilot. The subproblems are represented by graphs where finding a feasible schedule comes down to solving a shortest path problem with resource constraints. This form of column generation has already been implemented commercially within high-performing CRP solvers. Furthermore, in recent years and with the rise in the use of machine learning (ML), new types of learning algorithms and metaheuristics have been considered to either replace or assist operations research (OR) traditional solvers. These innovations have lead to interesting successes, but came with limitations. However, few systematic analyses have been conducted to determine clearly in which contexts ML-OR interaction has potential, and which types of algorithms should be considered when it does. For this reason, this dissertation considers two main issues. The first involves accelerating the resolution of the CRP, while the other is assessing the potential of ML methods in an ML-OR context. We build a sequential assignment procedure that forms a monthly roster one day at a time. Each assignment problem is represented by a graph where arc costs show the utility of assigning a given pairing to a pilot. These costs are calculated with the help of weights learned by ML through an evolutionary algorithm. With the solution obtained, we anticipate or improve the behavior of a state-of-the-art CRP solver. This type of learning is part of the family of learning to preprocess, where useful information is provided to the solver before the optimization procedure is launched. An advantage of this approach is that the input used for preprocessing can be kept unchanged even when testing different ways of improving column generation (i.e., different forms of preprocessing). Since the input’s quality remains the same as well, we can see which ML-OR interactions can leverage even limited additional information. First, we consider CRP planning. Before the beginning of each month, the airline scheduling workers must determine how many pilots must be made available, stand by on reserve, or be assigned to special activities (e.g., specialized training, vacations). Then, we measure if the quality of the solutions obtained by sequential assignment makes it possible to predict that of rosters found in the standard solver. We find a solid relationship between the quality of these solutions that exceeds what other fast methods provide. The scheduling workers are then able to anticipate whether the current configuration of a CRP instance allows for good solutions in the solver and to modify the planning done so far in a few seconds as needed. Next, we implement a solution method with windowing. In this context, each part of the solution provided as input is reoptimized in turn while keeping the rest of the roster fixed. We have compared windowing with and without an initial ML solution to other fast or naive heuristics. While an acceleration of the CRP’s resolution of an order of more than 10 is observed with both forms of windowing, the sequential assignment solutions obtained with ML have allowed to get an objective on average only 1% away from optimality for two large instances with different levels of average expected productivity per pilot. These results outperform those found by other methods. Our last specific contribution lies in evaluating the ability of ML solutions to maximize the benefits associated with dynamic constraint aggregation (DCA). This goal requires learning which sequences of pairings are part of the optimal roster for the problem with good accuracy. We consider different methods to enhance the solutions given as input to the DCA procedure, such as varying the choice of the ML algorithm, the creation of additional ML features rich in potential information, and a less myopic form of sequential assignment. In the absence of convincing results yielded by these other techniques, we conclude that predicting the content of an optimal solution is an often unrealistic challenge in comparison to creating solutions containing useful, but more general information that is then to be refined by a traditional optimization solver. In conclusion, this dissertation allows us to treat in depth the use of ML methods for the CRP. By comparing the successes and obstacles encountered during this process, we have found ways to solve the CRP more efficiently. We have also started a process of structured analysis of the suitability of ML/OR interaction in general, with in this case a focus on the CRP with learning to preprocess that has the potential to extend to other problems.