Imitation du branchement fort pour les problèmes de rotations d'équipage

Airlines have to solve crew pairing problems every months. These problems aim to find a good anonymous schedule so that every flights are assigned to pilots and copilots. Crew scheduling needs to verify geographical, temporal and administrative constraints while optimizing millions of variables, which is why only an approximate solution can be found in practice. These problems are approximately solved using a diving Branch-and-Price algorithm. The diving Branch-and-Price algorithm constructs a tree of solutions that is searched using a branching heuristic. The branching heuristic have a great impact on the final solution quality and on the total runtime of the algorithm. The best known heuristic is the strong branching, it raises the best approximate solutions but it is also computationally heavy. A better approach is to use the fractional branching, which is faster and still raises good solutions. In this work, we use machine learning to learn new branching heuristics based on the strong branching decisions. The goal is to have a branching heuristic as fast as the fractional branching while yielding better approximate solutions. We study the possibility of using imitation learning to learn new branching heuristics with the objective of beating fractional branching based solvers. We compare the solutions and runtimes of our heuristics with the fractional and the strong branching heuristics. We also evaluate the impact of distributional shift on the heuristic performances as it could be a limit of the method. We show that imitation learning is a promising method to build new branching heuristics that can outperform the fractional branching solutions while having the same computational complexity.

Résumé

Les compagnies aériennes doivent résoudre des problèmes d'optimisations parmi les plus complexes en industrie. La planification de vol demande de respecter des multitudes de contraintes et met en jeu des ressources à la fois matérielles, humaines et économiques. C'est pourquoi il est crucial pour une compagnie de toujours chercher à améliorer les solveurs (logiciels de résolution de problèmes) chargés d'optimiser ces problèmes. Un de ces problèmes est celui de la planification d'équipage, qui a pour but de déterminer un emploi du temps pour chaque personnel navigant de la compagnie. La résolution de ce problème permet de s'assurer qu'à chaque vol soit affecté un pilote et copilote tout en respectant les contraintes liées aux droits du travail des employés et aux préférences de chacun. Les équipages sont une source de dépense annuelle très importante pour une compagnie aérienne. Pour autant, il n'est actuellement pas possible de trouver une solution optimale à ce problème et c'est pourquoi il y a beaucoup d'investissements pour améliorer les solveurs afin de réduire les coûts des solutions obtenues. Les meilleurs solveurs actuels se basent sur une recherche arborescente de solution : le Branchand- Bound. Un arbre de recherche est construit, afin de parcourir l'espace des solutions du problème. Cependant, dans le cas de la planification d'équipage, le problème est trop gros pour se permettre de parcourir l'ensemble de l'espace des solutions. En pratique, on se contente d'explorer en profondeur une partie de cet espace afin d'obtenir une solution approximative du problème : on nomme cette méthode le diving Branch-and-Bound. Le parcours en profondeur d'un tel arbre est guidé par une heuristique de branchement qui influence fortement la performance globale du solveur. L'heuristique de branchement doit prendre des décisions durant la résolution du problème afin de choisir comment parcourir l'arbre de recherche. La meilleure heuristique connue est le strong branching. Lorsque le solveur l'utilise il obtient en moyenne les solutions aux coûts les plus faibles. Cependant, l'utilisation de cette heuristique coûte cher en temps de calcul. En effet, elle augmente la quantité de sous-problèmes à résoudre durant le parcours de l'arbre ce qui allonge énormément les temps de calcul. C'est pourquoi en pratique ce n'est pas le strong branching qui est utilisé, mais le branchement fractionnaire. Ce dernier, lorsqu'il est utilisé dans un solveur ne permet pas d'obtenir les meilleures solutions approximatives mais il est beaucoup plus économe en temps de calcul (pour certains grands problèmes, il utilise de l'ordre de 4h de calculs contre 16h lorsque le strong branching est utilisé).