Importance des variables et régressions statistiques imitant l'heuristique de branchement fort dans un problème de rotation d'équipages

Afin d'optimiser l'ensemble du processus de planification des plans de vols, les compagnies aériennes ont recours à des solveurs de plus en plus performants. Une des étapes de ce processus est la construction de rotations d'équipages où l'on cherche à trouver les ensembles de vols minimisant les coûts. Ces rotations doivent répondre à un ensemble de règles définies par des conventions entre la compagnie et ses employés afin d'être considérées valides. Les techniques de recherche opérationnelle produisent aujourd'hui des solutions relativement bonnes en prenant en compte l'ensemble de ces contraintes. Le problème est résolu sous forme d'un arbre de Branch-and-Bound, et plus particulièrement un arbre de Branch-and-Price. En effet, à cause du grand nombre de rotations entrant en jeu dans la définition du problème,il n'est pas possible de résoudre ce dernier sous sa forme initiale. La méthode de la génération de colonnes est utilisée à chacun des noeuds de l'arbre de Branch-and-Price pour résoudre le problème sous une forme réduite et ainsi explorer efficacement l'arbre en des temps réduits. Des méthodes dites de diving peuvent aussi être utilisées pour réduire encore plus les temps de résolution: une fois qu'un noeud a été exploré, il n'est plus possible de revenir sur des noeuds précédemment mis de côté plus haut dans l'arbre. L'espace de recherche s'en retrouve ainsi grandement réduit. Le choix de la variable à fixer lors de la résolution de l'arbre de Branch-and-Price peut se faire grâce à plusieurs heuristiques. La plus utilisée par les compagnies aériennes aujourd'hui est celle de la fixation de colonne qui consiste à brancher sur la colonne ou rotation ayant la plus grande valeur fractionnaire. Sa rapidité et ses bons résultats la rendent facilement exploitable dans un environnement industriel. L'heuristique du branchement fort propose quant à elle des résultats bien plus proches de l'optimalité mais souffre d'un temps d'exécution très élevé. Elle considère en effet un certain nombre de rotations candidates qui la mènent à résoudre successivement plusieurs problèmes linéaires avant d'étendre l'arbre. Cette particularité la rend donc inexploitable dans la pratique. Afin de combiner les très bonnes performances du branchement fort et la rapidité de la fixation de colonne dans notre contexte de Branch-and-Price et de diving, l'utilisation d'un modèle d'apprentissage machine se présente comme une solution adéquate.

Abstract

To optimize the whole planning process of their flight plans, airlines employ state-of-theart solvers. One of the steps of this process consists in the building of crew pairings where one aims to find the lists of pairings that minimize operation costs. These pairings must satisfy a set of rules defined by collective agreements and airline regulations between the company and its employees to be judged valid. Nowadays, operational research techniques generate very good solutions while considering these constraints. The problem is solved as a Branch-and-Bound tree, and especially a Branch-and- Price tree. Indeed, because of the large numbers of pairings present in the problem, it is not possible to solve it under its initial form. The column generation method is used at each node of the Branchand- Price tree to solve the problem under a reduced form and thus efficiently explore the tree with a lower computational time. Diving methods can also be used to reduce even more the resolution time: once a node has been explored, it is not possible to come back to previous nodes which have been put aside higher in the tree anymore. The search space is thus greatly reduced. The choice of the variable to fix during the resolution of the Branch-and-Price tree can be done thanks to several heuristics. The most used by airlines today is column fixing where we chose to branch on the column which has the highest fractional value. Its speed and its good results make it easily exploitable in an industrial environment. On the other side, the strong branching heuristic generates optimal or near-optimal results but suffer from a very high computational time. It considers a certain number of candidate pairings which lead it to solve successively several linear problems before expanding the tree. This particularity makes it unexploitable in practice. To combine the very good results of strong branching and the speed of column fixing in a Branch-and-Price and diving context, the use of a machine learning model appears promising. Specifically, imitation learning can take decisions similar to those of an expert, the strong branching. However, such a model does not need to solve each candidate node, reducing drastically the computational time. To produce a result, the model needs information about the candidates. The choice of those features is crucial to have the most precise predictions.