МОДЕЛИРОВАНИЕ ДВИЖЕНИЯ ОБЪЕКТОВ БЕЗ ОСТАНОВОК ПО СЕТИ ПЕРЕСЕКАЮЩИХСЯ МАРШРУТОВ
Аннотация
Рассматривается задача моделирования движения объектов по сети пересекающихся маршрутов. Задача формулируется в терминах дизъюнктивного линейного программирования, смешанного целочисленного линейного программирования и теории графов. Рассматривается несколько вариантов задания ограничений на сближение объектов. Доказывается NP-полнота задачи в сильном смысле.
Об авторах
И. В. Рубанов
Белорусская государственная академия авиации
Беларусь
старший преподаватель кафедры естественнонаучных дисциплин
Беларусь
старший преподаватель кафедры естественнонаучных дисциплин
М. С. Баркетов
Объединенный институт проблем информатики Национальной академии
наук Беларуси, Минск
Беларусь
кандидат физико-математических наук, старший научный сотрудник лаборатории математической кибернетики
Беларусь
кандидат физико-математических наук, старший научный сотрудник лаборатории математической кибернетики
М. Я. Ковалев
Объединенный институт проблем информатики Национальной академии
наук Беларуси, Минск
Беларусь
доктор физико- математических наук, профессор, член-корреспондент НАН Беларуси, заместитель генерального директора
Беларусь
доктор физико- математических наук, профессор, член-корреспондент НАН Беларуси, заместитель генерального директора
Список литературы
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 с.
Рецензия
Для цитирования:
Рубанов И.В., Баркетов М.С., Ковалев М.Я. МОДЕЛИРОВАНИЕ ДВИЖЕНИЯ ОБЪЕКТОВ БЕЗ ОСТАНОВОК ПО СЕТИ ПЕРЕСЕКАЮЩИХСЯ МАРШРУТОВ. Информатика. 2018;15(1):21-33.
For citation:
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.)
Просмотров: 740
Послать статью по эл. почте 