TY - JOUR

T1 - Размещение дронов для оптимального покрытия барьера

AU - Ерзин, Адиль Ильясович

AU - Шадрина, Анжела Викторовна

N1 - Ерзин, А. И. Размещение дронов для оптимального покрытия барьера / А. И. Ерзин, А. В. Шадрина // Дискретный анализ и исследование операций. – 2025. – Т. 32, № 2(164). – С. 54-71. – DOI 10.33048/daio.2025.32.828. – EDN VEDBBL. Исследование выполнено в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF-2022-0019).

PY - 2025

Y1 - 2025

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

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

KW - ПОКРЫТИЕ БАРЬЕРА

KW - ЛИНЕЙНАЯ МАРШРУТИЗАЦИЯ

KW - МОБИЛЬНОЕ УСТРОЙСТВО (ДРОН)

KW - ОГРАНИЧЕННАЯ ЭНЕРГИЯ

KW - ТРУДОЁМКОСТЬ

UR - https://elibrary.ru/item.asp?id=82969954

U2 - 10.33048/daio.2025.32.828

DO - 10.33048/daio.2025.32.828

M3 - статья

VL - 32

SP - 54

EP - 71

JO - Дискретный анализ и исследование операций

JF - Дискретный анализ и исследование операций

SN - 1560-7542

IS - 2 (164)

ER -