Computational methods for airspace sectorisation
https://doi.org/10.37661/1816-0301-2020-17-4-7-21
Abstract
A problem of combining elementary sectors of an airspace region is considered, in which a minimum number of combined sectors must be obtained with restrictions on their load and feasibility of combinations such as the requirement of the space connectivity or the membership of a given set of permissible combinations. Computational methods are proposed and tested to be used for solution of general problems of airspace sectorization. In particular, two types of combinatorial algorithms are proposed for constructing partitions of a finite set with specified element weights and graph-theoretical relationships between the elements. Partitions are constructed by use of a branch and bound method to minimize the number of subsets in the final partition, while limiting the total weight of elements in the subset. In the first type algorithm, ready-made components of the final partition are formed in each node of the branch and bound tree. The remaining part of the original set is further divided at the lower nodes. In the second type algorithm, the entire current partition is formed in each node, the components of which are supplemented at the lower nodes. When comparing algorithms performance, the problems are divided into two groups, one of which contains a connectivity requirement, and the other does not. Several integer programming formulations are also presented. Computational complexity of two problem variants is established: a bin packing type problem with restrictions on feasible combinations, and covering type problem.
About the Authors
I. V. Rubanov
Belarusian State Academy of Aviation
Belarus
Belarus
Igor V. Rubanov, Senior Lecturer of the Department of Science Disciplines
Minsk
M. Y. Kovalyov
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus
Belarus
Belarus
Mikhail Y. Kovalyov, Dr. Sci. (Phys.-Math.), Professor, Corresponding Member of the National Academy of Sciences of Belarus, Deputy General Director
Minsk
References
1. Flener P., Pearson J. Automatic Airspace Sectorisation: A Survey. Department of Information Technology, Uppsala University, Sweden, 2018. Available at: https://arxiv.org/abs/1311.0653 (accessed 03.06.2020).
2. Farrahi A. H., Goldberg A. T., Bagasol L. N., Jaewoo J. Applying graph theory to problems in air traffic management. 17th AIAA AVIATION Technology, Integration, and Operations Conference, Denver, Colorado, 5–9 June 2017, AIAA AVIATION Forum. Denver, Colorado, 2017, 20 р. https://doi.org/10.2514/6.2017-3775
3. Bloom M., Kopardckar P. Combining airspace sectors for the efficient use of air traffic control resources. Navigation, and Control (GNC) Conference and Exhibit, Honolulu, HI, 18–21 August 2008. American Institute of Aeronautics and Astronautics, 2008, 15 р.
4. Gianazza D. Forecasting workload and airspace configuration with neural networks and tree search methods. Artificial Intelligence, 2010, no. 174(7–8), pp. 530–549.
5. Degtyarev O. V., Minaenko V. N., Orekhov M. O. Reshenie zadach sektorizacii rajona upravlenija vozdushnym dvizheniem [Reservation of regional sector regulations]. I. Osnovnye principy i problemy sektorizacii vozdushnogo prostranstva i ee formalizacija kak optimizacionnoj zadachi [Basic principles and problems of airspace sectorization and its formalization as an optimization problem]. Izvestija Rossijskoj akademii nauk. Teorija i sistemy upravlenija [Bulletin of the Russian Academy of Sciences. Control Theory and Systems], 2009, no. 3, рр. 56–72.
6. Degtyarev O. V., Minaenko V. N., Orekhov M. O. Reshenie zadach sektorizacii rajona upravlenija vozdushnym dvizheniem [Solving the Problems of Sectorization of the Air Traffic Control Area]. II. Razrabotka algoritmov sektorizacii [Development of sectorization algorithms]. Izvestija Rossijskoj akademii nauk. Teorija i sistemy upravlenija [Bulletin of the Russian Academy of Sciences. Control Theory and Systems], 2010, no. 4, рр. 117–135.
7. Veresov K. A., Degtyarev O. V., Minaenko V. N. Reshenie zadach sektorizacii rajona upravlenija vozdushnym dvizheniem [Solving the problems of sectorization of the air traffic control area]. III. Razrabotka algoritmov opredelenija konfiguracij i vremennogo grafika raboty sektorov upravlenija [Development of algorithms for determining configurations and a time schedule for the operation of control sectors]. Izvestija Rossijskoj akademii nauk. Teorija i sistemy upravlenija [Bulletin of the Russian Academy of Sciences. Control Theory and Systems], 2013, no. 2, рр. 133–153.
8. Bloom M., Gupta P., Kopardekar P. Algorithms for combining airspace sectors. Air Traffic Control Quarterly, September 2009, vol. 17, no. 3.
9. Drew M. C. A method of optimally combining sectors. 9th AIAA Aviation Technology, Integration, and Operations Conference (ATIO), Hilton Head, South Carolina, 21–23 September 2009. American Institute of Aeronautics and Astronautics, 2009, р. 7057.
10. Martello S., Toth P. An Knapsack Problems. Algorithms and Computer Implementations. John Wiley & Sons, 1990, 296 p.
11. Stanley R. Enumerative Combinatorics. Vol. 1. Cambridge University Press, 2012, 440 p.
12. Garey M., Johnson D. Computers and Intractability. New York, W. H. Freeman and Company, 1979, 340 p.
Review
For citations:
Rubanov I.V., Kovalyov M.Y. Computational methods for airspace sectorisation. Informatics. 2020;17(4):7-21. (In Russ.) https://doi.org/10.37661/1816-0301-2020-17-4-7-21
Views: 644
Email this article 