Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

Graph coloring for Air Traffic Flow Management

Nicolas Barnier 1 Pascal Brisset 2 
MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien
Abstract : The aim of Air Traffic Flow Management (ATFM) is to enhance the capacity of the airspace while satisfying Air Traffic Control constraints and airlines requests to optimize their operating costs. This paper presents a design of a new route network that tries to optimize these criteria. The basic idea is to consider direct routes only and to vertically separate intersecting flows of aircrafts by allocating distinct flight levels. This problem is a graph coloring problem that we tackle using Constraint Programming and a greedy algorithm to find cliques of the constraint graph which are used to post global constraints. Through the search for optimal solutions minimizing the number of distinct flight levels allocated, symmetries among equivalent flight levels are dynamically broken, and the variable ordering is guided by the cliques found in the first static step. With an implementation using FaCiLe, our Functional Constraint Library, optimality is achieved for all flow sizes except the smallest one, while the corresponding number of flight levels could fit in the current airspace structure. However, many other constraints should be added to this very simplified model to obtain an operational route network, such that the conclusion is rather the validation of the concept of vertical separation of large flows. This graph coloring technique has also been tested on various benchmarks, featuring good results on real-life instances, which systematically appear to contain large cliques.
Type de document :
Communication dans un congrès
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : jeudi 17 avril 2014 - 16:04:38
Dernière modification le : mardi 19 octobre 2021 - 11:02:56
Archivage à long terme le : : dimanche 9 avril 2017 - 02:21:01


Fichiers éditeurs autorisés sur une archive ouverte




Nicolas Barnier, Pascal Brisset. Graph coloring for Air Traffic Flow Management. CP-AI-OR 2002, 4th Fourth International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimisation Problems, Mar 2002, Le Croisic, France. pp 163-178, ⟨10.1023/B:ANOR.0000032574.01332.98⟩. ⟨hal-00938022⟩



Consultations de la notice


Téléchargements de fichiers