Légende
: vol (3 possibilités d’affectation)
: possibilité d’affectation d’un
niveau à un vol
: niveau affecté à un vol
: conflit potentiel rejeté
: conflit potentiel retenu dans la
solution
Programmation et évaluation d’algorithmes d’affectation des niveaux de vol
0
100
200
300
400
500
600
700
800
Coût (en millions)
RFLMinRFLMinMaxRFLMinMaxRFL + recherche localeCoutConflitMaxMinMaxParamsAmeliorationImmediateAmeliorationSecondaireRecherche Tabou (étendu)Recherche Tabou (restreint)Recuit SimuléRecherche Génétique Hybride
INSTITUT NATIONAL DE RECHERCHE SUR LES TRANSPORTS ET LEUR SECURITE
Nicolas GADENNE
Problème de la gestion du trafic aérien
Partie 1 : Algorithmes d’optimisation des niveaux de vol
Partie 2 : Amélioration du logiciel Indicateurs
Complexité du problème réel :
● Problème NP-difficile
● 25000 sommets
● 2 millions d’arêtes
● 1012000 solutions
285
736
215
279
455
653
278
590
137
276
719
253
273
303
837
271
258
666
260
265
270
275
280
285
290
Coût (en millions)
Conclusion
Réseau aérien sur l’Europe :
● 1000 secteurs aériens
● 10000 balises
● 2700 aéroports
Trafic aérien sur l’Europe :
● environ 25000 vols par jour
● Croissance de 4% par an
Réseau des balises et des routes aériennes dans le sud-est de la France
Fenêtre principale du simulateur
L’objectif de l’équipe « trafic aérien » du laboratoire LICIT est de
prévoir, planifier, réguler, et simuler le trafic aérien pour permettre
l’accroissement de capacité de l’espace aérien.
● Simule une journée de trafic aérien sur l’Europe à
partir d’archives de plans de vol réels déposés à la
CFMU
● Permet de tester les méthodes de régulation et
d’optimisation mises au point au LICIT
Le simulateurOptimisation des niveaux de vol
Remarque:
● Problème NP-Difficile de grande
dimension : aucun moyen de connaître la
valeur de la solution optimale
Le logiciel Indicateurs sera utilisé pour :
● Détecter les problèmes dans le fonctionnement du simulateur
● Obtenir des données statistiques sur le trafic aérien en Europe
● Mesurer l’efficacité des méthodes d’optimisation
Apports techniques :
● Algorithmes d’optimisation
combinatoire
● Programmation C++
(particulièrement la librairie STL)
● VCL de C++ Builder
Fenêtre principale du logiciel Indicateurs
Fenêtre des statistiques globales
Ce logiciel extrait les
informations utiles des fichiers
de sortie du simulateur :
● Durée des vols
● Consommation de carburant
● Distance parcourue
● Niveau de vol
● etc...
Travail effectué :
● Reprise de l’ancienne version et amélioration
(structure du programme, interface)
● Ajout de nouvelles fonctionnalités (histogrammes
dynamiques, calcul des conflits, sauvegarde/chargement,
comparaison de deux solutions, etc)
● Vérification de la validité des indicateurs (données
affichées)
Performance des algorithmes
Algorithmes développés :
● Algorithmes gloutons
● Algorithmes arborescents
● Recherches locales par descente
● Méthode Tabou
● Recuit Simulé
● Partitionnement
● Algorithme génétique hybride
Apports personnels :
● Première expérience
professionnelle informatique
● Découverte du milieu de la
recherche
Stage effectué au LICIT (Laboratoire d’Ingénierie Circulation Transports), unité mixte INRETS / ENTPE (25 avenue François Mitterrand, 69675 BRON) par Nicolas Gadenne ([email protected]), sous la direction de Rémy Fondacci ([email protected]) et Sophie Constans ([email protected])
Modélisation du problème par un graphe
L’objectif est d’affecter à chaque vol survolant l’Europe pendant une
journée un niveau de croisière, de façon à minimiser le nombre de conflits
potentiels ; deux avions étant en conflit potentiel lorsque leurs trajectoires
prévues ne respectent pas les distances minimales de séparation.
Septembre 2004 - Février 2005