Dans cette thèse, nous proposons des modèles probabilistes et statistiques d'analyse de données multidimensionnelles pour la prévision de l'incertitude sur les trajectoires d'aéronefs. En supposant que pendant le vol, chaque aéronef suit sa trajectoire 3D contenue dans son plan de vol déposé, nous avons utilisé l'ensemble des caractéristiques de l'environnement des vols comme variables indépendantes pour expliquer l'heure de passage des aéronefs sur les points de leur trajectoire de vol prévue. Ces caractéristiques sont : les conditions météorologiques et atmosphériques, les paramètres courants des vols, les informations contenues dans les plans de vol déposés et la complexité de trafic. Typiquement, la variable dépendante dans cette étude est la différence entre les instants observés pendant le vol et les instants prévus dans les plans de vol pour le passage des aéronefs sur les points de leur trajectoire prévue : c'est la variable écart temporel. En utilisant une technique basée sur le partitionnement récursif d'un échantillon des données, nous avons construit quatre modèles. Le premier modèle que nous avons appelé CART classique est basé sur le principe de la méthode CART de Breiman. Ici, nous utilisons un arbre de régression pour construire une typologie des points des trajectoires des vols en fonction des caractéristiques précédentes et de prévoir les instants de passage des aéronefs sur ces points. Le second modèle appelé CART modifié est une version améliorée du modèle précédent. Ce dernier est construit en remplaçant les prévisions calculées par l'estimation de la moyenne de la variable dépendante dans les nœuds terminaux du modèle CART classique par des nouvelles prévisions données par des régressions multiples à l'intérieur de ces nœuds. Ce nouveau modèle développé en utilisant l'algorithme de sélection et d'élimination des variables explicatives (Stepwise) est parcimonieux. En effet, pour chaque nœud terminal, il permet d'expliquer le temps de vol par des variables indépendantes les plus pertinentes pour ce nœud. Le troisième modèle est fondé sur la méthode MARS, modèle de régression multiple par les splines adaptatives. Outre la continuité de l'estimateur de la variable dépendante, ce modèle permet d'évaluer les effets directs des prédicteurs et de ceux de leurs interactions sur le temps de passage des aéronefs sur les points de leur trajectoire de vol prévue. Le quatrième modèle utilise la méthode d'échantillonnage bootstrap. Il s'agit notamment des forêts aléatoires où pour chaque échantillon bootstrap de l'échantillon de données initial, un modèle d'arbre de régression est construit, et la prévision du modèle général est obtenue par une agrégation des prévisions sur l'ensemble de ces arbres. Malgré le surapprentissage observé sur ce modèle, il est robuste et constitue une solution au problème d'instabilité des arbres de régression propre à la méthode CART. Les modèles ainsi construits ont été évalués et validés en utilisant les données test. Leur application au calcul des prévisions de la charge secteur en nombre d'avions entrants a montré qu'un horizon de prévision d'environ 20 minutes pour une fenêtre de temps supérieure à 20 minutes permettait d'obtenir les prévisions avec des erreurs relatives inférieures à 10%. Parmi ces modèles, CART classique et les forêts aléatoires présentaient de meilleures performances. Ainsi, pour l'autorité régulatrice des courants de trafic aérien, ces modèles constituent un outil d'aide pour la régulation et la planification de la charge des secteurs de l'espace aérien contrôlé.

Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins quadridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode développée.

Les visualisations de données permettent de transmettre de l'information aux utilisateurs. Pour explorer et comprendre les données, les utilisateurs sont amenés à interagir avec ces visualisations.Toutefois, l'interaction avec les visualisations modifie le visuel. Pour éviter des changements brusques et garder l'utilisateur focalisé sur les objets graphiques d'intérêt, des transitions visuelles sont nécessaires pour accompagner les modifications de la visualisation. Ces transitions visuelles peuvent être codées sous la forme d'animations, ou de techniques qui permettent de faire des correspondances, ou des liens avec des données représentées sur plusieurs affichages. Le premier objectif de cette thèse était d'étudier les bénéfices et les propriétés des animations pour l'exploration et la compréhension de grandes quantités de données multidimensionnelles. Nous avons établi en conséquence une taxonomie des transitions animées en visualisation d'information basée sur les tâches des utilisateurs. Cette taxonomie a permis de constater qu'il n'existe pas de contrôle utilisateur sur la direction des objets durant l'animation. Nous avons donc proposé des interactions pour le contrôle de la direction des objets graphiques lors d'une transition animée. D'autre part, nous avons étudié une technique de transition animée mettant en jeu une rotation 3D entre visualisations. Nous avons identifié les avantages qu'elle pouvait apporter et en avons proposé une amélioration.Le second objectif était d'étudier les transitions visuelles dans le domaine du Contrôle du Trafic Aérien. En effet, les contrôleurs utilisent de nombreuses visualisations qui comportent des informations étalées et dupliquées sur plusieurs affichages: l'écran Radar, le tableau de strips, des listes spécifiques d'avions (départ, arrivées) etc. Ainsi dans leur activité, les Contrôleurs Aériens réalisent des transitions visuelles en recherchant et en reliant de l'information à travers les différents affichages. Nous avons étudié comment les animations pouvaient être utilisées dans le domaine du contrôle aérien en implémentant un prototype d'image radar regroupant trois visualisations usuelles pour instrumenter l'activité de supervision du trafic aérien.

