Abstract: A line segment (barrier) is specified on the plane, as well as the location of depots. Each sensor is able to travel a limited-length path, starting and ending at its depot. The part of the barrier along which the sensor moves is covered by this sensor. It is necessary to place some number of mobile sensors (drones) in each depot in order to cover the entire barrier with a minimum number of drones (MinNum), or to minimize the total length of paths traveled by drones (MinSum), or to minimize the maximum distance traveled by a drone (MinMax). Previously, the authors investigated a similar problem with an unlimited number of drones and, for its solution, proposed a pseudopolynomial algorithm depending on the length of the barrier L. In this paper, a generalized problem with a limited number of drones is considered and, to construct an optimal solution, we propose an algorithm with the same complexity. However, in the case of an unlimited number of drones, the new algorithm has complexity L times less than the previous one.

Cite: Erzin A.I. , Shadrina A.V.
Drone Placement for Optimal Barrier Coverage
Journal of Applied and Industrial Mathematics. 2025. V.19. N2. P.230-239. DOI: 10.1134/S1990478925020036 Scopus РИНЦ OpenAlex

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

Dates:

Submitted:	Feb 10, 2025
Accepted:	Apr 22, 2025

Identifiers:

≡ Scopus:	2-s2.0-105035394893
≡ Elibrary:	89162701
≡ OpenAlex:	W7147429284

Altmetrics: