О перераспределении целей между перехватчиками в динамической задаче коммивояжёра

Автор(ы): Галяев А.А., Долгушин П.Д.

Выпуск: 110

Рубрика: Математическая теория управления

Год: 2024

Библиография: Галяев А.А., Долгушин П.Д. О перераспределении целей между перехватчиками в динамической задаче коммивояжёра // Управление большими системами. Выпуск 110. М.: ИПУ РАН, 2024. С.87-112. DOI: https://doi.org/10.25728/ubs.2024.110.4

Дата опубликования: 31.07.2024

Ключевые слова: динамическая задача коммивояжёра, комбинаторная оптимизация, задача перераспределения целей

Аннотация: Рассматривается динамическая задача коммивояжёра (ДЗК) с прямолинейно и равномерно движущимися целями. Параметры закона движения целей, такие как начальное положение, скорость и направление, считаются заранее известными. В иностранной литературе для подобной задачи употребительно название "moving-target traveling salesman problem" (MTTSP). В рамках общей постановки рассмотрена частная подзадача -- задача о перераспределении целей между двумя коммивояжёрами (перехватчиками). В качестве критерия оптимальности исследуется временной критерий, т.е. наибольшее из времён работ двух перехватчиков. Полагая известным оптимальный план обхода целей для одного перехватчика, ставится задача о поиске оптимального плана для каждого из двух при заданной исходной конфигурации целей. Тем самым исследуемая в работе в рамках MTTSP подзадача отличается от общей постановки наличием дополнительной информации. Для этой постановки предложены два алгоритма перераспределения целей, проведен их статистический анализ и представлены результаты их работы. Первый из алгоритмов более точен, т.е. характеризуется меньшей средней ошибкой, но более длителен в исполнении. Второй алгоритм демонстрирует более быструю работу за счёт уменьшения точности.

Author(s): Galyaev A., Dolgushin P.

Article title: On redistribution of targets between interceptors in moving targets traveling salesman problem

Issue: 110

Year: 2024

Keywords: MTTSP, combinatorial optimization, target redistribution problem

Abstract: The paper considers a moving target traveling salesman problem (MTTSP) with rectilinearly and uniformly moving targets. Parameters of the targets’ law of motion such as initial positions, velocities and motion directions considered to be known. Within the framework of the general formulation, a private subtask is considered -- task on the redistribution of targets between two traveling salesmen (interceptors). Time criterion is used as an optimization criterion. Time criterion here is maximum operating time of two interceptors. Assuming that the optimal plan for bypassing targets for one interceptor is known, the task is to find the optimal plan for each of the two with a given initial target configuration. Thus, the under study problem differs from the general MTTSP in having some additional information. For considered problem two algorithms for redistributing targets are proposed, statistical analysis of both of them is carried out and the results of their work are presented. The first one is more precise but is slower. The second one is faster because of less precision.