Dans cette thèse, nous nous sommes intéressés à deux problèmes industriels dans le domaine du transport. Le premier est un problème de conception de réseau de service avec gestion de ressources pour un transport régulier de fret. Le second est le problème de gestion de perturbation dans le domaine aérien, sujet du challenge ROADEF'2009. Dans les deux cas, il s'agit de problèmes pratiques difficiles qui comportent des contraintes complexes non standard. Le défi est d'autant plus marqué que les instances à résoudre sont de grandes tailles et que les problèmes comportent une dimension temporelle forte. Nous avons analysé la complexité des problèmes en étudiant la complexité de problèmes combinatoires purs, sous-problèmes au cœur de nos problèmes industriels. Nous présentons différentes formulations MIP du problème de conception d'un réseau de service avec gestion de flotte. Il ressort de notre étude que les formulations à base de cycles pour les véhicules sont très prometteuses. Finalement, nous présentons notre contribution au challenge ROADEF'2009. Nous proposons une méthode de résolution rapide, basée sur une décomposition, permettant de trouver de bonnes solutions à un problème industriel complexe en temps limité.

La gestion du trafic aérien est un système complexe. Actuellement en pleine mutation, une des problématiques essentielles à l'évolution du système est la recherche de méthodes automatiques de résolution de conflits. Nous présentons d'abord un nouveau modèle de trajectoire courbe basé sur les B-splines et permettant de définir une trajectoire à l'aide d'un nombre très limité de paramètres. À partir de cette modélisation, nous arrêtons une nouvelle formulation du problème de résolution de conflits pour obtenir un problème d'optimisation continue. Celle-ci repose sur une formulation dite semi-infinie de la contrainte de séparation entre deux avions. La manière dont nous avons défini la fonction-objectif et les fonctions contraintes nous permettent également d'en calculer les gradients. Nous utilisons trois différentes méthodes d'optimisation pour résoudre notre problème. Une méthode globale stochastique est d'abord testée : les algorithmes génétiques, couramment utilisés pour le problème de résolution de conflits. Deux méthodes d'optimisation locale sont aussi mises en œuvre, une méthode de points intérieurs et une méthode d'optimisation sans dérivées. Enfin, nous présentons des résultats numériques prometteurs montrant la fiabilité de l'optimisation locale pour le problème de résolution de conflits. Notre méthodologie, alliant une modèle de trajectoire courbe parcimonieux et une méthode d'optimisation locale appliquée à notre formulation mathématique du problème, est une option crédible pour le problème de résolution de conflits aériens.

Afin de pouvoir satisfaire la demande sans cesse croissante du trafic aérien, le futur système de gestion du trafic aérien utilisera le concept d'opérations basées sur les trajectoires (Trajectory Based Operations), qui augmentera la capacité du trafic aérien, en réduisant la charge de travail du contrôleur. Pour ce faire, les tâches de détection et de résolution de conflits seront transférées depuis la phase tactique vers la phase stratégique de la planification. Dans le cadre de ce nouveau paradigme pour le système de gestion du trafic aérien, nous introduisons dans cette thèse une méthodologie qui permet d'aborder ce problème de planification stratégique de trajectoires d'avion à l'échelle d'un pays ou d'un continent. Le but de la méthodologie proposée est de minimiser l'interaction globale entre les trajectoires d'avion, en affectant de nouveaux créneaux de décollage, de nouvelles routes et de nouveaux niveaux de vols aux trajectoires impliquées dans l'interaction. De plus, afin d'améliorer la robustesse du plan stratégique de vols obtenu, nous prenons en compte l'incertitude de la position de l'avion et de son heure d'arrivée à un point donné de la trajectoire de l'avion. Nous proposons une formulation mathématique de ce problème de planification stratégique conduisant à un problème d'optimisation discrète et un problème d'optimisation en variables mixtes, dont la fonction objectif est basée sur le nouveau concept d'interaction. Un algorithme efficace en termes de temps de calcul pour évaluer l'interaction entre des trajectoires d'avion pour des applications de grande taille est introduit et mis en œuvre. Des méthodes de résolution basées sur des algorithmes de type métaheuristique et métaheuristique hybride ont été développées pour résoudre ces problèmes d'optimisation de grande taille. Enfin, la méthodologie globale de planification stratégique de trajectoires d'avion est mise en œuvre et testée sur des données de trafic, prenant en compte des incertitudes, pour l'espace aérien français et l'espace aérien européen, impliquant plus de 30000 vols. Des plans de vols 4D sans conflits et robustes ont pu être produits avec des temps de calcul acceptables dans un contexte opérationnel, ce qui démontre la viabilité de l'approche proposée.

Le trafic aérien en Europe représente environ 30 000 vols quotidiens actuellement. Selon les prévisions de l’organisme Eurocontrol, ce trafic devrait croître de 70% d’ici l’année 2020 pour atteindre 50 000 vols quotidiens. L’espace aérien, découpé en zones géographiques appelées secteurs de contrôle, atteindra bientôt son niveau de saturation vis-à-vis des méthodes actuelles de planification et de contrôle. Afin d’augmenter la quantité de trafic que peut absorber le système, il est nécessaire de diminuer la charge de travail des contrôleurs aériens en les aidant dans leur tâche de séparation des avions. En se fondant sur les demandes de plans de vol des compagnies aériennes, nous proposons une méthode de planification des trajectoires en 4D permettant de présenter au contrôleur un trafic dont la plupart des conflits auront été évités en avance. Cette planification s’établit en deux étapes successives, ayant chacune un unique degré de liberté : une allocation de niveaux de vol permettant la résolution des conflits en croisière puis une allocation d’heures de décollage permettant de résoudre les conflits restants. Nous présentons des modèles pour ces deux problèmes d’optimisation fortement combinatoires, que nous résolvons en utilisant la programmation par contraintes ou les algorithmes évolutionnaires, ainsi que des techniques permettant de prendre en compte des incertitudes sur les heures de décollage ou le suivi de trajectoire. Les simulations conduites sur l’espace aérien français mènent à des situations où tous les conflits sont évités, avec des retards alloués de l’ordre d’une minute en moyenne (80 à 90 minutes pour le vol le plus retardé) et un écart par rapport à l’altitude optimale limité à un niveau de vol pour la quasi totalité des vols. La prise en compte d’incertitudes de manière statique dégrade fortement ces solutions peu robustes, mais nous proposons un modèle dynamique utilisant une fenêtre glissante susceptible de prendre en compte des incertitudes de quelques minutes avec un impact réduit sur le coût de l’allocation. / Air traffic in Europe represents about 30,000 flights each day and forecasts from Eurocontrol predict a growth of 70% by 2020 (50,000 flights per day). The airspace, made up of numerous control sectors, will soon be saturated given the current planification and control methods. In order to make the system able to cope with the predicted traffic growth, the air traffic controllers workload has to be reduced by automated systems that help them handle the aircraft separation task. Based on the traffic demand by airlines, this study proposes a new planning method for 4D trajectories that provides conflict-free traffic to the controller. This planning method consists of two successive steps, each handling a unique flight parameter : a flight level allocation phase followed by a ground holding scheme.We present constraint programming models and an evolutionary algorithm to solve these large scale combinatorial optimization problems, as well as techniques for improving the robustness of the model by handling uncertainties of takeoff times and trajectory prediction. Simulations carried out over the French airspace successfully solved all conflicts, with a mean of one minute allocated delay (80 to 90 minutes for the most delayed flight) and a discrepancy from optimal altitude of one flight level for most of the flights. Handling uncertainties with a static method leads to a dramatic increase in the cost of the previous non-robust solutions. However, we propose a dynamic model to deal with this matter, based on a sliding time horizon, which is likely to be able to cope with a few minutes of uncertainty with reasonable impact on the cost of the solutions.

Cette thèse explore des pistes d'amélioration du système de trafic aérien dans l'espace océanique de l'Atlantique Nord (NAT). D'abord, on considère le système actuel, où les avions suivent les rails prédefinis. On favorise les re-routages entre rails, diminuant la congestion dans l'espace continental. On applique des méthodes stochastiques d'optimisation pour trouver une configuration de vols sans conflits avec la séparation reduite entre aéronefs. Ensuite, on simule la planification des trajectoires avec le Wind Networking (WN). La source prinicipale des erreurs dans la prédiction de trajectoires étant l'incertitude dans la prévision du vent, le WN permet aux avions d'échanger leurs vents mesurés afin d'ajuster leurs prédictions. Enfin, on introduit le concept de free-flight dans NAT. Etant donné des trajectoires vent-optimales, on applique une méthode stochastique d'optimisation pour réduire le nombre de conflits au niveau stratégique, tout en conservant les trajectoires proches de leur optimum. Nos résultats numériques mettent en évidence plusieurs pistes pour améliorer le système de trafic aérien dans NAT, en considérant de nouvelles technologies et de nouveaux concepts. / This thesis investigates the ways to improve the air traffic system in the highly congested North Atlantic oceanic airspace (NAT). First, we consider the current system, where aircraft follow predefined NAT tracks. We favor the re-routings between tracks, decreasing congestion in pre-oceanic airspace, and apply stochastic methods of optimization to find a conflict-free flight configuration with reduced separation between aircraft. Second, we simulate trajectory prediction by Wind Networking (WN). While the main source of time prediction errors is the uncertainty in wind forecast, WN permits aircraft to exchange measured winds and adjust their predictions using this recent and accurate information. Third, we study the impact of introducing the free flight concept in NAT. We apply a stochastic method of optimization on data provided by NASA consisting of NAT flights with wind optimal trajectories. The aim is to reduce the number of conflicts on the strategic level, while keeping the trajectories close to the optimal routes. Our computational experiments show that the air traffic situation in NAT can be improved in several different ways, considering new technologies and new trajectory planning concepts.

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.

Avec la croissance continue du trafic aérien et la limitation des ressources, il est nécessaire de réduire la congestion de l'espace aérien. Ces dernières années, un intérêt particulier a été porté au problème de la sectorisation de l'espace aérien.Pour pallier à cette augmentation continue du trafic en Europe, il est nécessaire d'optimiser la gestion du trafic aérien. Une automatisation de la sectorisation de l'espace aérien peut permettre, dans cette optique, d'accroître l'adaptabilité des configurations du secteur aérien à une nouvelle demande de trafic. L'objectif de la première partie de cette thèse est de proposer une méthode globale de sectorisation de l'espace aérien européen en se basant sur une modélisation mathématique et des méthodes d'optimisation heuristiques. La méthode de sectorisation proposée est basée sur la division initiale de l'espace aérien en cellules de Voronoi à l'aide de méthodes des k-moyennes. Pour des raisons de complexité combinatoire induite, un algorithme d'optimisation stochastique est utilisé pour résoudre le problème de sectorisation. Un algorithme génétique est utilisé pour construire les secteurs de l'espace aérien dans plusieurs zones de contrôle européennes, en se basant sur des données réelles de trafic aérien pendant plusieurs jours.De plus, les configurations du secteur de l'espace aérien doivent être adaptées dynamiquement pour offrir une efficacité et une flexibilité maximales en fonction des conditions météorologiques et de circulation. L'objectif de la deuxième partie de cette thèse est d'adapter automatiquement les configurations de l'espace aérien en fonction de l'évolution du trafic, au cours d'une journée de fonctionnement. Pour atteindre cet objectif, il faut considérer que l'espace aérien est divisé en blocs d'espaces aériens 3D qui doivent être groupés ou dégroupés en fonction de l'état du trafic. La méthode proposée est basée sur une technique de partitionnement de graphe et sur des algorithmes génétiques. La méthode est testée sur plusieurs zones de contrôle européennes. / With the continuous air traffic growth and limits of resources, there is a need for reducing the congestion of the airspace systems. Nowadays, several projects are launched, aimed at modernizing the global air transportation system and air traffic management. In recent years, special interest has been paid to the solution of the airspace sectorization problem. This thesis is devoted to studying the airspace sectorization in Europe and the possibilities to improve it.The airspace sectorization needs to be optimized with the support of automation in order to increase an adaptability of airspace sector configurations to the new traffic demands. The aim of the first part of this thesis is to propose a global method for the sector design of the European airspace based on a mathematical modeling and heuristic optimization methods. The proposed resolution method to solve the sector design problem is based on the initial division of the airspace into Voronoi cells using k-means clustering algorithm. Then, due to the induced combinatorial complexity, a stochastic optimization method is applied to solve the sector design problem. Resolution method based on metaheuristic algorithm called Genetic Algorithm (GA) has been developed to build airspace sectors in several control areas of Europe, involving traffic data for several days. Furthermore, airspace sector configurations need to be dynamically adjusted to provide maximum efficiency and flexibility in response to changing weather/traffic conditions. The objective of the second part of this thesis is to automatically adapt the airspace configurations according to the evolution of traffic. In order to reach this objective, the airspace is considered to be divided into predefined 3D airspace blocks which have to be grouped or ungrouped depending on the traffic situation. The resolution method based on the graph partitioning technique and on the metaheuristic algorithm (GA) has been developed to generate a sequence of sector configurations, composed of the predefined airspace blocks. The overall methodology, is implemented and tested with air traffic data taken for one day of operation and for several different airspace control areas of Europe.