Programmation stochastique à deux étapes pour l’ordonnancement des arrivées d’avions sous incertitude

Dans le contexte d'une augmentation soutenue du trafic aérien et d'une faible marge d'expansion des capacités aéroportuaires, la pression s'accroît sur les aéroports les plus fréquentés pour une utilisation optimale de leur infrastructure, telle que les pistes, reconnues comme le goulot d'étranglement des opérations aériennes. De ce besoin opérationnel est né le problème d'ordonnancement des atterrissages d'avions, consistant à trouver pour les avions se présentant à un aéroport la séquence et les heures d'atterrissage optimales par rapport à certains critères (utilisation des pistes, coût total des retards, etc) tout en respectant des contraintes opérationnelles et de sécurité.  En réponse à ce besoin également, depuis les années 1990 aux États-Unis et en Europe, des outils d'aide à la décision ont été mis à la disposition des contrôleurs aériens, afin de les assister dans leur tâche d'assurer la sécurité et surtout la performance des flux d'arrivée.  Un certain nombre de travaux de recherche se sont focalisés sur le cas déterministe et statique du problème d'atterrissage d'avions. Cependant, le problème plus réaliste, de nature stochastique et dynamique, a reçu une attention moindre dans la littérature. De plus, dans le cadre du projet européen de modernisation des systèmes de gestion de trafic aérien, il a été proposé d’étendre l’horizon opérationnel des outils d’aide à la décision de manière à prendre en compte les avions plus loin de l'aéroport de destination. Cette extension de l'horizon opérationnel  promet une meilleure gestion des flux d'arrivées via un ordonnancement précoce plus efficient. Néanmoins, elle est inévitablement accompagnée d'une détérioration de la qualité des données d'entrée, rendant indispensable la prise en compte de leur stochasticité.   L’objectif de cette thèse est l’ordonnancement des arrivées d’avions, dans le cadre d'un horizon opérationnel étendu, où les heures effectives d'arrivée des avions sont incertaines. Plus précisément, nous proposons une approche basée sur la programmation stochastique à deux étapes. En première étape, les avions sont pris en considération à 2-3 heures de leur atterrissage prévu à l'aéroport de destination. Il s'agit de les ordonnancer à un point de l'espace aérien aéroportuaire, appelé IAF (Initial Approach Fix). Les heures effectives de passage à ce point sont supposées suivre des distributions de probabilité connues. En pratique, cette incertitude peut engendrer un risque à la bonne séparation des avions nécessitant l'intervention des contrôleurs. Afin de limiter la charge de contrôle conséquente, nous introduisons des contraintes en probabilité traduisant le niveau de tolérance aux risques de sécurité à l'IAF après révélation de l'incertitude. La deuxième étape correspond au passage effectif des avions considérés à l'IAF. Comme l'incertitude est révélée, une décision de recours est prise afin d'ordonnancer les avions au seuil de piste en minimisant un critère de deuxième étape (charge de travail des contrôleurs, coût du retard, etc).   La démonstration de faisabilité et une étude numérique de ce problème d'ordonnancement des arrivées d'avions en présence d'incertitude constituent la première contribution de la thèse. La modélisation de ce problème sous la forme d’un problème de programmation stochastique à deux étapes et sa résolution par décomposition de Benders constituent la deuxième contribution.  Finalement, la troisième contribution étend le modèle proposé au cas opérationnel, plus réaliste où nous considérons plusieurs points d’approche initiale. Airport operations are well known to be a bottleneck in the air traffic system, which puts more and more pressure on the world busiest airports to optimally schedule landings, in particular, and also – but to a smaller extent – departures. The Aircraft Landing Problem (ALP) has arisen from this operational need. ALP consists in finding for aircraft heading to a given airport a landing sequence and landing times so as to optimize some given criteria (optimizing runway utilization, minimizing delays, etc) while satisfying operational constraints (safety constraints mainly). As a reply to this operational need, decision support tools have been designed and put on service for air traffic controllers since the early nineties in the US as well as in Europe.  A considerable number of publications dealing with ALP focus on the deterministic and static case. However, the aircraft landing problem arising in practice has a dynamic nature riddled with uncertainties. In addition, operational horizon of  current decision support tools are to be extended so that aircraft are captured at larger distances from the airport to hopefully start the scheduling process earlier. Such a horizon extension affects the quality of input data which enlarges the uncertainty effect.  In this thesis, we aim at scheduling aircraft arrivals under uncertainty. For that purpose, we propose an approach based on two-stage stochastic programming. In the first stage, aircraft are captured at a large distance from the destination airport. They are to be scheduled on the same initial approach fix (IAF), a reference point in the near-to-airport area where aircraft start their approach phase preparing for landing. Actual IAF arrival times are assumed to be random variables with known probability distributions.   In practice, such an uncertainty may cause loss of safety separations between aircraft.  In such situations, air traffic controllers are expected to intervene to ensure air traffic safety. In order to alleviate the consequent air traffic control workload, chance constraints are introduced so that the safety risks around the IAF are limited to an acceptable level once the uncertainty is revealed. The second stage corresponds to the situation where aircraft are actually close to the IAF. In this stage, the uncertainty is revealed and a recourse decision is made in order to schedule aircraft on the runway threshold so that a second-stage cost function is minimized (e.g., air traffic control workload, delay cost, etc).  Our first contribution is a proof of concept of the extended aircraft arrival management under uncertainty and a computational study on optimization parameters and problem characteristics. Modeling this problem as a two-stage stochastic programming model and solving it by a Benders decomposition is our second contribution. Finally, our third contribution focuses on extending our model to the more realistic case, where aircraft in the first stage are scheduled on several IAFs.

Keyphrases: Programmation stochastique à deux étapes, Décomposition de Benders, Ordonnancement des arrivées d'avions, Two-stage stochastic programming, Benders decomposition, Aircraft arrival scheduling