Optimal Placement of Mobile Sensors for the Distance-Constrained Line Routing Problem

A line segment (barrier) is specified on the plane, as well as the location of the depots. Each sensor can travel a limited-length path, starting and ending at its depot. The part of the barrier along which the sensor moved is covered by this sensor. It is necessary to determine the number of sensors (drones) in each depot in order to cover the entire barrier using a minimal number of drones (problem MinNum), or to minimize the maximum distance traveled by each drone (problem MinMax), or to minimize the total length of paths traveled by all drones (problem MinSum). Previously, the problem MinNum of covering a barrier using minimal number of drones (one drone in each depot) was considered. In the problem considered in this paper, the solution is the number of drones in each depot, as well as the trajectory of each drone. We propose algorithms for solving the problem for all three criteria mentioned above.