Régulation court terme du trafic aérien et optimisation combinatoire

Objectifs et organisation de l’ATFM en Europe

Qu’est ce que la régulation aérienne ? L’espace aérien est une ressource limitée qui est soumise à une forte demande dans certaines parties du monde telles que l’Europe de l’Ouest, l’Amérique du Nord et l’Asie du Sud Est. Afin d’assurer le respect des normes de sécurité imposant une séparation physique minimale entre deux avions, cet espace aérien a été divisé dans ces zones en différents secteurs aériens, zones d’espace tridimensionnelles : à chaque secteur est affectée une équipe de contrôleurs aériens qui est responsable du respect de ces normes en temps réel : c’est le contrôle aérien (ATC pour Air Traffic Control). Le nombre d’avions qu’une équipe de contrôleurs peut gérer en même temps est évidemment limité et face à la forte demande de trafic aérien, un mécanisme est nécessaire pour éviter les surcharges de travail pour les contrôleurs et pour assurer une bonne utilisation des ressources de contrôle disponibles : ce mécanisme de régulation du trafic aérien est appelé ATFM (Air Traffic Flow Management). Les trois objectifs principaux de l’ATFM sont alors : prévenir les surcharges, lisser l’écoulement du trafic et minimiser les conséquences des actions de régulation notamment pour les compagnies aériennes.
Historique de la régulation aérienne en Europe En Europe les premières tentatives de gestion des flux de trafic pour répondre à une saturation du système de contrôle du trafic aérien (ATC) ont été envisagées à la fin des années 60 et mises en place au début des années 70 (1972 en France, 1975 en Allemagne). Ces tentatives n’ont pas été coordonnées à un niveau supranational du fait de la séparation de la responsabilité de la gestion du trafic entre les différents pays. Bien que pouvant être efficaces au niveau local, ces premières mises en œuvre aggravèrent les conséquences des problèmes croissants de congestion au niveau européen, du fait d’un manque de communication et de coordination entre les différentes unités d’ATFM ([15]). Les bases d’un système européen global d’ATFM (en remplacement des différents systèmes nationaux) ont été posées lors du meeting ICAO (International Civil Aviation Organisation) consacré à l’espace aérien européen en 1980. La CFMU (Central Flow Management Unit) devait voir réellement le jour Régulation court terme du trafic aérien et optimisation combinatoire en juillet 1989, sous la responsabilité naturelle d’Eurocontrol, l’organisation créée en 1963 afin de centraliser progressivement la gestion du trafic aérien en Europe assurée jusqu’ici par les différentes administrations nationales. Pour mémoire l’équivalent américain de la CFMU s’appelle Air Traffic Control System Command Center (ATCCC).
L’évolution de la régulation aérienne : de l’ATFM à l’ATFCM Depuis avril 2004 et la publication du document « Air Traffic Flow and Capacity Management Strategy » ([5]), on assiste à un glissement terminologique de ATFM vers ATFCM pour désigner les activités de régulation assurées par la CFMU. Le C pour Capacity insiste ainsi sur le fait que les actions de régulation ne concerneront plus seulement la demande (le trafic) mais également l’offre (la capacité de contrôle), traduisant ainsi un rééquilibrage des objectifs de la CFMU en faveur des usagers des services de contrôle aérien.
La CFMU et les autres acteurs du trafic aérien L’ATFM est donc un service de gestion globale du trafic aérien contribuant à assurer la circulation sûre, ordonnée et efficace des flux de trafic aérien. La CFMU fournit ce service de gestion des flux de trafic aux gestionnaires de l’espace aérien (Air Traffic Service ATS) comprenant notamment les centres de contrôles aérien et aux utilisateurs de cet espace aérien (Aircraft Operators AOs) dont font partie les compagnies aériennes. La CFMU cherche à optimiser l’utilisation du système aérien : à la fois celle de l’espace-temps aérien (Airspace Time) et celle des capacités du système (capacités des centres de contrôles et des aéroports). Envers l’ATS l’objectif est de lisser l’écoulement du trafic et de protéger les contrôleurs aériens des surcharges. Envers les AOs l’objectif est d’aider à la planification des vols et de minimiser les surcoûts liés à la congestion.

