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

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

Dates:

Submitted:	Feb 10, 2025
Accepted:	Apr 22, 2025
Published print:	Oct 2, 2025
Published online:	Oct 2, 2025

Identifiers:

Elibrary:

82969954

Citing: Пока нет цитирований

Altmetrics: