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

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é).