Научная электронная библиотека ULRICH'S Periodicals Directory

Сибирский государственный университет
науки и технологий имени академика М.Ф. Решетнева

Сибирский аэрокосмический журнал
ISSN 2712-8970 (Print) ISSN 2782-5760 (on-line)

Сведения об образовательной организации

UDK УДК 004.021 Doi: 10.31772/2712-8970-2022-23-2-168-176
Методы построения маршрутов вне населенных пунктов на основе GPS-данных
Крутько Д. А., Калашников А. С., Буряченко В. В.
Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева Российская Федерация, 660037, г. Красноярск, просп. им. газ. «Красноярский Рабочий», 31
Методы построения маршрутов включают задачу поиска кратчайшей траектории между двумя или несколькими объектами, которая может изменяться в зависимости от погодных условий, координат высоты и других параметров. Методы, которые рассматриваются в статье, позволяют выполнять построение маршрутов с использованием GPS-треков для различных областей знаний: проектирование маршрутов в рамках города, региона, страны либо при дистанционном зондировании земли. Рассматриваемые алгоритмы используются в сфере мониторинга окружающей среды при чрезвычайных ситуациях, для поиска оптимальных маршрутов передачи данных в спутниковых системах и их валидации, а также в организационно-экономических системах. Наиболее широко для построения маршрутов применяются подходы теории графов и поиска в пространстве состояний, где любой траектории между объектами ставится свой вес. Однако до сих пор не существует универсальной системы, позволяющей построить оптимальный маршрут по пересеченной местности. В статье рассмотрены такие методы, как алгоритм Дейкстры, Левита, Флойда – Уоршелла, а также выполнено сравнение их эффективности по времени работы и вычислительной сложности. Целью является разработка алгоритма поиска кратчайшего пути и построения туристического маршрута от заданной точки А до точки Б, что откроет большие возможности для горожан самостоятельно посещать новые интересные районы, активно проводить свободное время и узнавать окрестности города. Система апробирована на территории Торгашинского хребта, включает более 38 точек маршрута, расположенных на расстоянии более 25 км, и позволяет построить желаемые маршруты в течение менее 15 мс с учетом перепада весов и расстояния между объектами. При этом система допускает ввод собственных координат, которые учитываются при построении маршрутов.
Ключевые слова: кратчайший путь, теория графов, построение маршрутов, gpx-треки, алгоритм Дейкстры.
References

1.   Крутько Д. А. Проблема автоматизации построения схем маршрутов пешего туризма в горных массивах Красноярского края // Актуальные проблемы авиации и космонавтики : материалы VII Междунар. науч.-практ. конф. Красноярск, 2021. Т. 2. С. 260–262.

2.   Иванова К. А., Маликова О. В. Технология комплексной обработки геопространственных данных для мониторинга последствий чрезвычайных ситуаций // Региональные проблемы дистанционного зондирования Земли : материалы II Междунар. науч. конф. (22–25 сентября 2015, г. Красноярск) / науч. ред. Е. А. Ваганов ; отв. ред. М. В. Носков. Красноярск : Сиб. федер. ун-т, 2015. С. 62–65.

3.   Агафонов А. А., Максимов А. И., Бородинов А. А. Исследование эффективности вычисления надежного кратчайшего пути с использованием GPU // VI Междунар. конф. и молодёжная школа «Информационные технологии и нанотехнологии» (ИТНТ-2020), 2020. С. 1–7.

4.   Агафонов А. А., Мясников В. В. Метод определения надежного кратчайшего пути в стохастической сети с использованием параметрически заданных устойчивых распределений вероятностей // СПИИРАН. 2020. Т. 3, вып. 18. С. 558–582.

5.   Федоров А. А., Сошилов И. В., Логинов В. Н. Эвристические алгоритмы поиска маршрутов передачи данных в спутниковых системах и их валидация // ТРУДЫ МФТИ. 2020. Т. 12,
№ 3. С. 1–9.

6.   Рамзаев В. М., Хаймович И. Н., Мартынов И. В. Методы поиска кратчайших путей на графах в организационно-экономических системах и их реализация // V Междунар. конф. и молодёжная школа «Информационные технологии и нанотехнологии» (ИТНТ-2019), 2019. С. 1–8.

7.   Стыценко Ф. В., Сайгин И. А., Барталев С. А. Исследование возможностей многолетнего мониторинга состояния поврежденных пожарами лесов на основе спутниковых данных // Информационные технологии в дистанционном зондировании Земли – RORSE 2018. ИКИ РАН, 2019. С. 185–190. Doi: 10.21046/rorse2018.185.

8.   Миклашевич Т. С., Барталев C. А., Плотников Д. Е. Интерполяционный алгоритм восстановления длинных временных рядов данных спутниковых наблюдений растительного покрова // Современные проблемы дистанционного зондирования Земли из космоса. 2019. Т. 16. № 6.
С. 1–10.

9.   Zhen B., Noon C. Shortest Path Algorithms: An Evaluation using Real Road Networks Transportation Science. 1998. Р. 1–10.

10.  Algorithm to find tourism place shortest route: a systematic literature review / E. Madyat-
madja, H. Nindito, R. Bhaskoro et. аl. // Journal of Theoretical and Applied Information Technology. 2021. Vol. 99, No. 4. Р. 1–10.

11.  Fitriansyah A., Parwati N., Wardhani D., Kustian N. Dijkstra’s Algorithm to Find Shortest Path of Tourist Destination in Bali ICASMI, 2018.

12.  Базовые алгоритмы нахождения кратчайших путей во взвешенных графах [Электронный ресурс]. URL: https://habr.com/ru/post/119158/.

13.  Алгоритм Левита – алгоритмы поиска на графах [Электронный ресурс]. URL: https://amp.ww.google-info.org/3957083/1/algoritm-levita.html.

14.  A Study on Different Algorithms for Shortest Route Problem / Dr. Roopa, R. Apoorva,
H. Srinivasu, M. Viswanatah // International Journal of Engineering Research & Technology (IJERT). 2013. Vol. 2, Iss. 9. Р. 1–13.

15.  Крутько Д. А. Проблема поиска кратчайшего пути в трехмерном пространстве на территории Торгашинского хребта // Актуальные проблемы авиации и космонавтики : материалы VIII Междунар. науч.-практ. конф. Красноярск, 2022.

16.  xml.dom.minidom – Minimal DOM implementation [Электронный ресурс]. URL: https:// docs.python.org/3/library/xml.dom.minidom.html.

17.  Вычисление расстояния и начального азимута между двумя точками на сфере [Электронный ресурс]. URL: https://gis-lab.info/qa/great-circles.html.


Крутько Диана Андреевна – студентка группы БПИ18-01; Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева. E-mail: krutko.d00@gmail.com.

Калашников Алексей Сергеевич – студент группы А17-02; Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева. E-mail: fangy.ko@gmail.com.

Буряченко Владимир Викторович – кандидат технических наук, доцент; Сибирский государственный университет науки и технологий имени академика М. Ф. Решетнева. E-mail: buryachenko@sibsau.ru.


  Методы построения маршрутов вне населенных пунктов на основе GPS-данных