Cette thèse s'intéresse au problème de conception optimale des routes de départ et d'arrivée dans une zone terminale autour d'un aéroport. Cette conception prend en compte la configuration et l'environnement autour des aéroports, et les différentes contraintes sous-jacentes, notamment l'évitement des obstacles et la séparation des routes. Nous proposons une formulation mathématique conduisant à un problème d'optimisation combinatoire, ainsi que des méthodes de résolution ad hoc efficaces pour le problème. Pour la résolution du problème, nous procédons en deux étapes. Nous considérons d'abord la conception d'une route de longueur minimale évitant les obstacles, en utilisant la méthode de Branch and Bound (B&B). Ensuite, nous nous intéressons à la conception de plusieurs routes en assurant en plus la séparation des routes. Deux approches différentes sont appliquées : une méthode basée sur la méthode B&B pour construire les routes séquentiellement suivant un ordre fixé à l'avance, et une méthode de recuit simulé pour construire les routes simultanément. Les résultats sur un ensemble de problèmes tests (artificiels et réels) montrent l'efficacité de notre approche. / This thesis proposes a methodology for the optimization of departure and arrival routes in the Terminal Maneuvering Area (TMA). The design of these routes takes into account the configuration and environment around airports, and the related constraints, in particular the avoidance of obstacles and the separation between routes. We propose a mathematical formulation leading to a combinatorial optimization problem, as well as efficient ad hoc resolution methods for the problem. The problem is solved in two steps. First, we design an individual route avoiding obstacles with respect to minimum route length by using a Branch and Bound (B&B) method. Afterwards, the design of multiple routes is solved by two different approaches: a B&B-based approach (where routes are generated sequentially in a given order) and a Simulated Annealing approach (where routes are generated simultaneously). The simulation results of a set of (artificial and real) test problems show the efficiency of our approach.

Dans le contexte du futur système de gestion du trafic aérien, un des objectifs consiste à réduire l’impact environnemental du trafic aérien. Pour respecter ce but, le concept de “free-route”, introduit dans les années 1990, semble bien adapté aujourd’hui. Les avions ne seraient plus contraints à voler le long de routes aériennes, mais pourraient suivre des trajectoires optimales en terme de consommation. L’objectif de cette thèse est d’introduire une nouvelle méthode de planification du trafic à l’horizon pré-tactique avec des objectifs quelques fois contradictoires, c’est-à-dire avec pour but de minimiser la consommation ou de façon équivalente la durée de trajet en tenant compte des conditions météorologiques et de minimiser l’encombrement de l’espace aérien.La méthode a été mise au point en deux étapes. La première étape a été consacrée au calcul d’une seule trajectoire optimale en terme de temps de vol en tenant compte du vent et de contraintes celles des zones interdites de survol. Cette optimisation est basée sur une adaptation de l’algorithme Ordered Upwind. La deuxième étape introduit un algorithme hybride développé, basé sur un algorithme de recuit simulé et sur l’algorithme déterministe développé dans la première étape, afin de minimiser un compromis entre la congestion et la consommation. L’algorithme combine ainsi la capacité d’atteindre la solution optimale globale via une recherche locale qui permet d’accélérer la convergence.Des simulations numériques avec des prévisions de vent sur du trafic européen donnent des résultats encourageants qui démontrent que la méthode globale est à la fois viable et bénéfique en terme du temps de vol total comme de la congestion globale donc de la diminution des conflits / In the context of the future Air Traffic Management system (ATM), one objective is to reduce the environmental impact of air traffic. With respect to this criterion, the “freeroute” concept, introduced in the mid 1990’s, is well suited to improve over nowadays airspace based ATM. Aircraft will no longer be restricted to fly along airways and may fly along fuel-optimal routes. The objective of this thesis is to introduce a novel pretactical trajectory planning methodology which aims at minimizing airspace congestion while taking into account weather conditions so as to minimize also fuel consumption.The development of the method was divided in two steps. The first step is dedicated to compute a time-optimal route for one aircraft taking into account wind conditions. This optimization is based on an adaptation of the Ordered Upwind Method on the sphere.The second step introduces a hybrid algorithm, based on simulated annealing and on the deterministic algorithm developed in the first step, in order to minimize congestion. Thus the algorithm combines the ability to reach a globally-optimal solution with a local-search procedure that speeds up the convergence.

Dans le cadre du projet européen SESAR, la nécessité d'accroître la capacité du trafic aérien a motivé la planification de trajectoires avions 4D (espace + temps). Afin de mettre en place une planification pré-tactique (évitement de zones avec une mauvaise météo ou congestionnées pour un avion) et de mettre en place une planification tactique (générer des ensembles de trajectoires 4D sans conflit), nous introduisons un nouvel algorithme : l'algorithme de propagation de la lumière (APL). Cet algorithme est basé sur une méthode de propagation de front d'onde qui s'inspire de l'analogie avec la propagation de la lumière et qui est adapté au problème de planification de trajectoires. L'APL donne des résultats satisfaisant pour une journée de trafic réel sur la France tout en satisfaisant les contraintes spécifiques à la gestion du trafic aérien. L'APL a ensuite été adapté pour prendre en compte les incertitudes qui concernent la vitesse réelle des avions. Ainsi adapté aux incertitude, l'APL a été testé sur la même journée de trafic avec mise en place de points RTA (Real Time Arrival). Les points RTA permettent de réduire l'incertitude dans le cas où l'APL n'arrive pas à résoudre les conflits. Les résultats obtenus sont très encourageants.

