Apprentissage machine pour l'accélération de l'optimisation des blocs mensuels d'équipages aériens

Les compagnies aériennes sont soumises à une forte pression pour diminuer leurs coûts, c'est pourquoi elles consacrent beaucoup d'efforts dans l'optimisation de la planification aérienne, et notamment dans l'optimisation des horaires d'équipages, car le personnel de bord est leur deuxième poste de dépense après le carburant. Ce mémoire se situe dans le cadre de l'optimisation des blocs mensuels d'équipages aériens, qui consiste à construire les emplois du temps des membres d'équipage sur un mois, en affectant à tous les employés des rotations déjà construites, et ce de manière personnalisée. Une rotation est une séquence de vols commençant et terminant au même aéroport de base. Une méthode connue et efficace pour résoudre ces problèmes est la génération de colonnes, utilisée par l'entreprise AD OPT qui a collaboré sur ce projet. Dans cette méthode, un problème maître restreint optimise les coûts sur un sous-ensemble de blocs mensuels possibles en s'assurant de la couverture de toutes les rotations. D'autre part, des sous-problèmes se chargent de générer des nouveaux blocs mensuels qui vont améliorer la solution du problème maître restreint. La génération de colonnes est un algorithme itératif exact qui considère implicitement tous les blocs possibles sans les énumérer. Dans notre cas, un sous-problème est un problème de plus court chemin dans un réseau contenant toutes les rotations possibles, un chemin représentant un bloc. Il y a un sous-problème par employé. Les données fournies par AD OPT concernent une compagnie aérienne réelle, ayant environ 2000 employés et 5000 rotations par mois. On a donc ici 2000 réseaux de 5000 rotations chacun. En outre, il faut résoudre les problèmes de plus courts chemins dans ces réseaux des centaines de fois. Or, un bloc ne contient jamais plus de 10 rotations. L'objectif de cette maîtrise est alors d'accélérer les temps de calcul en réduisant la taille de ces réseaux d'un facteur 10 avec des techniques d'apprentissage machine. Grâce aux données historiques, la machine peut estimer la probabilité qu'une rotation soit dans le bloc d'un employé dans un mois futur. À partir de ces informations, on pourra extraire, pour chaque employé, les 500 rotations les plus probables et donner seulement celles-ci aux réseaux correspondants. Les réseaux réduits ainsi obtenus seront ensuite étendus progressivement, au fur et à mesure des itérations de la génération de colonnes, pour finalement considérer les réseaux entiers, garantissant ainsi l'optimalité. Le rôle de l'apprentissage machine est donc de fournir des informations pertinentes à un optimiseur exact de blocs mensuels. Les caractéristiques d'apprentissage sont les suivantes : les préférences et qualifications des employés, ainsi que les vols et les qualifications requises des rotations. Quelques améliorations du modèle classique d'apprentissage profond en classification sont présentées : une méthode de pondération de l'entropie croisée qui favorise la minimisation du rappel, ainsi que deux méthodes de sur-échantillonnage qui visent à rééquilibrer l'ensemble de données. L'une répète les échantillons de la classe minoritaire, et l'autre en génère des nouveaux par interpolation. À chaque fois, trois architectures de perceptron multicouche ont été testées, deux optimiseurs ont été envisagés, et plusieurs valeurs d'hyper-paramètres ont été explorées. La mesure de performance utilisée est calculée par rapport à la solution dont nous disposons, alors qu'il en existe de nombreuses autres tout aussi bonnes quoique très différentes. Ainsi, la performance est sous-évaluée par rapport à celle qui considérerait plusieurs de ces solutions équivalentes. Idéalement, la performance serait en fait calculée par rapport à une nouvelle solution, donnée par la génération de colonnes qui intégrerait les résultats de l'apprentissage. Ce n'était pas envisageable pour des raisons pratiques, mais c'est assurément un prolongement possible de ces travaux. Après avoir sélectionné les cas où l'ensemble des rotations apparaissaient au moins une fois dans les réseaux réduits des employés, les expériences effectuées donnent une performance de 37% dans le meilleur cas. Pour des raisons pratiques, l'intégration des résultats d'apprentissage dans la génération de colonnes n'a pas pu être réalisée dans le cadre de cette maîtrise. Ceci fera l'objet d'un projet futur, et on espère obtenir des meilleurs résultats en utilisant une mesure de performance plus adéquate à l'optimisation.

Abstract

Airline companies are under a heavy pressure to lower their costs. Therefore, they put a lot of effort into their airline planning optimization, and especially into the crew scheduling optimization, since the onboard staff is their second biggest expense after fuel. The framework of this project is the aircrew rostering problem, which consists of building the monthly schedules of all the crew members by assigning pairings in a personalized way. A pairing is a sequence of flights, starting and ending at the same airport. A well-known and efficient way to solve this problem is the column generation algorithm, used by the AD OPT company, which collaborated on this project. In this method, a restricted master problem minimizes the total cost on a subset of possible blocks, while ensuring the coverage of all the pairings. On the other hand, sub-problems generate new monthly blocks, which will improve the solution of the restricted master problem. Column generation is an iterative and exact algorithm that implicitly considers all the possible blocks without enumerating them. In this case, a sub-problem is a shortest path problem in a network that contains all the possible pairings (a path represents a block). There is one sub-problem by employee. The data provided by AD OPT relates to a real-world airline company, that has around 2000 employees and 5000 pairings each month. Therefore, there are 2000 networks containing 5000 pairings each. However, a block never has more than 10 pairings. Therefore, the purpose of this thesis is to accelerate the computational time by reducing the network sizes by a factor of 10 with machine learning techniques. Based on historical data, one can estimate the probability of a pairing being in the block of an employee in the future. From this information, one will be able to extract the 500 most likely pairings for each employee, and give only these to the corresponding networks. The resulting reduced networks will be progressively extended when the columns generated with the current reduced networks seem to be insufficient, and in the end, the whole networks will be considered to guarantee optimality. Thus, the role of machine learning is to provide relevant information to an exact optimizer of the crew rostering problem. The learning features are: the employees' wishes and qualifications, together with the pairings' flights and required qualifications. We present a few improvements to the standard deep learning model used in classification: a method that weighs the cross-entropy loss function in a way that favors recall minimization, as well as two sampling methods, that aim to rebalance the dataset. The first one repeats minority samples, and the other one artificially generates new ones by interpolation. In each of these methods, three perceptron architectures are tested, two optimizers are considered and several values of hyper-parameters are explored. The selected performance measure is computed with respect to the solution at disposal, whereas many very different, but just as good solutions exist. Consequently, the performance will always be under-evaluated in comparison to a performance that would consider many of these solutions. In fact, ideally, the performance would be computed with respect to a new solution provided by the column generation algorithm, that integrates the information provided by machine learning. For practical reasons, that wasn't realistic in this case, but it would definitely be part of the future work. Once we selected the cases in which all the pairings appear at least once in the reduced networks, the best performance among the experiences carried out in this project is 37%. For practical reasons, the integration of the learnt results within the column generation algorithm couldn't be completed in this masters' thesis. This will be implemented in the future, and we hope to deliver better results by using a performance measure that is more relevant to the optimization point of view.