[Home bibliotech]
Home > Les thèses en ligne de l'INP

Optimisation de graphes sous contrainte géométrique : création d'un réseau de routes aériennes pour un contrôle Sector-Less

Rivière, Thomas (2006) Optimisation de graphes sous contrainte géométrique : création d'un réseau de routes aériennes pour un contrôle Sector-Less. (Graph optimisation under geometric constraint : generating an air route network for the Sector-Less concept.)

Full text available as:

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
2.3 Mo

Prix Léopold Escande 2006 (more)

Abstract

Alors que le système de gestion du trafic aérien arrive à saturation, de nouveauxconcepts sont étudiés afin de trouver une alternative. Cette thèse s'applique à vérifier la validité d'un de ces nouveaux concepts, le concept Sector-Less qui envisage un contrôle des aéronefs par flux, c'est-à-dire depuis leur aéroport de départ jusqu'à leur aéroport d'arrivée, par opposition au contrôle actuel effectué par zone géographique. La validation est faite à travers la construction et la validation d'un réseau de routes aériennes adapté à ce concept. La définition de ce nouveau réseau est donnée uniquement en fonction des contraintes imposées par le concept Sector-Less, sans utiliser de base préexistante. Ce réseau initial de routes est optimisé par deux méta-heuristiques différentes, recuit simulé et algorithme génétique. Le processus d'optimisation vise à minimiser la longueur de la trajectoire pour chaque flux d'aéronefs. Il intègre en particulier des algorithmes dynamiques de calcul des plus courts chemins dans un graphe. Pour prendre en compte les capacités de navigation des aéronefs, deux techniques ont été utilisées pour intégrer au processus d'optimisation des contraintes géométriques. La première technique consiste à exprimer les contraintes géométriques directement à travers la structure du graphe et à utiliser les algorithmes classiques pour calculer les plus courts chemins. La seconde est basée sur un nouvel algorithme permettant, sans altérer le graphe, de calculer une approximation des plus courts chemins. Le réseau de routes ainsi construit est testé du point de vue gestion du trafic aérien en simulant, à l'aide d'un simulateur de trafic en temps discret, le trafic dans l'espace aérien européen sur une journée complète. L'évaluation estime en particulier la charge de travail des contrôleurs aériens. L'analyse des résultats montre que le concept Sector-Less, tel qu'il est actuellement proposé, ne peut pas ˆetre mis en oeuvre. ABSTRACT : Taking into consideration the fact that the current air traffic management system is becoming saturated, new concepts are being developed in order to find an alternative. The aim of this thesis is to verify the validity of one of these new concepts, the Sector-Less concept, which envisages the control of aircraft from their departure to their destination as opposed to the current control which is done geographically. The process of validation is performed by constructing and validating an air route network adapted to this concept. The definition of this new network is designed from scratch, according to constraints imposed by the Sector-Less concept, without using any preexisting network. This initial route network is optimised using two different meta-heuristic, a simulated annealing algorithm and a genetic algorithm. The optimisation process tends to minimise the length of the trajectory of each flow. It integrates a graph dynamic shortest paths algorithm. Taking into account the aircraft navigation capacities, two techniques have been used in order to integrate geometric constraints with the optimisation process. The first technique consists of expressing geometric constraints directly through the graph structure and to use classic dynamic shortest paths algorithms. The second one is based on a new algorithm allowing, without altering the graph, to calculate an approximation of the shortest path. The route network constructed in this way is tested from an air traffic management point of view in simulating, using a discreet time air traffic simulator, European air trafic in the course of one day. The evaluation estimates in particular the workload of the air traffic controllers. The analysis of the results show that the Sector-Less concept, as it is currently proposed, cannot be put into effect.

Department or laboratory:Laboratoire d'Optimisation Globale (Toulouse, France)
Directeur de thèse:Noailles, Joseph
Uncontrolled Keywords:Recuit simulé – Invariants – Réseau de routes aériennes – Algorithme génétique – Plus courts chemins – Sector-Less
Subjects:Computer science > Computer programming and systems
Deposited On:15 September 2006

Archive Staff Only: edit this record


Contacts | Infos légales | Plan du site | Intranet

(c)INP de Toulouse 2012 - Tous droits réservés. -  INP Communication