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

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.