83075

Автор(ы): 

Автор(ов): 

4

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Оптимизация маршрутов полета БПЛА при групповом патрулировании протяженных территорий как множественная задача коммивояжера с несколькими депо

ISBN/ISSN: 

1684-6427

DOI: 

10.17587/mau.25.259-265

Наименование источника: 

  • Мехатроника, автоматизация, управление

Обозначение и номер тома: 

Т. 25. № 5

Город: 

  • Москва

Издательство: 

  • Новые Технологии

Год издания: 

2024

Страницы: 

259-265
Аннотация
Рассматривается одна из актуальных и ключевых задач транспортной отрасли - задача планирования маршрутов следования транспортных средств. Для многих приложений данная задача может быть описана и формализована как задача коммивояжера (англ. Traveling Salesman Problem, TSP), которая заключается в поиске для коммивояжера оптимального маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В общем случае при планировании таких маршрутов приходится решать множественную задачу коммивояжера (англ. Multiple Traveling Salesman Problem, MTSP), допускающую более одного коммивояжера и более одного депо - пункта их базирования, в котором начинаются и заканчиваются маршруты. MTSP как задача комбинаторной оптимизации относится к классу NP-трудных задач. В настоящей статье излагается эвристический метод ее решения на основе геопространственной кластеризации исходного множества городов. Сначала рассматривается MTSP с одним депо. Дается двухиндексная математическая формализация данной задачи и излагается метод Миллера-Такера-Землина, сводящий ее к задаче целочисленного линейного программирования. Обсуждаются метаэвристические методы решения MTSP. Рассматривается более сложная задача - MTSP с несколькими депо. Излагается кластерный двухэтапный метод решения данной задачи - метод CFRS ("Cluster First - Route Second"), позволяющий свести ее к семейству MTSP с одним депо. Здесь на первом этапе осуществляется геопространственная кластеризация городов, для которой возможно использовать различные методы кластеризации, включая метод K-средних. На втором этапе для каждого построенного кластера осуществляется выбор депо для его обслуживания и строятся маршруты объезда всех городов данного кластера. Обсуждается методология кластеризации как эффективный инструмент решения MTSP. Приводится числовой пример авиационной логистики - маршрутизация полетов группы БПЛА.

Библиографическая ссылка: 

Филимонов А.Б., Филимонов Н.Б., Нгуен Т.К., Фам К.Ф. Оптимизация маршрутов полета БПЛА при групповом патрулировании протяженных территорий как множественная задача коммивояжера с несколькими депо // Мехатроника, автоматизация, управление. 2024. Т. 25. № 5. С. 259-265.