HEATS-3D: Hybrid Evolutionary Algorithms for Trajectory Separation in 3 Dimensions

HEATS-3D homepage is also available in english.

Résumé

Acronyme: HEATS-3D
Nom du projet: Hybrid Evolutionary Algorithms for Trajectory Separation in 3 Dimensions
Date de début: 2001
Date de fin: -

Description

HEATS-3D a démarré en 2001 dans le cadre d'une thèse sur l'optimisation des flux de trafic aérien.

L'objectif est d'allouer des trajectoires 3D optimales, séparées les unes des autres, aux principaux flux origine-destination. Deux stratégies ont été explorées : une approche séquentielle et une approche globale.

La première méthode utilise un algorithme A* pour calculer les trajectoires en séquence, en évitant celles précédemment calculées, tout en minimisant un coût individuel lié aux déviations par rapport à une trajectoire idéale.
Dans l'approche globale, un algorithme évolutionnaire, hybridé avec un A*, permet d'optimiser un coût global associé à un ensemble de trajectoires, tout en respectant les contraintes de séparation entre trajectoires.

L'itinéraire entre origine et destination peut être choisi soit entre trois routes directes parallèles, soit parmi plusieurs itinéraires sur le réseau de routes standard. Plusieurs modes de détection d'interférences et plusieurs modèles d'allocation de trajectoires aux flux ont été développés, correspondant à divers degrés de réalisme. Les trois modes de détection d'interférences entre trajectoires sont les suivants :

détection selon un critère de distance entre trajectoires filaires, avec un seul type d'avion,
détection d'intersection de tubes définis autour de trajectoires filaires, toujours avec un seul type d'avion,
détection d'intersection de zones d'incertitudes, tenant compte de la disparité des types d'avions.

Pour ce qui concerne les différents modèles d'allocation, on pourra affecter :

une seule trajectoire par flux origine-destination,
une trajectoire principale, plus éventuellement des trajectoires supplémentaires pour les arrivées ou les départs d'aéroports proches de la frontière, dans le cas des flux entrant ou sortant de l'espace aérien,
plusieurs trajectoires par origine-destination, en fonction des niveaux demandés en entrée, en croisière, et en sortie. Une méthode des k-means permet dans ce cas de réaliser une classification préalable des vols en fonction des niveaux demandés.

Etat d'avancement

Les deux approches, globale et séquentielle, ont dans un premier temps été développées sur des cas-tests, avec une modélisation très simplifiée des trajectoires et de la détection d'interférences entre trajectoires.

Dans un deuxième temps, les algorithmes ont été adaptés aux données réelles de trafic français et européen, en tenant compte des performances des avions et de la disparité des types d'avions au sein d'un même flux.

Le concept de la séparation en 3D des flux de trafic a été validé, dans le contexte français uniquement, par des simulations avec CATS, en considérant un trafic de référence et un trafic où les avions des principaux flux évoluent sur le réseau de trajectoires 3D calculé par la méthode séquentielle ou globale. On comparera le nombre de conflits détectés dans les deux situations, en considérant que les avions suivant une même trajectoire 3D sont séquencés temporellement au départ .

Les simulations portent sur le trafic total d'une journée. Seule une certaine proportion de ce trafic peut être traité sur le réseau de trajectoires 3D séparées. Cette proportion est variable, en fonction du modèle d'allocation choisi, et du choix des principaux flux. Le tableau suivant donne une synthèse des résultats, avec en colonne de gauche la proportion de trafic géré sur le réseau de trajectoires séparées, et en colonne de droite la diminution du nombre de conflits détectés.

% trafic	Gain
30.00%	10 à 15 %
40.00%	20 à 30 %
50.00%	35 à 40 %

Cliquez ici pour voir la présentation, au 6th USA/Europe ATM 2005 R&D Seminar, de l'évaluation du concept de séparation des flux en 3D.

Les principales améliorations restant à réaliser portent sur l'application aux données Europe, avec tout d'abord la définition de flux entre TMA (zones terminales), et non entre aéroports. Par ailleurs, et uniquement dans le contexte du trafic européen, il semble possible de découper le problème global en sous-problèmes indépendants, ce qui permettrait de paralléliser l'algorithme évolutionnaire.

Exemple sur un cas-test

Voici une illustration d'un résultat de l'algorithme évolutionnaire sur une configuration de 10 flux, avec des points origine et destination situés sur un cercle, et des flux aller-retour.

Cette exemple montre à la fois des déviations latérales, pour les flux retour, et verticales au point de croisement au centre.

Exemple sur les données France

L'example porte sur des flux comportant au moins 20 avions dans la journée du 21 juin 2002, au-dessus de la France, pour les vols demandant une croisière au-dessus du niveau de vol FL145 (soit 14500 pieds au-dessus de l'isobare 1013,25 hPa).

Cette configuration de 71 trajectoires, avec une seule trajectoire par flux origine-destination représente 39,6% du trafic total.

Exemple sur les données Europe

Ici, c'est le modèle d'allocation avec plusieurs trajectoires par flux origine-destination qui est utilisé, pour les flux d'au moins 10 avions dans la journée du 21 juin 2002, au dessus de l'Europe.

Les 235 trajectoires représentent 12 % du trafic total, ce qui est proportionnelement beaucoup moins que pour le trafic français. Il serait plus profitable d'allouer des trajectoires à des flux entre TMA (zone terminales) de grande taille regroupant plusieurs aéroports, plutôt qu'entre aéroports. Ceci permettrait de traiter plus de trafic, mais nécessiterait d'organiser le trafic à l'intérieur des TMA.

Logiciel

HEATS-3D est écrit en Objective Caml. Le code n'est pas dans le domaine public.

Liens utiles

Centre d'Etudes de la Navigation Aérienne (maintenant Sous Direction des Etudes et de la Recherche)
Ocaml

Principales publications

Algorithme évolutionnaire et A* pour la séparation en 3D des flux de trafic aérien David Gianazza Journal Européen des Systèmes automatisés, volume 38 - n°9-10/2004, numéro spécial "Métaheuristiques pour l'optimisation difficile". (2005/10/05)
Assessment of the 3D-separation of Air Traffic Flows David Gianazza, Nicolas Durand 6th USA/Europe Seminar on Air Traffic Management Research and Development (2005/06/28)
Optimisation des flux de trafic aérien David Gianazza Thèse doctorat informatique de l'INPT (2004/11/02)
Separating air traffic flows by allocating 3D-trajectories. D. Gianazza, N. Durand 23d DASC (2004/10/24)
Allocating 3D trajectories to air traffic flows using A* and genetic algorithms D. Gianazza, N. Durand, N. Archambault CIMCA04 (2004/06/02)
Optimisation des flux de trafic aérien : allocation de niveaux de vols et définition de trajectoires 3D David Gianazza Colloque des doctorants de l'Ecole Doctorale Informatique et Télécommunications 2003 (2003/04/14)

Toutes les publications du LOG sont disponibles ici.

Last Update: Wednesday, 28-Mar-2007 10:40:10 UTC

WARNING: This web page is no longer maintained. See POM and LOTA
[LOG Home]
[The Lab] [Research topics] [Publications] [Software]
[Partnerships] [Addresses] [Gamezone]
Contact .