informИнформатикаInformatics1816-03012617-6963UIIP NASBinform-313Research ArticleМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕMATHEMATICAL MODELINGМОДЕЛИРОВАНИЕ ДВИЖЕНИЯ ОБЪЕКТОВ БЕЗ ОСТАНОВОК ПО СЕТИ ПЕРЕСЕКАЮЩИХСЯ МАРШРУТОВMODELING MOVEMENT OF OBJECTS WITHOUT STOPS IN A NETWORK OF CROSSING ROUTESРубановИ. В.RubanovI. V.

старший преподаватель кафедры естественнонаучных дисциплин

Senior Lecturer of the Department of Science Disciplines

irubanov@inbox.ruБаркетовМ. С.BarketauM. S.

кандидат физико-математических наук, старший научный сотрудник лаборатории математической кибернетики

Ph. D. (Physics and Mathematics), Senior Researcher of Mathematical Cybernetics Laboratory

barketau@mail.ruКовалевМ. Я.KovalyovM. Y.

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

D. Sc. (Physics and Mathematics), Professor, Corresponding member of the National Academy of Sciences of Belarus, Deputy General Director

kovalyov_my@newman.bas-net.byБелорусская государственная академия авиацииBelarusian State Academy of AviationОбъединенный институт проблем информатики Национальной академии наук Беларуси, МинскThe United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk2018260320181512133Copyright © Рубанов И.В., Баркетов М.С., Ковалев М.Я., 20182018Рубанов И.В., Баркетов М.С., Ковалев М.Я.Rubanov I.V., Barketau M.S., 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/313

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

Modeling of movement of objects without stops in a network of crossing routes is studied. The problem is formulated in terms of disjunctive linear programming, mixed integer linear programming and graph theory. Several variants for representing constraints on convergence of objects are considered. NP-completeness of the problem in the strong sense is proved.

