MODELING MOVEMENT OF OBJECTS WITHOUT STOPS IN A NETWORK OF CROSSING ROUTES
Abstract
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.
About the Authors
I. V. Rubanov
Belarusian State Academy of Aviation
Belarus
Senior Lecturer of the Department of Science Disciplines
Belarus
Senior Lecturer of the Department of Science Disciplines
M. S. Barketau
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk
Belarus
Ph. D. (Physics and Mathematics), Senior Researcher of Mathematical Cybernetics Laboratory
Belarus
Ph. D. (Physics and Mathematics), Senior Researcher of Mathematical Cybernetics Laboratory
M. Y. Kovalyov
The United Institute of Informatics Problems of the National Academy of Sciences of Belarus, Minsk
Belarus
D. Sc. (Physics and Mathematics), Professor, Corresponding member of the National Academy of Sciences of Belarus, Deputy General Director
Belarus
D. Sc. (Physics and Mathematics), Professor, Corresponding member of the National Academy of Sciences of Belarus, Deputy General Director
References
1. Крыжановский, Г. А. Введение в прикладную теорию управления воздушным движением : учебник для вузов гражданской авиации / Г. А. Крыжановский. – М.: Машиностроение, 1984. – 368 с.
2. Солодухин, В. А. Задачи оптимизации процессов планирования и управления потоками воздушного движения / В. А. Солодухин // Научный вестник МГТУ ГА. – 2009. – № 139. – С. 85–90.
3. Безряков, В. В. Прямые и обратные задачи оптимизации управления потоками воздушного движения в районе аэродрома / В. В. Безряков, Г. А. Крыжановский, В. А. Солодухин // Научный вестник МГТУ ГА. – 2011. – № 171. – С. 109–113.
4. 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.
5. Рубанов, И. В. Задача выбора маршрутов движения объектов при ограничении на сближение / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Междунар. науч. конф., Минск, 27–29 марта 2014 г. – Минск: ОИПИ НАН Беларуси, 2014. – С. 136–140.
6. Рубанов, И. В. Малозатратные методы решения системы разностных и интервальных ограничений / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Седьмой Междунар. науч. конф., Минск, 28–29 марта 2016 г. – Минск: ОИПИ НАН Беларуси, 2016. – С. 170–174.
7. Рубанов, И. В. Подходы к решению дизъюнктивной системы разностных и интервальных ограничений / И. В. Рубанов, М. С. Баркетов, М. Я. Ковалев // Танаевские чтения : докл. Седьмой Междунар. науч. конф., Минск, 28–29 марта 2016 г. – Минск: ОИПИ НАН Беларуси, 2016. – С. 175–180.
8. Рубанов, И. В. Методы поиска нескольких решений системы разностных и интервальных ограничений / И. В. Рубанов, М.С. Баркетов, М. Я. Ковалев // Информатика. – 2016. – № 3(51). – С. 67–79.
9. Кранц, П. Сферическая тригонометрия : пер. с нем. / П. Кранц ; под ред. Я.В. Шпильрейна. – 2-е. изд. – М.: Изд-во ЛКИ, 2007. – 96 с.
10. Кузнецов, С. В. Прикладные задачи обоснования минимальных интервалов эшелонирования воздушных судов с использованием системы наблюдения ОВД в соответствии с отечественными и международными правилами / С. В. Кузнецов, В. Б. Спрысков // Научный вестник ГосНИИ «Аэронавигация» : сб. науч. тр. – М., 2012. – № 11 : Организация воздушного движения. Использование воздушного пространства. Безопасность полетов. – С. 47–63.
11. 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.
12. 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.
13. Сотсков, Ю. Н. Построение расписания, допустимого относительно смешанного мультиграфа / Ю. Н. Сотсков, В. С. Танаев // Вес. Акад. наук БССР. Сер. физ.-мат. наук. – 1989. – № 4. – С. 94–98.
14. Peron, M. An Abstract Domain Extending Difference-Bound Matrices with Disequality Constraints / M. Peron, N. Halbwachs. – Grenoble, France, 2006. – 15 p.
15. Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. – М.: Мир, 1982. – 416 с.
Review
For citations:
Rubanov I.V., Barketau M.S., Kovalyov M.Y. MODELING MOVEMENT OF OBJECTS WITHOUT STOPS IN A NETWORK OF CROSSING ROUTES. Informatics. 2018;15(1):21-33. (In Russ.)
Views: 738
Email this article 