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.