Cette thèse s’inscrit dans le domaine de la programmation mathématique appliquée à la séparation d’aéronefs stabilisés en altitude. L’objectif est le développement d’algorithmes de résolution de conflits aériens ; l’enjeu étant d’augmenter la capacité de l’espace aérien afin de diminuer les retards et d’autoriser un plus grand nombre d’aéronefs à suivre leur trajectoire optimale. En outre, du fait de l’imprécision des prédictions relatives à la météo ou à l’état des aéronefs, l’incertitude sur les données est une caractéristique importante du problème. La démarche suivie dans ce mémoire s’attache d’abord au problème déterministe dont l’étude est nettement plus simple. Pour cela, quatre modèles basés sur la programmation non linéaire et sur la programmation linéaire à variables mixtes sont développés en intégrant notamment un critère reflétant la consommation de carburant et la durée de vol. Leur comparaison sur un ensemble de scénarios de test met en évidence l’intérêt d’utiliser un modèle linéaire approché pour l’étude du problème avec incertitudes. Un champ de vent aléatoire, corrélé en temps et en espace, ainsi qu’une erreur gaussienne sur la mesure de la vitesse sont ensuite pris en compte.Dans un premier temps, le problème déterministe est adapté en ajoutant une marge sur la norme de séparation grâce au calcul d’une approximation des probabilités de conflits. Finalement, une formulation stochastique avec recours est développée. Ainsi, les erreurs aléatoires sont explicitement incluses dans le modèle afin de tenir compte de la possibilité d’ordonner des manoeuvres de recours lorsque les erreurs observées engendrent de nouveaux conflits. / This thesis belongs to the field of mathematical programming, applied to the separation of aircraft stabilised on the same altitude. The primary objective is to develop algorithms for the resolution of air conflicts. The expected benefit of such algorithm is to increase the capacity of the airspace in order to reduce the number of late flights and let more aircraft follow their optimal trajectory. Moreover, meteorological forecast and trajectory predictions being inexact,the uncertainty on the data is an important issue. The approach that is followed focuses on the deterministic problem in the first place because it is much simpler. To do this, four nonlinear and mixed integer linear programming models, including a criterion based on fuel consumption and flight duration, are developed. Their comparison on a benchmark of scenarios shows the relevance of using an approximate linear model for the study of the problem with uncertainties.A random wind field, correlated in space and time, as well as speed measures with Gaussianerrors are then taken into account. As a first step, the deterministic problem is adapted by computinga margin from an approximate calculation of conflict probabilities and by adding it tothe reference separation distance. Finally, a stochastic formulation with recourse is developed.In this model, the random errors are explicitly included in order to consider the possibility of ordering recourse actions if the observed errors cause new conflicts.

La gestion des flux de trafic aérien (ATFM) cherche à structurer le trafic de manière à réduire la congestion dans l'espace aérien. La congestion étant causée par les avions volant dans les mêmes portions de l'espace aérien en même temps, l'ATFM organise le trafic dans les dimensions spatiales (ex. le réseau de routes) et dans la dimension temporelle (ex. séquencement et fusion de flux d'avions atterrissant ou décollant aux aéroports). L'objectif de cette thèse est de développer une méthodologie qui permet au trafic aérien de s'auto-structurer dans les dimensions spatiales et temporelle quand la demande est élevée. Cette structuration disparait quand la demande diminue. Pour remplir cet objectif, un système multi-agents a été développé, dans lequel les avions coopèrent pour structurer le trafic. Les systèmes multi-agents possèdent plusieurs avantages, incluant une bonne résilience aux perturbations, la résilience étant la capacité du système à modifier ses décisions de manière à retrouver un état stable après l'occurrence d'une perturbation dans son environnement. Dans ce système, trois algorithmes sont implémentés, visant à réduire la com- plexité du trafic de trois manières différentes. Le premier algorithme permet aux agents avions volant sur un réseau de route de réguler leur vitesse de manière à ré- duire le nombre de conflits, un conflit se produisant quand deux avions ne respectent pas les normes de séparation. Le deuxième algorithme permet aux avions de résoudre les conflits quand le trafic n'est pas structuré par un réseau de routes. Le troisième algorithme crée des réseaux de routes locaux temporaires pour structurer le trafic. Les trois algorithmes implémentés dans ce système multi-agents permet de réduire la complexité globale du trafic, qui devient plus simple à gérer pour les contrôleurs aériens. Ces algorithmes sont appliqués à des exemples réalistes et sont capables de structurer le trafic de manière résiliente. / Air Traffic Flow Management (ATFM) aims at structuring traffic in order to reduce congestion in airspace. Congestion being linked to aircraft located at the same position at the same time, ATFM organizes traffic in the spatial dimension (e.g. route network) and in the time dimension (e.g. sequencing and merging of aircraft flows taking off or landing at airports). The objective of this thesis is to develop a methodology that allows the traffic to self-organize in the time and space dimensions when demand is high. This structure disappears when the demand diminishes. In order to reach this goal, a multi-agent system has been developed, in which aircraft cooperate to structure traffic. Multi-agent systems have several advantages, including a good resilience when confronted with disruptive events, resilience being the ability of the system to adapt its decisions in order to get back to a stable state when confronted to a disruption in its environment. In this system, three algorithms have been implemented, aiming at reducing traffic complexity in three different ways. The first algorithm allows aircraft agents flying on a route network to regulate speed in order to reduce the number of conflicts, a conflict occurring when two aircraft do not respect separation norms. The second algorithm allows aircraft to solve conflicts when the traffic is not structured by a route network. The third algorithm creates temporary local route networks allowing to structure traffic. The three algorithms implemented in this multi-agent system allow to decrease overall traffic complexity, which becomes easier to manage by air traffic controllers. This algorithm was applied on realistic examples and was able to structure traffic in a resilient way.