маршрутизацияпостроение расписанийбезопасность полетовразностная логикавыполнимость формул в теорияхцелочисленное линейное программированиедизъюнктивное программированиеroutingschedulingflight safetydifference logicsatisfiability modulo theorieslinear programmingdisjunctive programmingReferencesКрыжановский, Г. А. Введение в прикладную теорию управления воздушным движением : учебник для вузов гражданской авиации / Г. А. Крыжановский. – М.: Машиностроение, 1984. – 368 с.Крыжановский, Г. А. Введение в прикладную теорию управления воздушным движением : учебник для вузов гражданской авиации / Г. А. Крыжановский. – М.: Машиностроение, 1984. – 368 с.Солодухин, В. А. Задачи оптимизации процессов планирования и управления потоками воздушного движения / В. А. Солодухин // Научный вестник МГТУ ГА. – 2009. – № 139. – С. 85–90.Солодухин, В. А. Задачи оптимизации процессов планирования и управления потоками воздушного движения / В. А. Солодухин // Научный вестник МГТУ ГА. – 2009. – № 139. – С. 85–90.Безряков, В. В. Прямые и обратные задачи оптимизации управления потоками воздушного движения в районе аэродрома / В. В. Безряков, Г. А. Крыжановский, В. А. Солодухин // Научный вестник МГТУ ГА. – 2011. – № 171. – С. 109–113.Безряков, В. В. Прямые и обратные задачи оптимизации управления потоками воздушного движения в районе аэродрома / В. В. Безряков, Г. А. Крыжановский, В. А. Солодухин // Научный вестник МГТУ ГА. – 2011. – № 171. – С. 109–113.Dell’Olmo, P. A new hierarchical architecture for Air Traffic Management: Optimisation of airway capacity in a Free Flight scenario / P. Dell’Olmo, G. Lulli // European Journal of Operational Research. – 2003. – Vol. 144. – P. 179–193.Dell’Olmo, P. A new hierarchical architecture for Air Traffic Management: Optimisation of airway capacity in a Free Flight scenario / P. Dell’Olmo, G. Lulli // European Journal of Operational Research. – 2003. – Vol. 144. – P. 179–193.Рубанов, И. В. Задача выбора маршрутов движения объектов при ограничении на сближение / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск: ОИПИ НАН Беларуси, 2014. – С. 136–140.Рубанов, И. В. Задача выбора маршрутов движения объектов при ограничении на сближение / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск: ОИПИ НАН Беларуси, 2014. – С. 136–140.Рубанов, И. В. Малозатратные методы решения системы разностных и интервальных ограничений / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Седьмой Междунар. науч. конф., Минск, 28–29 марта 2016 г. – Минск: ОИПИ НАН Беларуси, 2016. – С. 170–174.Рубанов, И. В. Малозатратные методы решения системы разностных и интервальных ограничений / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Седьмой Междунар. науч. конф., Минск, 28–29 марта 2016 г. – Минск: ОИПИ НАН Беларуси, 2016. – С. 170–174.Рубанов, И. В. Подходы к решению дизъюнктивной системы разностных и интервальных ограничений / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Седьмой Междунар. науч. конф., Минск, 28–29 марта 2016 г. – Минск: ОИПИ НАН Беларуси, 2016. – С. 175–180.Рубанов, И. В. Подходы к решению дизъюнктивной системы разностных и интервальных ограничений / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Седьмой Междунар. науч. конф., Минск, 28–29 марта 2016 г. – Минск: ОИПИ НАН Беларуси, 2016. – С. 175–180.Рубанов, И. В. Методы поиска нескольких решений системы разностных и интервальных ограничений / И. В. Рубанов, М.С. Баркетов, М. Я. Ковалев // Информатика. – 2016. – № 3(51). – С. 67–79.Рубанов, И. В. Методы поиска нескольких решений системы разностных и интервальных ограничений / И. В. Рубанов, М.С. Баркетов, М. Я. Ковалев // Информатика. – 2016. – № 3(51). – С. 67–79.Кранц, П. Сферическая тригонометрия : пер. с нем. / П. Кранц ; под ред. Я.В. Шпильрейна. – 2-е. изд. – М.: Изд-во ЛКИ, 2007. – 96 с.Кранц, П. Сферическая тригонометрия : пер. с нем. / П. Кранц ; под ред. Я.В. Шпильрейна. – 2-е. изд. – М.: Изд-во ЛКИ, 2007. – 96 с.Кузнецов, С. В. Прикладные задачи обоснования минимальных интервалов эшелонирования воздушных судов с использованием системы наблюдения ОВД в соответствии с отечественными и международными правилами / С. В. Кузнецов, В. Б. Спрысков // Научный вестник ГосНИИ «Аэронавигация» : сб. науч. тр. – М., 2012. – № 11 : Организация воздушного движения. Использование воздушного пространства. Безопасность полетов. – С. 47–63.Кузнецов, С. В. Прикладные задачи обоснования минимальных интервалов эшелонирования воздушных судов с использованием системы наблюдения ОВД в соответствии с отечественными и международными правилами / С. В. Кузнецов, В. Б. Спрысков // Научный вестник ГосНИИ «Аэронавигация» : сб. науч. тр. – М., 2012. – № 11 : Организация воздушного движения. Использование воздушного пространства. Безопасность полетов. – С. 47–63.Netjasov, F. Framework for airspace planning and design based on conflict risk assessment. Part 2 : Conflict risk assessment model for airspace tactical planning / F. Netjasov // Transportation Research Part C. – 2012. – No. 24. – P. 213–226.Netjasov, F. Framework for airspace planning and design based on conflict risk assessment. Part 2 : Conflict risk assessment model for airspace tactical planning / F. Netjasov // Transportation Research Part C. – 2012. – No. 24. – P. 213–226.Systemic identification of airspace collision risk tipping points using an evolutionary multi-objective scenario-based methodology / S. Alam [et al.] // Transportation Research Part C. – 2013. – No. 35. – P. 57–84.Systemic identification of airspace collision risk tipping points using an evolutionary multi-objective scenario-based methodology / S. Alam [et al.] // Transportation Research Part C. – 2013. – No. 35. – P. 57–84.Сотсков, Ю. Н. Построение расписания, допустимого относительно смешанного мультиграфа / Ю. Н. Сотсков, В. С. Танаев // Вес. Акад. наук БССР. Сер. физ.-мат. наук. – 1989. – № 4. – С. 94–98.Сотсков, Ю. Н. Построение расписания, допустимого относительно смешанного мультиграфа / Ю. Н. Сотсков, В. С. Танаев // Вес. Акад. наук БССР. Сер. физ.-мат. наук. – 1989. – № 4. – С. 94–98.Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France, 2006. – 15 p.Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France, 2006. – 15 p.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.

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