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.