Методика построения оптимального маршрута при проведении работ по сканированию территории
+7 (383) 343-12-55 vestnik@ssga.ru
Ru
En
Ru
En
Авторам публикаций
Вестник СГУГиТАрхив журнала Методика построения оптимального маршрута при проведении работ по сканированию территории

Методика построения оптимального маршрута при проведении работ по сканированию территории

Землеустройство, кадастр и мониторинг земель
УДК: 528.44:528.721.221.6
DOI: 10.33764/2411-1759-2025-30-5-89-100
Д. А. Гура 1 2, Р. А. Дьяченко 1, С. А. Ярутин 1, А. С. Макарян 1
Год: 2025
Том: 30
№: 5
Страницы: 89 - 100
1 Кубанский государственный технологический университет, г. Краснодар, Российская Федерация
2 Кубанский государственный аграрный университет, г. Краснодар, Российская Федерация

Финансирование: Исследование проводилось при финансовой поддержке Кубанского научного фонда в рамках проекта № LAB-24.1/2.

Аннотация:

В работе представлена методика оптимального обхода участка с использованием наземного лазерного сканера, реализованная на основе модифицированного алгоритма Кристофидеса и модели целочисленного линейного программирования (ILP). Предлагаемый подход решает NP-трудную задачу, сводимую к модифицированной версии задачи коммивояжера, с учетом дополнительных геометрических ограничений, обусловленных наличием препятствий на территории. Методика включает дискретизацию участка, генерацию облаков точек вокруг вершин препятствий и построение графа допустимых позиций сканирования. Экспериментальная проверка на синтетических и реальных данных показала, что предложенный алгоритм позволяет снизить количество необходимых сканирующих окружностей и суммарную длину маршрута обхода на 12–18 % по сравнению с традиционными эвристическими подходами, при сохранении полного покрытия границы. Кроме того, проведенный сравнительный анализ выявил, что, несмотря на возрастание вычислительной сложности ILP-модели с увеличением числа препятствий, предложенная методика обладает высокой точностью и применима в задачах геодезии, кадастра, картографии и инженерной диагностики. Перспективными направлениями дальнейших исследований являются динамическая адаптация маршрута и интеграция гибридных методов оптимизации для повышения масштабируемости решения.

Ключевые слова (RU):

кадастр, лазерное сканирование, маршрут, алгоритм Кристофидеса, оптимизация, NP-трудная задача

Ключевые слова (EN):

cadastre, laser scanning, the Christofides algorithm, route, optimization, NP-hard problem

Читать статью Скачать JATS XML

Библиографический список:

  1. Christofides, N. Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University. – 1976.
  2. Шарафутдинова А. А., Брынь М. Я. Опыт применения наземного лазерного сканирования и информационного моделирования для управления инженерными данными в течение жизненного цикла промышленного объекта // Вестник СГУГиТ. – 2021. – Т. 26, № 1. – С. 57–67. – DOI 10.33764/2411-1759-2021-26-1-57-67. – EDN UONPQL.
  3. Дьяченко Р. А., Борисов С. Н. О возможности использования API геоинформационных систем // Научные чтения профессора Н. Е. Жуковского. Сборник научных статей VIII Международной научно-практической конференции «Научные чтения имени профессора Н. Е. Жуковского». КВВАУЛ им. Героя Советского Союза А. К. Серова, 2018. – C. 299–302. – EDN YPSAUK.
  4. Макаров О. О. Анализ метаэвристик для задач многоагентной маршрутизации // Таврический вестник информатики и математики. – 2023. – № 1 (58). – С. 62–87. – EDN CHFQMW.
  5. Мартынов А. В., Курейчик В. М. Гибридный алгоритм решения задачи коммивояжера // Известия ЮФУ. Технические науки. – 2015. – № 4 (165). – С. 36–44. – EDN TYMNZV.
  6. Schneider D., Klein R. Review of scanning station placement strategies in 3D acquisition // Computer Vision and Image Understanding. – 2019. – Vol. 182. – P. 34–50. – DOI 10.1016/j.cviu.2019.03.003.
  7. Мухаммад Ш. Х. Геодезическое обеспечение обмерной фиксации объектов культурного наследия на основе применения лазерно-сканирующей съемки : дис. … канд. техн. наук : 25.00.35 / Мухаммад Шокер Хуссейн. – СПб., 2022. – 145 с.
  8. Конушина Е. Ю., Симашева Д. В. Фотограмметрия, как основополагающая дисциплина современного геодезиста // Перспективные разработки и прорывные технологии в АПК: Сборник материалов национальной научно-практической конференции, Тюмень, 21–23 октября 2020 г. – Тюмень : Государственный аграрный университет Северного Зауралья, 2020. – С. 30–34. – EDN LLOUUJ.
  9. Красиков А. А. Необходимость интеграции геодезических и BIM-технологий в процессе проектирования зданий // Наука и образование: актуальные вопросы, достижения и инновации: сборник статей IX Международной научно-практической конференции, Пенза, 25 августа 2023 года. – Пенза : Наука и Просвещение, 2023. – С. 185–187. – EDN OQTABM.
  10. Литвиненко М. В. Практические аспекты исправления реестровых ошибок при наложении границ нескольких смежных земельных участков // Известия высших учебных заведений. Геодезия и аэрофотосъемка. – 2018. – Т. 62, № 5. – С. 530–535. – DOI 10.30533/0536-101X2018-62-5-530-535. – EDN YMSADZ.
  11. Краснопевцев Б. В. Фотограмметрия. – М. : Репрография МИИГАиК, 2008. – С. 91. – EDN QKHVXH.
  12. Гура Д. А., Дубенко Ю. В., Бучацкий П. Ю., Марковский И. Г., Хушт Н. И. Мониторинг сложных объектов инфраструктуры // Вестник Адыгейского государственного университета. Сер. 4. Естественно-математические и технические науки. – 2019. – № 4 (251). – С. 74–80.
  13. Аврунев Е. И., Горобцов С. Р. Геодезическое обеспечение кадастровых работ : монография. – Новосибирск : СГУГиТ, 2024. – 239 с.
  14. Брынь М. Я., Богомолова Н. Н., Журавлев И. Н., Никитчин А. А. Возможности применения лазерного сканирования на стадии изысканий при реконструкции искусственных сооружений // Бюллетень результатов научных исследований. – 2020. – № 1. – С. 43–53. – DOI 10.20295/2223-9987-2020-1-43-53. – EDN IEWCHM.
  15. Гура Д. А., Ващенко Д. А., Беспятчук Д. А., Самарин С. В., Пшидаток С. К. Перспективы применения воздушного лазерного сканирования и аэрофотосъемки для обеспечения пространственными данными 3D-кадастра // Землеустройство, кадастр и мониторинг земель. – 2023. – № 3. – С. 179–183. – DOI 10.33920/sel-04-2303-07. – EDN QVATCF.
  16. Щенявская Л. А., Шалая А. А. Технология объединения пространственных данных, полученных по результатам наземного лазерного сканирования, цифровой аэрофотосъемки и ручного лазерного сканирования // Молодежная наука. Сборник лучших научных работ молодых ученых : материалы LI студенческой научной конференции, Краснодар, 29 февраля 2024 г. – Краснодар : Кубанский государственный технологический университет, 2024. – С. 509–515. – EDN UCRUHR.
  17. Гура Д. А., Дьяченко Р. А., Шалая А. А. Разработка модульной структуры геоинформационной системы пространственного анализа данных // Землеустройство, кадастр и мониторинг земель. – 2024. – Т. 19, № 5 (232). – С. 314–317. – DOI 10.33920/sel-04-2405-07. – EDN NUMDGH.
  18. Дьяченко Р. А., Гура Д. А., Осенняя А. В. [и др.] Разработка структуры информационной системы геопространственных данных для решения задач территориального планирования // Известия высших учебных заведений. Геодезия и аэрофотосъемка. – 2024. – Т. 68, № 4. – С. 87–99. – DOI 10.30533/GiA-2024-013. – EDN YQASPD.
  19. Золотухин В. В. Цифровое геодезическое оборудование в археологических исследованиях с применением методов геоинформационных систем // Вестник Новосибирского государственного университета. Сер. История, филология. – 2011. – Т. 10, № 7. – С. 61–66. – EDN OFWUYJ.
  20. Волынова М. П. Цифровизация результатов территориального планирования на примере Федеральной государственной информационной системы территориального планирования // Цифровизация землепользования и кадастров: тенденции и перспективы : материалы международной научно-практической конференции 25 сентября 2020 г. – М. : ГУЗ, 2020. – С. 70–74. – EDN RQJJXV.
  21. Портнов А. М., Добровольский Д. О. Сравнительная оценка геометрической сложности контуров объектов местности при осуществлении государственного земельного надзора и мониторинга земель на примере объектов капитального строительства // Геодезия и картография. – 2024. – Т. 85, № 3. – С. 50–61. – DOI 10.22389/0016-2024-1005-3-50-61. – EDN HTGACU.
  22. Чернов А. В. Исследование вариантов построения 3D-модели объектов недвижимости для целей кадастра // Вестник СГУГиТ. – 2018. – Т. 23, № 3. – С. 192–210. – EDN YAATKP.
  23. Богомолова Н. Н. Определение точности геодезических измерений при реконструкции исторических объектов // Известия Петербургского университета путей сообщения. – 2022. – Т. 19, № 4. – С. 693–701. – DOI 10.20295/1815-588X-2022-4-693-701. – EDN QLTIEJ.
  24. Степанов И. Ю. Использование методов машинного обучения в геоинформационных моделях при решении задач геофизической разведки // Вестник СГУГиТ. – 2024. – Т. 29, № 2. – С. 108–117. – DOI 10.33764/2411-1759-2024-2-108-117. – EDN BHXCBY.
  25. Гура Д. А. Применение технологий машинного обучения для распознавания крыш объектов недвижимости // Цифровые, компьютерные и информационные технологии в науке и образовании : сборник статей Межрегиональной научно-практической конференции с международным участием, Брянск, 01–02 ноября 2023 г. – Брянск : Брянский государственный университет имени академика И. Г. Петровского, 2023. – С. 301–309. – EDN OAKNKJ.

Образец цитирования:

Гура Д. А., Дьяченко Р. А., Ярутин С. А., Макарян А. С. Методика построения оптимального маршрута при проведении работ по сканированию территории // Вестник СГУГиТ. – 2025. – Т. 30, № 5. – С. 89-100. – DOI 10.33764/2411-1759-2025-30-5-89-100