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.