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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alliot, J.-M. and N. Durand. (1998). “Faces: A Free Flight Autonomous and Coordinated Embarked Solver.” In Proceedings of the Second Air Traffic Management R&D Seminar ATM-2000, Orlando, USA. Eurocontrol & FAA.
Barnier N. and P. Brisset. (2001). “FaCiLe: A Functional Constraint Library.” In Colloquium on Implementation of Constraint and LOgic Programming Systems CICLOPS'01 (Workshop of CP'01), Paphos, Cyprus, December.
Bessière, C. and J.-C. Régin. (1996). “MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems.” In Principles and Practice of Constraint Programming, pp. 61–75.
Bomze, I., M. Budinich, P. Pardalos, and M. Pelillo. (1999). “The Maximum Clique Problem.” In D.-Z. Du and P.M. Pardalos (eds.), Handbook of Combinatorial Optimization, Vol. 4. Boston, MA: Kluwer Academic.
Brélaz, D. (1979). “New Methods to Color the Vertices of a Graph.” Communications of the ACM 22, 251–256.
Brown, R.J. (1972). “Chromatic Scheduling and the Chromatic Number Problem.” Management Science 19, 451–463.
Caramia, M. and P. Dell'Olmo. (2002). “Constraint Propagation in Graph Coloring.” Journal of Heuristics 1(8), 83–108.
Christofides, N. (1971). “An Algorithm for the Chromatic Number of a Graph.” Computer Journal 14, 38–39.
Coudert. O. (1997). “Exact Coloring of Real-Life Graphs is Easy.” In Design Automation Conference DAC97, Anaheim, CA, June.
Culberson, J.C. (1992). “Iterated Greedy Graph Coloring and the Difficulty Landscape.” Technical Report TR 92-07, University of Alberta, Edmonton, Canada.
Dorne, R. and J.K. Hao. (1998). “Tabu Search for Graph Coloring, T-Colorings and Set T-Colorings.” In Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, chapter 3, pp. 77–92. Dordrecht: Kluwer Academic.
Fleurent, C. and J.A. Ferland. (1994). “Genetic and Hybrid Algorithm for Graph Coloring.” Technical Report, Université de Montréal.
Gawinowski, G. and L. Guichard. (2002). “Sectorless-1 Operational Concept Document 0.1.” Technical Report, Eurocontrol Experimental Centre.
Hertz, A. and D. de Werra. (1987). “Using Tabu Search Techniques for Graph Coloring.” Computing 39, 345–351.
Johnson, D.S. and M.A. Trick (eds.). (1996). Cliques, Coloring, and Satisfiability: Second DIMACS Imple-mentation Challenge, DIMACS Series on Discrete Mathematics and Theoretical Computer Science. Providence, RI: Amer. Math. Soc.
Kirovski, D. and M. Potkonjak. (1998). “Efficient Coloring of a Large Spectrum of Graphs.” In Design Automation Conference, pp. 427–432.
Leighton, F.T. (1979). “A Graph Colouring Algorithm for Large Scheduling Problems.” Journal of Research of the National Bureau of Standards 84(6), 489–503.
Letrouit, V. (1998). “Optimisation du réseau des routes aériennes en Europe.” Ph.D. Thesis, Institut National Polytechnique de Grenoble.
Maugis, L., J.-B. Gotteland, R. Zanni, and P. Kerlirzin. (1998). “TOSCA-II-WP3: Assessment of the TMA to TMA Hand-over Concept.” Technical Report TOSCA/SOF/WPR/3/03, SOFREAVIA.
Mehadhebi, K. (2000). “A Methodology for the Design of a Route Network.” In Proceedings of the Third Air Traffic Management R & D Seminar ATM-2000, Napoli, Italy, June. Eurocontrol & FAA.
Morgenstern, C. and H. Shapiro. (1986). “Chromatic Number Approximation Using Simulated Annealing.” In ACM Mountain Regional Meeting Proceedings.
Peemöller, J. (1983). “A Correction to Brélaz's Modification of Brown's Coloring Algorithm.” Communications of the ACM 26, 595–597.
Prestwich, S. (2001). “Local Search and Backtracking versus Non-systematic Backtracking.” In Papers from the AAAI 2001 Fall Symposium on Using Uncertainty within Computation, pp. 109–115. Cape Cod, MA: North Falmouth.
Smith, B.M. (1999) “The Brélaz Heuristic and Optimal Static Orderings.” Research Report 1999.13, School of Computer Studies, University of Leeds, June.
Smith, B.M. and S.A. Grant. (1995). “Where the Exceptionally Hard Problems Are.” Technical Report 95.35, University of Leeds.
The European Commission. (1999). Fifteen Countries, a Single European Sky. IP/99/924.
Trick, M. (1994). “Network Resources for Coloring a Graph.” mat.gsia.cmu.edu/COLOR/color. html
Van Hentenryck, P. (1990). “A Logic Language for Combinatorial Optimization.” Annals of Operations Research 21, 247–274.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Barnier, N., Brisset, P. Graph Coloring for Air Traffic Flow Management. Annals of Operations Research 130, 163–178 (2004). https://doi.org/10.1023/B:ANOR.0000032574.01332.98
Issue Date:
DOI: https://doi.org/10.1023/B:ANOR.0000032574.01332.98