|
Математическая теория управления
О перераспределении целей между перехватчиками в динамической задаче коммивояжёра
А. А. Галяев, П. Д. Долгушин ФГБУН Институт проблем управления им. В.А. Трапезникова РАН, Москва
Аннотация:
Рассматривается динамическая задача коммивояжёра (ДЗК) с прямолинейно и равномерно движущимися целями. Параметры закона движения целей, такие как начальное положение, скорость и направление, считаются заранее известными. В иностранной литературе для подобной задачи употребительно название "moving-target traveling salesman problem" (MTTSP). В рамках общей постановки рассмотрена частная подзадача – задача о перераспределении целей между двумя коммивояжёрами (перехватчиками). В качестве критерия оптимальности исследуется временной критерий, т.е. наибольшее из времён работ двух перехватчиков. Полагая известным оптимальный план обхода целей для одного перехватчика, ставится задача о поиске оптимального плана для каждого из двух при заданной исходной конфигурации целей. Тем самым исследуемая в работе в рамках MTTSP подзадача отличается от общей постановки наличием дополнительной информации. Для этой постановки предложены два алгоритма перераспределения целей, проведен их статистический анализ и представлены результаты их работы. Первый из алгоритмов более точен, т.е. характеризуется меньшей средней ошибкой, но более длителен в исполнении. Второй алгоритм демонстрирует более быструю работу за счёт уменьшения точности.
Ключевые слова:
динамическая задача коммивояжёра, комбинаторная оптимизация, задача перераспределения целей.
Поступила в редакцию: 27 февраля 2024 г. Опубликована: 31 июля 2024 г.
Образец цитирования:
А. А. Галяев, П. Д. Долгушин, “О перераспределении целей между перехватчиками в динамической задаче коммивояжёра”, УБС, 110 (2024), 87–112
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/ubs1215 https://www.mathnet.ru/rus/ubs/v110/p87
|
Статистика просмотров: |
Страница аннотации: | 40 | PDF полного текста: | 19 | Список литературы: | 13 |
|