We consider the Airspace Sectorization Problem (ASP) in which airspace has to be partitioned into a given number of sectors, each of which being assigned to a team of air traffic controllers. The objective is to minimize the coordination workload between adjacent sectors while balancing the total workload of controllers. Many specific constraints, including both geometrical and aircraft related constraints are taken into account. The problem is solved in a constraint programming framework. Experimental results show that our approach can be used on real life problems.
@article{RO_2005__39_2_105_0,
author = {Trandac, Huy and Baptiste, Philippe and Duong, Vu},
title = {Airspace sectorization with constraints},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {105--122},
publisher = {EDP-Sciences},
volume = {39},
number = {2},
year = {2005},
doi = {10.1051/ro:2005005},
mrnumber = {2181794},
zbl = {1121.90394},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2005005/}
}
TY - JOUR AU - Trandac, Huy AU - Baptiste, Philippe AU - Duong, Vu TI - Airspace sectorization with constraints JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2005 SP - 105 EP - 122 VL - 39 IS - 2 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2005005/ DO - 10.1051/ro:2005005 LA - en ID - RO_2005__39_2_105_0 ER -
%0 Journal Article %A Trandac, Huy %A Baptiste, Philippe %A Duong, Vu %T Airspace sectorization with constraints %J RAIRO - Operations Research - Recherche Opérationnelle %D 2005 %P 105-122 %V 39 %N 2 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2005005/ %R 10.1051/ro:2005005 %G en %F RO_2005__39_2_105_0
Trandac, Huy; Baptiste, Philippe; Duong, Vu. Airspace sectorization with constraints. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 2, pp. 105-122. doi : 10.1051/ro:2005005. http://www.numdam.org/articles/10.1051/ro:2005005/
[1] , A tutorial on constraint programming. Technical Report 95.14, School of Computer Studies, University of Leeds (1995).
[2] and, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, in Proc. of The sixth SIAM conference on Parallel Processing for Scientific Computing (1993) 711-718.
[3] , Online guide to constraint programming, http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/ (1998).
[4] , and, CLAIRE: Combining sets, search and rules to better express algorithms, in Proc. of the 16th International Conference on Logic Programming, Las Cruces, New Mexico - USA, Nov.-Dec. (1999).
[5] , Computational geometry: Methods and applications. Department Computer Science, Texas A&M University (February 1996).
[6] , An introduction to PROLOG-III. Commun. ACM 33 (1990) 69-90.
[7] , Les bases de Prolog IV. Technical report, Laboratoire d'Informatique de Marseille (1996).
[8] , Optimisation de la sectorisation de l'espace aérien par algorithmes génétiques. Ph.D. Thesis, École Nationale Supérieure de l'Aéronautique et de l'Espace (1995).
[9] ,, and, Genetic algorithms for automatic regrouping of air traffic control sectors, in Proc. of the Fourth International Conference on Evolutionary Programming, MIT Press (March 1995) 657-672.
[10] , and, Airspace sectoring by evolutionary computation, in IEEE International Congress on Evolutionary Computation (1998).
[11] and, A linear time heuristic for improving network partitions, in Proc. of 19th ACM/IEEE Design Automation Conference (1982) 175-181.
[12] , Algorithms for graph partitioning: A survey. Linkoping Electronic Articles in Computer and Information Science 3 (1998).
[13] and, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co. (1979). | MR | Zbl
[14] , and, Geometric mesh partitioning: Implementation and experiments. SIAM J. Sci. Comput. 19 (1998) 2091-2110. | Zbl
[15] , Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley (1989). | Zbl
[16] and, An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16 (1995) 452-469. | Zbl
[17] and, A multilevel algorithm for partitioning graphs, in Proc. of the 1995 ACM/IEEE Conference on Supercomputing, San Diego, California, USA, ACM Press (1995).
[18] and, A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20 (1998) 359-392. | Zbl
[19] and, Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing 48 (1998) 96-129.
[20] and, An efficient heuristic procedure for partitionning graphs. BELL System Technical Journal (February 1970) 291-307. | Zbl
[21] , CHOCO - A Constraint Programming kernel for solving combinatorial optimization problems (2002).
[22] and the OCRE group, CHOCO: Implementing a CP kernel, in CP00 Post Conference Workshop on Techniques for Implementing Constraint programming Systems (TRICS), Singapore (2000).
[23] ,, and, Genes: a genetic algorithms and fast time simulation, in 3rd ATM R&D Symposium, Spain (2002).
[24] et al., Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. New York, Wiley (1992). | MR | Zbl
[25] , A C++ implementation of CLP, in Proc. of the Second Singapore International Conference on Intelligent Systems, Singapore (1994).
[26] , Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972) 146-160. | Zbl
[27] , and, Eclipse: A platform for constraint logic programming. Technical report, IC-Parc, Imperial College, London (1997).
Cité par Sources :
