informИнформатикаInformatics1816-03012617-6963UIIP NASB10.37661/1816-0301-2020-17-4-7-21inform-884Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGВычислительные методы для решения задачи комбинирования секторов воздушного пространстваComputational methods for airspace sectorisationРубановИ. ВRubanovI. V.

Рубанов Игорь Владимирович, старший преподаватель кафедры естественнонаучных дисциплин

Минск

 

Igor V. Rubanov, Senior Lecturer of the Department of Science Disciplines

Minsk

irubanov@inbox.ruКовалевМ. ЯKovalyovM. Y.

Ковалев Михаил Яковлевич, доктор физико-математических наук, профессор, член-корреспондент НАН Беларуси, заместитель генерального директора

Минск

Mikhail Y. Kovalyov, Dr. Sci. (Phys.-Math.), Professor, Corresponding Member of the National Academy of Sciences of Belarus, Deputy General Director

Minsk

 

kovalyov_my@newman.bas-net.byБелорусская государственная академия авиацииBelarusian State Academy of AviationОбъединенный институт проблем информатики Национальной академии наук БеларусиThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus202002112020174721Copyright © Рубанов И.В., Ковалев М.Я., 20212021Рубанов И.В., Ковалев М.Я.Rubanov I.V., Kovalyov M.Y.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://inf.grid.by/jour/article/view/884

Рассматривается задача комбинирования секторов региона воздушного пространства, при которой должно быть получено минимальное количество секторов при ограничении на их нагрузку. Предлагаются вычислительные методы, которые могут быть применены в более общих моделях решения задачи. Предлагается алгоритм построения разбиений конечного множества, а также формулировка задачи целочисленного линейного программирования, используется также терминология теории графов.

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.

секторизация воздушного пространствабезопасность полетовразбиение конечного множествацелочисленное линейное программированиеметод ветвей и границairspace sectorizationflight safetyfinite set partitioninginteger linear programmingbranch and bound methodReferencesFlener, P. Automatic Airspace Sectorisation: A Survey [Electronic resource] / P. Flener, J. Pearson. – Department of Information Technology, Uppsala University, Sweden, 2018. – Mode of access: https://arxiv.org/abs/1311.0653. – Date of access: 03.06.2020.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).Applying graph theory to problems in air traffic management / A. H. Farrahi [et al.] // 17th AIAA AVIATION Technology, Integration, and Operations Conference, Denver, Colorado, 5–9 June 2017 / AIAA AVIATION Forum. – Denver, Colorado, 2017. – 20 р.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-3775Bloom, M. Combining airspace sectors for the efficient use of air traffic control resources / M. Bloom, P. Kopardckar // Navigation, and Control (GNC) Conference and Exhibit, Honolulu, HI, 18–21 Aug. 2008. – American Institute of Aeronautics and Astronautics, 2008. – 15 р.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 р.Gianazza, D. Forecasting workload and airspace configuration with neural networks and tree search methods / D. Gianazza // Artificial Intelligence. – 2010. – № 174(7–8). – P. 530–549.Gianazza D. Forecasting workload and airspace configuration with neural networks and tree search methods. Artificial Intelligence, 2010, no. 174(7–8), pp. 530–549.Дегтярев, О. В. Решение задач секторизации района управления воздушным движением. I. Основные принципы и проблемы секторизации воздушного пространства и ее формализация как оптимизационной задачи / О. В. Дегтярев, В. Н. Минаенко, М. О. Орехов // Известия РАН. Теория и системы управления. – 2009. – № 3. – С. 56–72.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.Дегтярев, О. В. Решение задач секторизации района управления воздушным движением. II. Разработка алгоритмов секторизации / О. В. Дегтярев, В. Н. Минаенко, М. О. Орехов // Известия РАН. Теория и системы управления. – 2010. – № 4. – С. 117–135.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.Вересов, К. А. Решение задач секторизации района управления воздушным движением. III. Разработка алгоритмов определения конфигураций и временного графика работы секторов управления / К. А. Вересов, О. В. Дегтярев, В. Н. Минаенко // Известия РАН. Теория и системы управления. – 2013. – № 2. – С. 133–153.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.Bloom, M. Algorithms for combining airspace sectors / M. Bloem, P. Gupta, P. Kopardekar // Air Traffic Control Quarterly. – Sept. 2009. – Vol. 17, no. 3.Bloom M., Gupta P., Kopardekar P. Algorithms for combining airspace sectors. Air Traffic Control Quarterly, September 2009, vol. 17, no. 3.Drew, M. C. A method of optimally combining sectors / M. C. Drew // 9th AIAA Aviation Technology, Integration, and Operations Conference (ATIO), Hilton Head, South Carolina, 21–23 Sept. 2009. – American Institute of Aeronautics and Astronautics, 2009. – P. 7057.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.Martello, S. An Knapsack Problems. Algorithms and Computer Implementations / S. Martello, P. Toth. – John Wiley & Sons, 1990. – 296 p.Martello S., Toth P. An Knapsack Problems. Algorithms and Computer Implementations. John Wiley & Sons, 1990, 296 p.Стенли, Р. Перечислительная комбинаторика : в 2 т. / Р. Стенли. – М. : Мир, 1990. – Т. 1. – 440 с.Stanley R. Enumerative Combinatorics. Vol. 1. Cambridge University Press, 2012, 440 p.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М. : Мир, 1982. – 416 с.Garey M., Johnson D. Computers and Intractability. New York, W. H. Freeman and Company, 1979, 340 p.

The authors declare that there are no conflicts of interest present.