Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download
Contributor : Laurence Porte <>
Submitted on : Thursday, April 17, 2014 - 4:04:38 PM
Last modification on : Tuesday, October 20, 2020 - 10:32:07 AM
Long-term archiving on: : Sunday, April 9, 2017 - 2:21:01 AM


Publisher files allowed on an open archive




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⟩



Record views


Files downloads