Modèles déterministes et stochastiques pour la résolution de conflits entre aéronefs

Cette thèse s'inscrit dans le domaine de la programmation mathématique appliquée au problème de détection et de résolution de conflits entre aéronefs. Un conflit est une perte de séparation entre deux ou plusieurs aéronefs qui se retrouvent trop proches selon des normes de sécurité prédéfinies. Étant donnée une configuration initiale d'un ensemble d'aéronefs (position, vitesse, accélération), le problème de détection et de résolution de conflits entre aéronefs consiste à trouver une nouvelle configuration sans conflits futurs et minimisant une fonction de coût choisie par l'utilisateur (critère économique, critère sécuritaire, etc.). Dans le système de gestion du trafic aérien actuel, cette tâche est gérée par un contrôleur aérien visualisant le trafic sur un moniteur. Quand le contrôle anticipe un conflit, il transmet des manœuvres d'évitement aux pilotes des aéronefs concernés. Les pilotes appliquent ces manoeuvres avant de rejoindre leur trajectoire prévue par leur plan de vol. Les enjeux de l'optimisation du maintien de séparation entre aéronefs sont multiples. En particulier, le développement de modèles d'aide à la décision pour le contrôle permettrait l'augmentation de la capacité des secteurs aériens. Ainsi, plus d'aéronefs pourraient circuler en même temps, et ce le long de leur trajectoire optimale, tout en diminuant les retards. De plus, au-delà de la complexité du trafic, les imprécisions relatives aux données météorologiques et à l'état des aéronefs, ainsi que les délais de communication, mettent en avant la nécessité de robustesse dans la résolution du problème. Dans cette optique, la communauté de recherche opérationnelle s'est attaquée durant les deux dernières décennies à des variantes du problème de plus en plus complexes permettant de prendre en compte des contraintes opérationnelles difficiles à traiter. Cette thèse s'insère dans cette tendance. Dans un premier temps, cette thèse présente une étude économique destinée à valider le besoin opérationnel d'outils automatisés d'aide à la décision pour le contrôleur aérien. Plus particulièrement, les interactions entre les décisions tactiques faites lors de l'affectation des créneaux de décollage et les décisions opérationnelles faites lors de la résolution de conflits sont étudiées dans un contexte de trafic augmenté. Pour cela, un simulateur de trafic permettant de travailler avec différents paradigmes d'allocations de créneaux de décollage, de capacité de secteurs, d'augmentation de trafic est utilisé. À partir de données de trafic français datant de 2012, une semaine de trafic standard est générée pour différentes années jusqu'à un horizon allant à 2035. L'étude montre alors que les coûts des retards dus à l'allocation de créneaux de décollage augmentent exponentiellement avec l'augmentation du trafic si la capacité du réseau n'est pas augmentée, tandis que l'augmentation des coûts de résolution de conflits augmente de façon beaucoup plus acceptable avec un réseau de plus grande capacité. Cependant, l'augmentation de la capacité du réseau entraîne une charge de travail ingérable pour un contrôleur avec les outils actuellement disponibles. L'étude propose ensuite un compromis entre une forte augmentation des coûts de retards et une forte charge de travail, en contrôlant la hausse des coûts des retards en augmentant les capacités des secteurs. La valeur ajoutée de cette étude est que nous sommes désormais capables de quantifier les objectifs de recherche en optimisation du trafic aérien, tout en donnant une légitimité aux travaux déjà existants. Dans un second temps, cette thèse présente un modèle mathématique de détection et de résolution de conflits dans un cadre déterministe. Le design de la méthode repose sur la volonté d'obtenir un modèle robuste. En d'autres termes, le formalisme mathématique doit demeurer valable, et ce quelles que soient les hypothèses considérées. Pour cela, les aspects relatifs à la modélisation de la dynamique des avions, des manoeuvres ainsi que la fonction de coût sont complètement séparés du modèle mathématique de résolution. Formellement, le problème est modélisé comme une recherche de clique de cardinalité maximale et de poids minimum dans un graphe. Les sommets du graphe correspondent à un ensemble de manoeuvres possibles pour les aéronefs, et les arêtes lient des manoeuvres sans conflit pour des aéronefs différents. Afin de garder un graphe compact, nous modélisons les coûts de façon originale : en effet, ces coûts dépendent des sommets appartenant à la clique et ne sont ainsi plus connus a priori. Ce choix de modélisation en fait une nouvelle variante d'un problème de recherche de clique de cardinalité maximale de poids minimum. Nous formulons ensuite le problème comme un programme linéaire à variables mixtes. Deux méthodes de décomposition sont également développées. La première vise à utiliser l'influence du nombre de manoeuvres par aéronef sur le temps d'exécution afin de trouver un compromis entre efficacité et temps de résolution, alors que la seconde vise à exploiter les caractéristiques géométriques des instances. Des instances ayant jusqu'à 250 avions répartis sur 20 niveaux sont résolues en moins de 10 secondes de calcul. La dernière partie de cette thèse traite la prise en compte d'incertitudes lors de la résolution de conflits. Plus particulièrement, nous considérons les incertitudes dues aux erreurs de prévisions météorologiques sur le vent, ainsi que les erreurs de mesure de la vitesse venant de la connaissance incomplète des paramètres physiques des avions. Nous introduisons également un nouveau type d'incertitude : le délai dû aux communications entre le contrôleur et les pilotes. Ces perturbations induisent une erreur longitudinale sur la trajectoire des avions que nous quantifions, afin d'établir une formule analytique de la probabilité de conflit entre chaque paire d'avions. Nous utilisons ensuite cette formule pour modifier la définition des arêtes du graphe présenté dans la seconde partie de la thèse. Nous abordons ensuite le problème de résolution de conflits sous un angle bi-objectif. Pour ce faire, nous considérons un critère économique correspondant à la consommation de carburant pour exécuter les manoeuvres, ainsi qu'un critère de sécurité décrit par l'espérance du nombre de conflits. Nous présentons ensuite une méthode itérative permettant de générer un ensemble de solutions approximant le front de Pareto du problème. Cette approche est innovante car elle nous permet d'avoir une approche bi-objectif du problème de résolution de conflits, ce qui correspond plus à la nature intrinsèque du problème, et elle permet de fournir au contrôleur un ensemble de solutions. Ce dernier point est le plus pertinent car la notion d'optimalité est discutable en résolution de conflits à cause de l'existence de plusieurs “bonnes solutions” proches de la solution optimale, et il peut être intéressant de laisser au contrôleur des options dans sa prise de décision. En moyenne, 6 solutions sont générées en moins de 3 minutes pour des instances ayant jusqu'à 35 avions.