Airspace sectorization with constraints

Huy Trandac; Philippe Baptiste; Vu Duong

RAIRO - Operations Research - Recherche Opérationnelle (2005)

  • Volume: 39, Issue: 2, page 105-122
  • ISSN: 0399-0559

Abstract

top
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.

How to cite

top

Trandac, Huy, Baptiste, Philippe, and Duong, Vu. "Airspace sectorization with constraints." RAIRO - Operations Research - Recherche Opérationnelle 39.2 (2005): 105-122. <http://eudml.org/doc/244609>.

@article{Trandac2005,
abstract = {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.},
author = {Trandac, Huy, Baptiste, Philippe, Duong, Vu},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {airspace sectorization; constraint programming},
language = {eng},
number = {2},
pages = {105-122},
publisher = {EDP-Sciences},
title = {Airspace sectorization with constraints},
url = {http://eudml.org/doc/244609},
volume = {39},
year = {2005},
}

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
PB - EDP-Sciences
VL - 39
IS - 2
SP - 105
EP - 122
AB - 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.
LA - eng
KW - airspace sectorization; constraint programming
UR - http://eudml.org/doc/244609
ER -

References

top
  1. [1] S. Barbara, A tutorial on constraint programming. Technical Report 95.14, School of Computer Studies, University of Leeds (1995). 
  2. [2] S.T. Barnard and H.D. Simon, 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. [3] R. Bartak, Online guide to constraint programming, http://ktilinux.ms.mff.cuni.cz/~bartak/constraints/ (1998). 
  4. [4] Y. Caseau, F.X. Josset and F. Laburthe, 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). Zbl1105.68339
  5. [5] J. Chen, Computational geometry: Methods and applications. Department Computer Science, Texas A&M University (February 1996). 
  6. [6] A. Colmerauer, An introduction to PROLOG-III. Commun. ACM 33 (1990) 69–90. 
  7. [7] A. Colmerauer, Les bases de Prolog IV. Technical report, Laboratoire d’Informatique de Marseille (1996). 
  8. [8] D. Delahaye, 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. [9] D. Delahaye, J.M. Alliot, M. Schoenauer and J.L. Farges, 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. [10] D. Delahaye, M. Schoenauer and J.M. Alliot, Airspace sectoring by evolutionary computation, in IEEE International Congress on Evolutionary Computation (1998). 
  11. [11] C.M. Fiduccia and R.M. Mattheyses, A linear time heuristic for improving network partitions, in Proc. of 19th ACM/IEEE Design Automation Conference (1982) 175–181. 
  12. [12] P.O. Fjallstrom, Algorithms for graph partitioning: A survey. Linkoping Electronic Articles in Computer and Information Science 3 (1998). 
  13. [13] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman & Co. (1979). Zbl0411.68039MR519066
  14. [14] J.R. Gilbert, G.L. Miller and S.H. Teng, Geometric mesh partitioning: Implementation and experiments. SIAM J. Sci. Comput. 19 (1998) 2091–2110. Zbl0913.65107
  15. [15] D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley (1989). Zbl0721.68056
  16. [16] B. Hendrickson and R. Leland, An improved spectral graph partitioning algorithm for mapping parallel computations. SIAM J. Sci. Comput. 16 (1995) 452–469. Zbl0816.68093
  17. [17] B. Hendrickson and R. Leland, A multilevel algorithm for partitioning graphs, in Proc. of the 1995 ACM/IEEE Conference on Supercomputing, San Diego, California, USA, ACM Press (1995). Zbl0816.68093
  18. [18] G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20 (1998) 359–392. Zbl0915.68129
  19. [19] G. Karypis and V. Kumar, Multilevel k-way partitioning scheme for irregular graphs. Journal of Parallel and Distributed Computing 48 (1998) 96–129. Zbl0918.68073
  20. [20] B.W. Kernighan and S. Lin, An efficient heuristic procedure for partitionning graphs. BELL System Technical Journal (February 1970) 291–307. Zbl0333.05001
  21. [21] F. Laburthe, CHOCO – A Constraint Programming kernel for solving combinatorial optimization problems (2002). 
  22. [22] F. Laburthe 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. [23] S. Manuel, M.L. José, M.B. Victor and M.R. José, Genes: a genetic algorithms and fast time simulation, in 3rd ATM R&D Symposium, Spain (2002). 
  24. [24] A. Okabe et al., Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. New York, Wiley (1992). Zbl0877.52010MR1210959
  25. [25] J.-F. Puget, A C++ implementation of CLP, in Proc. of the Second Singapore International Conference on Intelligent Systems, Singapore (1994). 
  26. [26] R.E. Tarjan, Depth-first search and linear graph algorithms. SIAM J. Comput. 1 (1972) 146–160. Zbl0251.05107
  27. [27] M. Wallace, S. Novello and J. Schimpf, Eclipse: A platform for constraint logic programming. Technical report, IC-Parc, Imperial College, London (1997). 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.