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

Методы построения маршрутов включают задачу поиска кратчайшей траектории между двумя или несколькими объектами, которая может изменяться в зависимости от погодных условий, координат высоты и других параметров. Методы, которые рассматриваются в статье, позволяют выполнять построение маршрутов с использованием GPS-треков для различных областей знаний: проектирование маршрутов в рамках города, региона, страны либо при дистанционном зондировании земли. Рассматриваемые алгоритмы используются в сфере мониторинга окружающей среды при чрезвычайных ситуациях, для поиска оптимальных маршрутов передачи данных в спутниковых системах и их валидации, а также в организационно-экономических системах. Наиболее широко для построения маршрутов применяются подходы теории графов и поиска в пространстве состояний, где любой траектории между объектами ставится свой вес. Однако до сих пор не существует универсальной системы, позволяющей построить оптимальный маршрут по пересеченной местности. В статье рассмотрены такие методы, как алгоритм Дейкстры, Левита, Флойда - Уоршелла, а также выполнено сравнение их эффективности по времени работы и вычислительной сложности. Целью является разработка алгоритма поиска кратчайшего пути и построения туристического маршрута от заданной точки А до точки Б, что откроет большие возможности для горожан самостоятельно посещать новые интересные районы, активно проводить свободное время и узнавать окрестности города. Система апробирована на территории Торгашинского хребта, включает более 38 точек маршрута, расположенных на расстоянии более 25 км, и позволяет построить желаемые маршруты в течение менее 15 мс с учетом перепада весов и расстояния между объектами. При этом система допускает ввод собственных координат, которые учитываются при построении маршрутов.