L’optimisation globale fiable est dédiée à la recherche d’un minimum global en présence d’erreurs d’arrondis. Les seules approches fournissant une preuve numérique d’optimalité sont des méthodes d’intervalles qui partitionnent l’espace de recherche et éliminent les sous-espaces qui ne peuvent contenir de solution optimale. Ces méthodes exhaustives, appelées branch and bound par intervalles, sont étudiées depuis les années 60 et ont récemment intégré des techniques de réfutation et de contraction, issues des communautés d’analyse par intervalles et de programmation par contraintes. Il est d’une importance cruciale de calculer i) un encadrement précis de la fonction objectif et des contraintes sur un sous-domaine ; ii) une bonne approximation (un majorant) du minimum global. Les solveurs de pointe sont généralement des méthodes intégratives : ils invoquent sur chaque sous-domaine des algorithmes d’optimisation locale afin d’obtenir une bonne approximation du minimum global. Dans ce document, nous nous intéressons à un cadre coopératif combinant des méthodes d’intervalles et des algorithmes évolutionnaires. Ces derniers sont des algorithmes stochastiques faisant évoluer une population de solutions candidates (individus) dans l’espace de recherche de manière itérative, dans l’espoir de converger vers des solutions satisfaisantes. Les algorithmes évolutionnaires, dotés de mécanismes permettant de s’échapper des minima locaux, sont particulièrement adaptés à la résolution de problèmes difficiles pour lesquels les méthodes traditionnelles peinent à converger. Au sein de notre solveur coopératif Charibde, l’algorithme évolutionnaire et l’algorithme sur intervalles exécutés en parallèle échangent bornes, solutions et espace de recherche par passage de messages. Une stratégie couplant une heuristique d’exploration géométrique et un opérateur de réduction de domaine empêche la convergence prématurée de la population vers des minima locaux et évite à l’algorithme évolutionnaire d’explorer des sous-espaces sous-optimaux ou non réalisables. Une comparaison de Charibde avec des solveurs de pointe (GlobSol, IBBA, Ibex) sur une base de problèmes difficiles montre un gain de temps d’un ordre de grandeur. De nouveaux résultats optimaux sont fournis pour cinq problèmes multimodaux pour lesquels peu de solutions, même approchées, sont connues dans la littérature. Nous proposons une application aéronautique dans laquelle la résolution de conflits est modélisée par un problème d’optimisation sous contraintes universellement quantifiées, et résolue par des techniques d’intervalles spécifiques. Enfin, nous certifions l’optimalité de la meilleure solution connue pour le cluster de Lennard-Jones à cinq atomes, un problème ouvert en dynamique moléculaire. / Reliable global optimization is dedicated to finding a global minimum in the presence of rounding errors. The only approaches for achieving a numerical proof of optimality in global optimization are interval-based methods that interleave branching of the search-space and pruning of the subdomains that cannot contain an optimal solution. The exhaustive interval branch and bound methods have been widely studied since the 1960s and have benefitted from the development of refutation methods and filtering algorithms, stemming from the interval analysis and interval constraint programming communities. It is of the utmost importance: i) to compute sharp enclosures of the objective function and the constraints on a given subdomain; ii) to find a good approximation (an upper bound) of the global minimum. State-of-the-art solvers are generally integrative methods, that is they embed local optimization algorithms to compute a good upper bound of the global minimum over each subspace. In this document, we propose a cooperative framework in which interval methods cooperate with evolutionary algorithms. The latter are stochastic algorithms in which a population of individuals (candidate solutions) iteratively evolves in the search-space to reach satisfactory solutions. Evolutionary algorithms, endowed with operators that help individuals escape from local minima, are particularly suited for difficult problems on which traditional methods struggle to converge. Within our cooperative solver Charibde, the evolutionary algorithm and the intervalbased algorithm run in parallel and exchange bounds, solutions and search-space via message passing. A strategy combining a geometric exploration heuristic and a domain reduction operator prevents premature convergence toward local minima and prevents the evolutionary algorithm from exploring suboptimal or unfeasible subspaces. A comparison of Charibde with state-of-the-art solvers based on interval analysis (GlobSol, IBBA, Ibex) on a benchmark of difficult problems shows that Charibde converges faster by an order of magnitude. New optimality results are provided for five multimodal problems, for which few solutions were available in the literature. We present an aeronautical application in which conflict solving between aircraft is modeled by an universally quantified constrained optimization problem, and solved by specific interval contractors. Finally, we certify the optimality of the putative solution to the Lennard-Jones cluster problem for five atoms, an open problem in molecular dynamics.

