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.