Реферат: На плоскости задан отрезок прямой линии (барьер), а также координаты депо, в которых нужно разместить мобильные устройства (сенсоры или дроны). Каждый дрон стартует из своего депо к некоторой точке барьера, двигается вдоль барьера и возвращается в своё депо, пройдя путь ограниченной длины. Часть барьера, вдоль которой двигался дрон, считается покрытой этим дроном. Барьер покрыт, если каждая его точка покрыта хотя бы одним дроном. Требуется разместить ограниченное число дронов в заданном множестве депо и определить траектории дронов таким образом, чтобы покрыть весь барьер и при этом число дронов было минимальным (MinNum), или общая длина путей дронов была минимальной (MinSum), или длина самого протяжённого пути среди всех дронов была минимальной (MinMax). Ранее авторы исследовали аналогичную задачу с неограниченным числом дронов и предложили псевдополиномиальный алгоритм для её решения, зависящий от длины барьера L. В этой статье рассматривается обобщённая задача, в которой число дронов ограниченно, и для построения её оптимального решения предложен алгоритм такой же трудоёмкости. Вместе с тем, в случае неограниченного числа дронов новый алгоритм имеет трудоёмкость в L раз меньше трудоёмкости ранее разработанного алгоритма.

Библиографическая ссылка: Ерзин А.И. , Шадрина А.В.
Размещение дронов для оптимального покрытия барьера
Дискретный анализ и исследование операций. 2025. Т.32. №2. С.54-71. DOI: 10.33048/daio.2025.32.828 РИНЦ

Даты:

Поступила в редакцию:	10 февр. 2025 г.
Принята к публикации:	22 апр. 2025 г.
Опубликована в печати:	2 окт. 2025 г.
Опубликована online:	2 окт. 2025 г.

Идентификаторы БД:

РИНЦ:

82969954

Цитирование в БД: Пока нет цитирований

Альметрики: