Оптимальное размещения дронов, покрывающих барьер в прямоугольной метрике

Оптимальное размещения дронов, покрывающих барьер в прямоугольной метрике

Ерзин А. И.
Дискретный анализ и исследование операций, 33, 1, 56-70 (2026)
Скачать статью

УДК 519.8+518.25 
DOI: 10.33048/daio.2026.33.849

Аннотация:

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

Ил. 3, библиогр. 19.

Литература:
  1. Bhattacharya B., BurmesterM., Hu Y., Kranakis E., Shi Q., Wiese A. Optimal movement of mobile sensors for barrier coverage of a planar region // Theor. Comput. Sci. 2009. V. 410, No. 52. P. 5515–5528. DOI: 10.1016/j.tcs. 2009.07.007.
     
  2. Czyzowicz J., Kranakis E., Krizanc D. [et al.]. On minimizing the sum of sensor movements for barrier coverage of a line segment // Ad-hoc, mobile and wireless networks. Proc. 9th Int. Conf. (Edmonton, Canada, Aug. 20–22, 2010). Heidelberg: Springer, 2010. P. 29–42. (Lect. Notes Comput. Sci.; V. 6288). DOI: 10.1007/978-3-642-14785-2_3.
     
  3. Dobrev S., Durocher S., Eftekhari M. [et al.]. Complexity of barrier coverage with relocatable sensors in the plane // Theor. Comput. Sci. 2015. V. 579. P. 64–73. DOI: 10.1016/j.tcs.2015.02.006.
     
  4. Wang H., Zhang X. Minimizing the maximum moving cost of interval coverage // Algorithms and computation. Proc. 26th Int. Symp. (Nagoya, Japan, Dec. 9–11, 2015). Heidelberg: Springer, 2015. P. 188–198. (Lect. Notes Comput. Sci.; V. 9472). DOI: 10.1007/978-3-662-48971-0_17.
     
  5. Cherry A., Gudmundsson J., Mestre J. Barrier coverage with uniform radii in 2D // Algorithms for sensor systems. Rev. Sel. Pap. 13th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks (Vienna, Austria, Sept. 4–8, 2017). Cham: Springer, 2017. P. 57–69. (Lect. Notes Comput. Sci.; V. 10718). DOI: 10.1007/978-3-319-72751-6_5.
     
  6. Erzin A. I., Lagutkina N. A. Barrier coverage problem in 2D // Algorithms for sensor systems. Rev. Sel. Pap. 14th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks (Helsinki, Finland, Aug. 23–24, 2018). Cham: Springer, 2019. P. 118–130. (Lect. Notes Comput. Sci.; V. 11410). DOI: 10. 1007/978-3-030-14094-6_8.
     
  7. Erzin A. I., Shadrina A. V. Optimal placement of mobile sensors for the distance-constrained line routing problem // Mathematical optimization theory and operations research: Recent trends. Rev. Sel. Pap. 23th Int. Conf. (Omsk, Russia, June 30 – July 6, 2024). Cham: Springer, 2024. P. 172–184. (Commun. Comput. Inf. Sci.; V. 2239). DOI: 10.1007/978-3-031-73365-9_12.
     
  8. Ерзин А. И., Шадрина А. В. Размещение дронов для оптимального покрытия барьера // Дискрет. анализ и исслед. операций. 2025. Т. 32, № 2. С. 54–71. DOI: 10.33048/daio.2025.32.828.
     
  9. Bar-Noy A., Rawitz D., Terlecky P. “Green” barrier coverage with mobile sensors // Algorithms and complexity. Proc. 9th Int. Conf. (Paris, France, May 20–22, 2015). Cham: Springer, 2015. P. 33–46. (Lect. Notes Comput. Sci.; V. 9079). DOI: 10.1007/978-3-319-18173-8_2.
     
  10. Benkoczi R., Friggstad Z., Gaur D., Thom M. Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line // Algorithms for sensor systems. Rev. Sel. Pap. 11th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks (Patras, Greece, Sept. 17–18, 2015). Cham: Springer, 2015. P. 98–111. (Lect. Notes Comput. Sci.; V. 9536). DOI: 10.1007/978-3-319-28472-9_8.
     
  11. Andrews A. M., Wang H. Minimizing the aggregate movements for interval coverage // Algorithmica. 2017. V. 78, No. 1. P. 47–85. DOI: 10.1007/ s00453-016-0153-8.
     
  12. Coutinho W. P., Battarra M., Fliege J. The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review // Comput. Ind. Eng. 2018. V. 120. P. 116–128. DOI: 10.1016/j.cie.2018.04.037.
     
  13. Campbell J. F., Corberan A., Plana I., Sanchis J. M. Drone arc routing problems // Networks. 2018. V. 72, No. 4. P. 543–559. DOI: 10.1002/net. 21858.
     
  14. Kek A. G. H., Cheu R. L., Meng Q. Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots // Math. Comput. Model. 2008. V. 47. P. 140–152. DOI: 10.1016/j.mcm.2007.02.007.
     
  15. Erzin A. I., Plotnikov R. V. Distance-constrained line routing problem // Optimization and applications. Rev. Sel. Pap. 10th Int. Conf. (Petrovac, Montenegro, Sep. 30 – Oct. 4, 2019). Cham: Springer, 2020. P. 43–55. (Commun. Comput. Inf. Sci.; V. 1145). DOI: 10.1007/978-3-030-38603-0_4.
     
  16. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978. 334 с.
     
  17. Vidal R. V. V. Optimal partition of an interval — The discrete version // Applied simulated annealing. Heidelberg: Springer, 1993. P. 291–312. (Lect. Notes Econ. Math. Syst.; V. 396). DOI: 10.1007/978-3-642-46787-5_15.
     
  18. Jackson B., Scargle J. D., Barnes D. [et al.]. An algorithm for optimal partitioning of data on an interval // IEEE Signal Proces. Lett. 2005. V. 12, No. 2. P. 105–108. DOI: 10.1109/LSP.2001.838216.
     
  19. Tilli P., Zucco D. Optimal partitioning of an interval and applications to Sturm–Liouville eigenvalues // J. Differ. Equ. 2019. V. 268, No. 8. P. 4900–4919. DOI: 10.1016/j.jde.2019.12.026.

Работа выполнена в рамках государственного задания Института математики им. С. Л. Соболева (проект № FWNF–2026–0021). Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Ерзин Адиль Ильясович
  1. Институт математики им. С. Л. Соболева, 
    пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия

E-mail: adilerzin@math.nsc.ru 

Статья поступила 17 декабря 2025 г.
После доработки — 15 января 2026 г.
Принята к публикации 22 января 2026 г.

Abstract:

We consider a line segment in the plane, called a barrier, and its monitoring (coverage) which is performed by identical mobile sensors (drones) with limited trajectory length. Each drone starts from its depot at a certain point on the barrier, moves along the barrier, and returns to its depot after having covered a path of limited length. The part of the barrier along which the drone moves is called covered by this drone. The barrier is covered if each point of it is covered by at least one drone. It is necessary to determine the number of drones in each depot and a trajectory of each drone so that the entire barrier is covered and the total length of the drones’ paths (trajectories) is minimal. A dynamic programming algorithm is known for solving this problem with Euclidean distance. It constructs an optimal solution with pseudo-polynomial complexity. In this article, a polynomial algorithm is proposed to solve the problem in a rectilinear metric that constructs an optimal solution with quadratic complexity of the depot number. 

Illustr. 3, bibliogr. 19.

References:
  1. B. Bhattacharya, M. Burmester, Y. Hu, E. Kranakis, Q. Shi, and A. Wiese Optimal movement of mobile sensors for barrier coverage of a planar region, Theor. Comput. Sci. 410 (52), 5515–5528 (2009), DOI: 10.1007/ 978-3-540-85097-7_10.
     
  2. J. Czyzowicz, E. Kranakis, D. Krizanc, [et al.], On minimizing the sum of sensor movements for barrier coverage of a line segment, in Ad-Hoc, Mobile and Wireless Networks (Proc. 9th Int. Conf., Edmonton, Canada, Aug. 20–22, 2010) (Springer, Heidelberg, 2010), pp. 29–42 (Lect. Notes Comput. Sci., Vol. 6288), DOI: 10.1007/978-3-642-14785-2_3.
     
  3. S. Dobrev, S. Durocher, M. Eftekhari, [et al.], Complexity of barrier coverage with relocatable sensors in the plane, Theor. Comput. Sci. 579, 64–73 (2015), DOI: 10.1016/j.tcs.2015.02.006.
     
  4. H. Wang and X. Zhang, Minimizing the maximum moving cost of interval coverage, in Algorithms and Computation (Proc. 26th Int. Symp., Nagoya, Japan, Dec. 9–11, 2015) (Springer, Heidelberg, 2015), pp. 188–198 (Lect. Notes Comput. Sci., Vol. 9472), DOI: 10.1007/978-3-662-48971-0_17.
     
  5. A. Cherry, J. Gudmundsson, and J. Mestre, Barrier coverage with uniform radii in 2D, in Algorithms for Sensor Systems (Rev. Sel. Pap. 13th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks, Vienna, Austria, Sept. 4–8, 2017) (Springer, Cham, 2017), pp. 57–69 (Lect. Notes Comput. Sci., Vol. 10718), DOI: 10.1007/978-3-319-72751-6_5.
     
  6. A. I. Erzin and N. A. Lagutkina, Barrier coverage problem in 2D, in Algorithms for Sensor Systems (Rev. Sel. Pap. 14th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks, Helsinki, Finland, Aug. 23–24, 2018) (Springer, Cham, 2019), pp. 118–130 (Lect. Notes Comput. Sci., Vol. 11410), DOI: 10.1007/978-3-030-14094-6_8.
     
  7. A. I. Erzin and A. V. Shadrina, Optimal placement of mobile sensors for the distance-constrained line routing problem, in Mathematical Optimization Theory and Operations Research: Recent Trends (Rev. Sel. Pap. 23th Int. Conf., Omsk, Russia, June 30 – July 6, 2024) (Springer, Cham, 2024), pp. 172–184 (Commun. Comput. Inf. Sci., Vol. 2239), DOI: 10.1007/978-3-031-73365-9.
     
  8. A. I Erzin and A. V. Shadrina, Drone placement for optimal barrier coverage, Diskretn. Anal. Issled. Oper. 32 (2), 54–71 (2025) [Russian] [J. Appl. Ind. Math. 19 (2), 230–239 (2025), DOI: ], DOI: 10.33048/daio.2025.32.828.
     
  9. A. Bar-Noy, D. Rawitz, and P. Terlecky, “Green” barrier coverage with mobile sensors, in Algorithms and Complexity (Proc. 9th Int. Conf., Paris, France, May 20–22, 2015) (Springer, Cham, 2015), pp. 33–46 (Lect. Notes Comput. Sci., Vol. 9079), DOI: 10.1007/978-3-319-18173-8_2.
     
  10. R. Benkoczi, Z. Friggstad, D. Gaur, and M. Thom, Minimizing total sensor movement for barrier coverage by non-uniform sensors on a line, in Algorithms for Sensor Systems (Rev. Sel. Pap. 11th Int. Symp. Algorithms and Experiments for Wireless Sensor Networks, Patras, Greece, Sept. 17–18, 2015) (Springer, Cham, 2015), pp. 98–111 (Lect. Notes Comput. Sci., Vol. 9536), DOI: 10.1007/978-3-319-28472-9_8.
     
  11. A. M. Andrews and H. Wang, Minimizing the aggregate movements for interval coverage, Algorithmica 78 (1), 47–85 (2017), DOI: 10.1007/ s00453-016-0153-8.
     
  12. W. P. Coutinho, M. Battarra, and J. Fliege, The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review, Comput. Ind. Eng. 120, 116–128 (2018), DOI: 10.1016/j.cie.2018.04.037.
     
  13. J. F. Campbell, A. Corberan, I. Plana, and J. M. Sanchis, Drone arc routing problems, Networks 72 (4), 543–559 (2018), DOI: 10.1002/net.21858.
     
  14. A. G. H. Kek, R. L. Cheu, and Q. Meng, Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots, Math. Comput. Model. 47, 140–152 (2008), DOI: 10.1016/j.mcm.2007. 02.007.
     
  15. A. I. Erzin and R. V. Plotnikov, Distance-constrained line routing problem, in Optimization and Applications (Rev. Sel. Pap. 10th Int. Conf., Petrovac, Montenegro, Sep. 30 – Oct. 4, 2019) (Springer, Cham, 2020), pp. 43–55 (Commun. Comput. Inf. Sci., Vol. 1145), DOI: 10.1007/978-3-030-38603-0_4.
     
  16. V. L. Beresnev, É. Kh. Gimadi, and V. T. Dementyev, Extremal Problems of Standardization (Nauka, Novosibirsk, 1978) [Russian].
     
  17. R. V. V. Vidal, Optimal partition of an interval — The discrete version, in Applied Simulated Annealing, (Springer, Heidelberg, 1993), pp. 291–312 (Lect. Notes Econ. Math. Syst., Vol. 396), DOI: 10.1007/ 978-3-642-46787-5_15.
     
  18. B. Jackson, J. D. Scargle, D. Barnes, [et al.], An algorithm for optimal partitioning of data on an interval, IEEE Signal Proces. Lett. 12 (2), 105–108 (2005), DOI: 10.1109/LSP.2001.838216.
     
  19. P. Tilli and D. Zucco, Optimal partitioning of an interval and applications to Sturm–Liouville eigenvalues, J. Differ. Equ. 268 (8), 4900–4919 (2019), DOI: 10.1016/j.jde.2019.12.026.