L’incertitude sur le système aérien

     Le système aérien est un système multi-acteurs extrêmement complexe comprenant des facteurs techniques, humains et naturels tous porteurs d’incertitude. Ainsi la vitesse et la direction du vent, la charge de l’avion, son état technique, les éventuelles mesures d’évitement en vol commandées par les contrôleurs aériens vont fortement peser sur la prévision de marche des avions. La précision des prévisions d’heure de passage dans des secteurs ou d’arrivée à l’aéroport final va donc évidemment diminuer avec l’augmentation de l’horizon de prévision. Il existe cependant un effet de seuil significatif pour les prévisions avant le décollage. En effet la taille des créneaux de décollage alloués (créneau ATFM de 15 minutes), la tolérance existante sur le respect de ces heures de décollage, l’incertitude sur les temps de roulage vont entraîner que la marge d’incertitude sur une prévision effectuée avant le décollage d’une heure de passage d’un avion dans un secteur va, en de nombreux cas, dépasser la durée de survol de ce secteur. Etant donné que la régulation actuelle est basée sur des prévisions effectuées quelques heures avant la saturation prévue, on comprend la limite indépassable de la régulation basée sur les retards au sol. La commission d’examen des performances d’Eurocontrol l’écrit explicitement dans son rapport 2005 ([4]) « Les régulations ATFM ne peuvent pas précisément contrôler les flux à travers les secteurs où le temps de transit est généralement plus court que le créneau ATFM lui-même ». L’ajout d’un nouveau filtre de régulation agissant notamment sur les avions en vol, avec un horizon de prévision très inférieur permettrait de prendre des décisions avec une incertitude significativement réduite.

Le cadre général de la commande prédictive à horizon glissant

    La principale raison d’être du régulateur court terme est le contexte hautement dynamique du système aérien. Les conséquences des décisions prises à un instant donné doivent donc être réévaluées continuellement et le cas échéant, des modifications ou de nouvelles actions doivent pouvoir être décidées. Pour ces raisons le processus de régulation envisagé est basé sur la commande prédictive à horizon glissant. Cette technique de commande consiste à calculer à un instant donné les prévisions de valeur des variables caractérisant notre système pour un horizon de temps appelé horizon de prédiction. On calcule alors une politique à appliquer aux variables sur lesquelles on peut agir, politique à appliquer sur un horizon de temps inférieur à l’horizon de prédiction et appelé parfois horizon de commande. Enfin on applique au système les éléments de la politique calculée correspondant à la première période suivant l’instant présent. A l’issue de cette période, la politique à suivre est réévaluée en fonction des nouvelles données disponibles, les deux horizons ayant « glissé » d’une période. La durée d’une période et la longueur des horizons de prédiction et de commande sont les principaux paramètres de la commande prédictive à horizon glissant.

Nombre d’avions présents au dessus d’un secteur

    Une manière d’agir directement sur le lissage de la charge des secteurs est d’introduire une capacité instantanée, c’est-à-dire de limiter le nombre d’avions présents à une date donnée au dessus d’un secteur. Cette approche a l’avantage de prendre en compte explicitement la durée pendant laquelle les vols restent au dessus d’un secteur, car tant qu’ils sont présents, ils demandent de l’attention au contrôleur aérien. Dans le cas où l’on ne considère que le nombre d’avions entrants, on ne prend pas en compte la sortie effective de l’avion du secteur : qu’elle se situe 2 minutes après son entrée ou 15 minutes ne change rien au calcul de la charge. L’inconvénient de l’approche en nombre d’avions présents est d’ajouter un nombre important de contraintes au problème d’optimisation, nombre dépendant de la taille de l’horizon de simulation et du pas de discrétisation du temps. Une autre difficulté réside dans le choix des valeurs à utiliser comme limites étant donné qu’il n’y a rien de tel dans les définitions officielles de capacité de secteurs. Enfin, dans le cas d’un processus basé sur la programmation linéaire en nombres entiers tel celui que nous avons retenu, l’ajout de telles contraintes peut compliquer la résolution générale du problème en rendant plus difficile le respect des contraintes d’intégrité.

Le Ground Holding Problem

    Basé sur l’idée qu’un retard au sol est moins coûteux qu’un retard en l’air, ce problème cherche à allouer des retards au décollage aux avions afin d’éviter des temps d’attente dus à la capacité limitée des aéroports lors de leur arrivée. Le GHP est aussi quelquefois appelé Slot Allocation Problem (SAP) dans la littérature spécialisée. Les premières recherches sur ce sujet ont été effectuées aux Etats-Unis où les problèmes de saturation sont essentiellement localisés au niveau des aéroports, ce qui explique que la capacité des secteurs n’ait pas été prise en compte dans les premiers modèles. D’une manière naturelle les chercheurs se sont d’abord intéressés à la version la plus simple du problème dont la résolution pourra ensuite servir de base pour la résolution des extensions. Dans cet esprit, la version la plus ancienne et la plus simple du GHP est le Single-Airport Ground Holding Problem (SAGHP) dans lequel on ne considère qu’un seul aéroport d’arrivée pour un ensemble donné d’aéroports de départ. On considère au contraire un réseau entier d’aéroports dans le Multi-Airport Ground Holding Problem (MAGHP). A noter que dans ce cas, on introduit également l’interdépendance des vols entre eux et que les retards se propagent ainsi dans le réseau en prenant en compte le fait qu’un avion effectue généralement plusieurs vols dans la journée. Si aux Etats-Unis les saturations sont limitées aux aéroports, ce n’est pas du tout le cas en Europe en raison de la proximité de grands pôles d’échanges et de la complexité induite par le découpage territorial. Pour pouvoir prendre en compte ces saturations, on peut introduire la capacité de l’aéroport de départ ou la capacité des secteurs en vol tant pour le SAGHP que pour le MAGHP : on parle alors de Air Traffic Flow Management Problem. On trouve des auteurs précisant plutôt « with en-route capacities ».

