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.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Graph Coloring for Air Traffic Flow Management


    Contributors:

    Published in:

    Publication date :

    2004-08-01


    Size :

    16 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English




    Air Traffic Deconfliction Using Sum Coloring

    Duchamp, Vincent / Josefsson, Billy / Polishchuk, Tatiana et al. | IEEE | 2019


    A Graph b-coloring Framework for Data Clustering

    Elghazel, H. / Kheddouci, H. / Deslandres, V. r. et al. | British Library Online Contents | 2008


    Improved Real Time Ride Sharing via Graph Coloring

    Jain, Saatvik / Biyani, Pravesh | IEEE | 2019


    Field-Programmable Gate-Array-Based Graph Coloring Accelerator

    L. M. Pochet / M. L. Linderman / S. L. Drager et al. | AIAA | 2002


    Consecutive Graph Coloring for School Timetabling (full paper)

    Giaro, K. / Kubale, M. / Szyfelbein, D. | British Library Conference Proceedings | 2000