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

RÉSUMÉ: 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. ABSTRACT: This thesis is related to the field of mathematical programming applied to the conflict detection and resolution problem between aircraft. A conflict happens when two or more aircraft are too close to each other regarding pre-defined separation distances. Given the initial configuration (position, speed, acceleration) of a set of aircraft, the conflict detection and resolution problem consists in finding a new conflict-free configuration that minimizes a cost function chosen by the user (economical criterion, safety criterion, etc.). In the current air traffic management system, this task is managed by an air traffic controller who monitors traffic on a screen. When he/she anticipates a conflict, he/she communicates avoidance maneuvers to the pilots of the corresponding aircraft. The pilots execute these maneuvers before recovering the trajectory described on their flight plan. The stakes behind the optimization of separation between aircraft are multiple. In particular, the development of automated decision tools for air traffic control would allow the increase in airspace capacity. As a consequence, more aircraft could fly simultaneously while following their optimal trajectory and reducing potential delays. Besides, in addition to traffic complexity, the imprecisions related to weather forecasts, to the aircraft physical parameters and the potential communication delays highlight the need for robustness in the problem resolution. To this end, in the last decades the research community has tackled more complex problems that consider hard-to-solve operational constraints. This thesis follows this trend. First, this thesis presents an economical study aiming at the validation of an operational need for the development of automated decision tools for the air traffic controller. More specifically, we study the interactions between strategic decisions for take-off slot allocation and the tactical decisions of conflict resolution in a context of increasing traffic. To this end, we use a complete traffic simulator allowing us to consider different paradigms of take-off slot allocation, sector capacities and traffic increase. Using historical French traffic data from 2012, a typical week of traffic is generated to represent traffic for different years until 2035. The study highlights on the one hand that the costs of delays due to the take-off slot allocation increase exponentially with the traffic increase if the network capacity is not increased. On the other hand, the costs of conflict resolution increase in an acceptable fashion in a network of larger capacity but the workload becomes unmanageable for an air traffic controller using the currently available tools. The study then proposes a compromise between a huge increase of delay costs and a heavy workload by controlling the growth of delay costs by increasing sector capacity. This is of great value, since we are now capable of quantifying research objectives for air traffic optimization while legitimizing the research already existing. Second, this thesis presents a deterministic mathematical model to solve the conflict detection and resolution problem between aircraft. The design of the presented method was driven by robustness. In other words, the proposed mathematical framework must remain valid, whatever the hypotheses considered. To this end, the aspects related to the modeling of aircraft dynamics, maneuvers and the cost function are fully separated from the mathematical resolution process. Formally, the problem is modeled as a search for a clique of maximal cardinality and minimum weight in a graph. The vertices of the graph correspond to possible aircraft maneuvers and edges connect conflict-free maneuvers of different aircraft. To keep the graph compact, we model the vertex costs in an innovative fashion: indeed, these costs depend on the vertices in the clique, and thus cannot be known a priori. This choice of modeling corresponds to a new variant of the minimum-weight maximum-cardinality clique problem. We formulate this problem as a mixed integer linear program. We also develop two decomposition methods. The first one aims at taking advantage of the effect of the number of maneuvers per aircraft on the solution time to find a trade-off between solution efficiency and time, while the second one exploits the geometrical characteristics of the set of aircraft. Instances with up to 250 aircraft divided between 20 flight levels are solved within 10 seconds. The last part of this thesis takes into account uncertainties in the conflict resolution process. More specifically, we consider uncertainties due to errors in weather forecasts, in the aircraft speed measure resulting from the incomplete knowledge of the physical paremeters of the aircraft. We introduce a new type of uncertainty: the delay in the execution of maneuvers due to communications. Those perturbations induce an along-track error on the aircraft trajectory that we can quantify in order to derive an analytical formula of the probability of conflict between every pair of aircraft. We use this formula to modify the definition of edges in the graph presented in the previous section of the thesis. We then tackle the conflict resolution problem as a bi-objective problem. To this end, we consider an economical criterion corresponding to the fuel consumption induced by the execution of maneuvers, along with a safety criterion represented by the expected number of conflicts. We also present an iterative method generating a set of solutions approximating the Pareto front of the problem. This method is innovative, since it uses a bi-objective approach of conflict resolution, which fits more with the inner nature of the problem, while providing the controller with a set of solutions. This last feature is the most relevant because the notion of optimality in conflict resolution is questionable, since there exist several ”good solutions” close to the optimal one, and it could be interesting to give the controller some options in his/her decision making. On average, 6 solutions are generated within 3 minutes for instances with up to 35 aircraft