Table des matières

Introduction Générale
chapitre I La régulation court terme du trafic aérien et son contexte
I. Organisation actuelle de la régulation du trafic aérien
I.1. Objectifs et organisation de l’ATFM en Europe
I.2. Mise en œuvre opérationnelle
II. Limites de l’organisation actuelle et réponses de la régulation court terme
II.1. Les faiblesses indépassables de la régulation actuelle
II.2. Les principes de la régulation court terme
III. Principes généraux du régulateur court terme du trafic aérien
III.1. Préliminaires
III.2. Cahier des charges de la régulation court terme
III.3. Architecture globale du régulateur court terme
chapitre II Le module d’optimisation du régulateur court terme
I. Description du problème d’optimisation principal
I.1. Description du problème à résoudre
I.2. Traduction des contraintes et des objectifs dans la modélisation
I.3. Autres choix de modélisation
II. Bibliographie sur les méthodes de résolutions candidates
II.1. Introduction
II.2. Taxinomie des problèmes de régulation ATFM
II.3. Etat de l’art sur le GHP et ses extensions
III. Choix de la méthode de génération de colonnes
III.1. Pourquoi la programmation linéaire en nombres entiers ?
III.2. Pourquoi la génération de colonnes ?
chapitre III Résolution du problème d’optimisation principal par la méthode de génération de colonnes
I. Notions générales sur la génération de colonnes et notations utilisées
I.1. La méthode de génération de colonnes
II. Modélisation du problème maître par un PLNE
II.1. Formulation mathématique du problème d’optimisation
II.2. Détails de la formulation
II.3. Complexité du problème maître
III. Architecture du système de résolution
III.1. Architecture globale du processus de résolution
IV. Formulation des différents modules de résolution
IV.1. Le problème maître restreint (RMP)
IV.2. Le processus d’initialisation du RMP
IV.3. Le sous problème de tarification
V. Le processus d’obtention d’une solution entière
V.1. La méthode branch-and-price dans le cas général
V.2. Application de la méthode de branch-and-price
chapitre IV Modélisation et résolution du sous problème de tarification
I. Description détaillée du sous problème de tarification
I.1. Entrées/sorties du sous problème de tarification
I.2. Lien avec les problèmes de plus courts chemins
I.3. Bibliographie et taxinomie des problèmes de plus courts chemins pertinents
II. Modélisation du sous problème de tarification
II.1. Modélisation en un graphe
II.2. La fonction coût réduit
III. Résolution du sous problème de tarification
III.1. Principe général de la résolution
III.2. Phase I : plus court chemin : recherche spatiale
III.3. Extension des trajectoires partielles
III.4. Règles de sélection des feuilles à examiner
III.5. Phase II : Programmation dynamique : recherche temporelle
chapitre V Mise en œuvre expérimentale et résultats
I. Objectifs de l’expérimentation et vue d’ensemble
I.1. Objectifs de la mise en œuvre expérimentale
I.2. Contexte de la mise en œuvre expérimentale
I.3. Vue d’ensemble sur la mise en œuvre expérimentale
II. Résolution du sous problème de tarification
II.1. Les différents scénarios et les paramètres de l’algorithme
II.2. Résultats et temps de calcul
II.3. Conclusions et stratégie adoptée pour la résolution du sous problème de tarification
III. Résolution globale du problème maître
III.1. Boucle de génération de colonnes
III.2. Gestion des trajectoires artificielles
chapitre VI Conclusion générale et perspectives
I. Perspectives d’approfondissement
I.1. Approfondissement sur la résolution d’une instance
I.2. Intégration de la résolution d’une instance dans le cadre du régulateur court terme
II. Bilan global de l’application de la méthode de génération de colonnes
II.1. Objectifs initiaux et résultats obtenus
II.2. Bilan global
Appendices
I. Bibliographie
I.1. Fonctionnement de l’ATFM et de la CFMU, recherches globales
I.2. Le Ground Holding Problem et ses extensions
I.3. Le TFMP et ses extensions
I.4. Problèmes de routage et de reroutement dynamique
I.5. Programmation linéaire et applications, génération de colonnes
I.6. Problèmes de plus courts chemins
I.7. Optimisation combinatoire: autres
I.8. Sites Internet
II. Annexes
II.1. Descriptions et démonstrations mathématiques
II.2. Lexique et acronymes

Télécharger le rapport complet