À travers une approche de contrôle optimal, cette thèse de doctorat propose une étude des modèles et des techniques de résolution dans un domaine d'application propre à la gestion du trafic aérien. Motivés par la croissance des flux aériens d'une part, et les développements en théorie du contrôle optimal d'autre part, ces travaux portent sur l'analyse du problème d'évitement de conflits aériens. Cette étude permet le développement de nouvelles approches et algorithmes en vue d'aider les contrôleurs aériens dans leur tâche. Ainsi, dans le cadre du trafic aérien, afin de préserver des distances minimales de sécurité entre avions, lors de phases tactiques et de configurations des vols en-route, notre recherche se focalise sur une stratégie de régulation subliminale en vitesse (variations très réduites), pour assurer la séparation entre avions, tout en conservant leur trajectoire prédéfinie. D'une part, une méthode de résolution numérique en contrôle optimal telle que la méthode directe de tir, impliquant une discrétisation totale ou partielle du problème, transforme le problème initial en un problème en programmation non linéaire de grande taille. Ce type de méthodes peut générer des problèmes d'optimisation de grande taille numériquement di_ciles à résoudre. Suivant le nombre de variables du problème, elles peuvent s'avérer trop coûteuse en termes de temps de calculs. D'autre part, les contraintes sur les variables d'états du problème posent des di_cultés de résolution, par exemple, pour l'usage d'une méthode numérique indirecte de tir. Développant les informations caractéristiques des conflits aériens, une détection et une détermination a priori des zones de conflits permettent alors la décomposition du problème présenté de contrôle optimal en sous-problèmes plus aisés à résoudre. La résolution des sous-problèmes hors-zones peut être abordée en utilisant les conditions du principe du maximum de Pontryagin, ce qui en permet une résolution e_cace. Une combinaison de méthodes numériques directes de tir et d'application des conditions du principe du maximum de Pontryagin est proposée, et des implémentations numériques valident ce type d'approche. / The purpose of this doctoral thesis is to study models and solution techniques based on optimal control approaches to address air tra_c management problems. Motivated by the growth of air tra_c volume, and by the advances in optimal control theory, this research works focus on analysing aircraft conflict avoidance problem. This study allows development of new approaches and algorithms to help air tra_c controllers. In the framework of air tra_c management, to ensure the minimum safety distances between aircraft, in tactical phases and en-route flight configurations, this thesis focusses on a subliminal velocity regulation strategy to perform the separation, while preserving the aircraft predefined trajectories. A numerical optimal control solution approach as the direct shooting method, wherein involves a total or partial discretization of the problem, transforms the initial problem into a large scale nonlinear programming problem. This kind of methods could generate large-size optimization problems which are numerically di_cult to solve. Depending on the number of variables which involved, this approaches could be too expensive in terms of computation time. Moreover, the state-variables constraints of the problem lead to numerical di_culties, e.g., considering the indirect numerical shooting method. Tailored on aircraft conflict avoidance problems, a detection and a determination of a priori conflict zones allow the decomposition of the optimal control problem into sub-problems, easier to solve than the original one. Solving the o_-zones sub-problems can be addressed using the Pontryagin maximum principle, which allows in this case directly the solution. A combination of direct numerical shooting method and application of conditions of Pontryagin's maximum principle is proposed, and numerical experiments validate this approach.