La thèse porte sur la conception et l'analyse mathématique de méthodes de Monte Carlo fiables et précises pour l'estimation de la (très petite) probabilité qu'un processus de Markov atteigne une région critique de l'espace d'état avant un instant final déterministe. L'idée sous-jacente aux méthodes de branchement multi-niveaux étudiées ici est de mettre en place une suite emboitée de régions intermédiaires de plus en plus critiques, de telle sorte qu'atteindre une région intermédiaire donnée sachant que la région intermédiaire précédente a déjà été atteinte, n'est pas si rare. En pratique, les trajectoires sont propagées, sélectionnées et répliquées dès que la région intermédiaire suivante est atteinte, et il est facile d'estimer avec précision la probabilité de transition entre deux régions intermédiaires successives. Le biais dû à la discrétisation temporelle des trajectoires du processus de Markov est corrigé en utilisant des régions intermédiaires perturbées, comme proposé par Gobet et Menozzi. Une version adaptative consiste à définir automatiquement les régions intermédiaires, à l’aide de quantiles empiriques. Néanmoins, une fois que le seuil a été fixé, il est souvent difficile voire impossible de se rappeler où (dans quel état) et quand (à quel instant) les trajectoires ont dépassé ce seuil pour la première fois, le cas échéant. La contribution de la thèse consiste à utiliser une première population de trajectoires pilotes pour définir le prochain seuil, à utiliser une deuxième population de trajectoires pour estimer la probabilité de dépassement du seuil ainsi fixé, et à itérer ces deux étapes (définition du prochain seuil, et évaluation de la probabilité de transition) jusqu'à ce que la région critique soit finalement atteinte. La convergence de cet algorithme adaptatif à deux étapes est analysée dans le cadre asymptotique d'un grand nombre de trajectoires. Idéalement, les régions intermédiaires doivent êtres définies en terme des variables spatiale et temporelle conjointement (par exemple, comme l'ensemble des états et des temps pour lesquels une fonction scalaire de l’état dépasse un niveau intermédiaire dépendant du temps). Le point de vue alternatif proposé dans la thèse est de conserver des régions intermédiaires simples, définies en terme de la variable spatiale seulement, et de faire en sorte que les trajectoires qui dépassent un seuil précocement sont davantage répliquées que les trajectoires qui dépassent ce même seuil plus tardivement. L'algorithme résultant combine les points de vue de l'échantillonnage pondéré et du branchement multi-niveaux. Sa performance est évaluée dans le cadre asymptotique d'un grand nombre de trajectoires, et en particulier un théorème central limite est obtenu pour l'erreur d'approximation relative. / The thesis deals with the design and mathematical analysis of reliable and accurate Monte Carlo methods in order to estimate the (very small) probability that a Markov process reaches a critical region of the state space before a deterministic final time. The underlying idea behind the multilevel splitting methods studied here is to design an embedded sequence of intermediate more and more critical regions, in such a way that reaching an intermediate region, given that the previous intermediate region has already been reached, is not so rare. In practice, trajectories are propagated, selected and replicated as soon as the next intermediate region is reached, and it is easy to accurately estimate the transition probability between two successive intermediate regions. The bias due to time discretization of the Markov process trajectories is corrected using perturbed intermediate regions as proposed by Gobet and Menozzi. An adaptive version would consist in the automatic design of the intermediate regions, using empirical quantiles. However, it is often difficult if not impossible to remember where (in which state) and when (at which time instant) did each successful trajectory reach the empirically defined intermediate region. The contribution of the thesis consists in using a first population of pilot trajectories to define the next threshold, in using a second population of trajectories to estimate the probability of exceeding this empirically defined threshold, and in iterating these two steps (definition of the next threshold, and evaluation of the transition probability) until the critical region is reached. The convergence of this adaptive two-step algorithm is studied in the asymptotic framework of a large number of trajectories. Ideally, the intermediate regions should be defined in terms of the spatial and temporal variables jointly (for example, as the set of states and times for which a scalar function of the state exceeds a time-dependent threshold). The alternate point of view proposed in the thesis is to keep intermediate regions as simple as possible, defined in terms of the spatial variable only, and to make sure that trajectories that manage to exceed a threshold at an early time instant are more replicated than trajectories that exceed the same threshold at a later time instant. The resulting algorithm combines importance sampling and multilevel splitting. Its preformance is evaluated in the asymptotic framework of a large number of trajectories, and in particular a central limit theorem is obtained for the relative approximation error.

À 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.