Régulation court terme du trafic aérien et optimisation combinatoire Application de la méthode de génération de colonnes

In this work, we address a combinatorial problem arising in the context of dynamic air traffic regulation. In this problem, four-dimensional trajectories have to be built and assigned to every aircraft in order to suppress any sector overload, while minimizing the cost of the chosen policy. This problem is modelled with a mixed linear program, which is solved through column generation and branch-and-price. Its pricing sub-problem looks for feasible trajectories in a dynamic three dimensional network; to solve it, we developed a specific algorithm based on labelling shortest path algorithms and dynamic programming. Each algorithm is tested on real-world data relative to the European air system under the responsibility of the CFMU (Central Flow Management Unit). Results and computing times validate the whole solving processCe travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins quadridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode développée