Graph Coloring for Air Traffic Flow Management

Nicolas Barnier () and Pascal Brisset ()

Annals of Operations Research, 2004, vol. 130, issue 1, 163-178

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 vertically separate intersecting ones by allocating distinct flight levels, thus leading to a graph coloring problem. This problem is solved using constraint programming after having found large cliques with a greedy algorithm. These cliques are used to post global constraints and guide the search strategy. With an implementation using FaCiLe, our Functional Constraint Library, optimality is achieved for all instances except the largest one, while the corresponding number of flight levels could fit in the current airspace structure. 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. Copyright Kluwer Academic Publishers 2004

Keywords: air traffic flow management; route network; graph coloring; cliques; greedy algorithm; constraint programming (search for similar items in EconPapers)
Date: 2004
References: Add references at CitEc
Citations: View citations in EconPapers (10)

Downloads: (external link)
http://hdl.handle.net/10.1023/B:ANOR.0000032574.01332.98 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:130:y:2004:i:1:p:163-178:10.1023/b:anor.0000032574.01332.98

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/B:ANOR.0000032574.01332.98

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().