Automated Airspace Sectorization by Genetic Algorithm

Avec la croissance continue du trafic aérien et la limitation des ressources, il est nécessaire de réduire la congestion de l'espace aérien. Ces dernières années, un intérêt particulier a été porté au problème de la sectorisation de l'espace aérien.Pour pallier à cette augmentation continue du trafic en Europe, il est nécessaire d'optimiser la gestion du trafic aérien. Une automatisation de la sectorisation de l'espace aérien peut permettre, dans cette optique, d'accroître l'adaptabilité des configurations du secteur aérien à une nouvelle demande de trafic. L'objectif de la première partie de cette thèse est de proposer une méthode globale de sectorisation de l'espace aérien européen en se basant sur une modélisation mathématique et des méthodes d'optimisation heuristiques. La méthode de sectorisation proposée est basée sur la division initiale de l'espace aérien en cellules de Voronoi à l'aide de méthodes des k-moyennes. Pour des raisons de complexité combinatoire induite, un algorithme d'optimisation stochastique est utilisé pour résoudre le problème de sectorisation. Un algorithme génétique est utilisé pour construire les secteurs de l'espace aérien dans plusieurs zones de contrôle européennes, en se basant sur des données réelles de trafic aérien pendant plusieurs jours.De plus, les configurations du secteur de l'espace aérien doivent être adaptées dynamiquement pour offrir une efficacité et une flexibilité maximales en fonction des conditions météorologiques et de circulation. L'objectif de la deuxième partie de cette thèse est d'adapter automatiquement les configurations de l'espace aérien en fonction de l'évolution du trafic, au cours d'une journée de fonctionnement. Pour atteindre cet objectif, il faut considérer que l'espace aérien est divisé en blocs d'espaces aériens 3D qui doivent être groupés ou dégroupés en fonction de l'état du trafic. La méthode proposée est basée sur une technique de partitionnement de graphe et sur des algorithmes génétiques. La méthode est testée sur plusieurs zones de contrôle européennes.With the continuous air traffic growth and limits of resources, there is a need for reducing the congestion of the airspace systems. Nowadays, several projects are launched, aimed at modernizing the global air transportation system and air traffic management. In recent years, special interest has been paid to the solution of the airspace sectorization problem. This thesis is devoted to studying the airspace sectorization in Europe and the possibilities to improve it.The airspace sectorization needs to be optimized with the support of automation in order to increase an adaptability of airspace sector configurations to the new traffic demands. The aim of the first part of this thesis is to propose a global method for the sector design of the European airspace based on a mathematical modeling and heuristic optimization methods. The proposed resolution method to solve the sector design problem is based on the initial division of the airspace into Voronoi cells using k-means clustering algorithm. Then, due to the induced combinatorial complexity, a stochastic optimization method is applied to solve the sector design problem. Resolution method based on metaheuristic algorithm called Genetic Algorithm (GA) has been developed to build airspace sectors in several control areas of Europe, involving traffic data for several days. Furthermore, airspace sector configurations need to be dynamically adjusted to provide maximum efficiency and flexibility in response to changing weather/traffic conditions. The objective of the second part of this thesis is to automatically adapt the airspace configurations according to the evolution of traffic. In order to reach this objective, the airspace is considered to be divided into predefined 3D airspace blocks which have to be grouped or ungrouped depending on the traffic situation. The resolution method based on the graph partitioning technique and on the metaheuristic algorithm (GA) has been developed to generate a sequence of sector configurations, composed of the predefined airspace blocks. The overall methodology, is implemented and tested with air traffic data taken for one day of operation and for several different airspace control areas of Europe