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

Полный текст

Введение

На сегодняшний день актуальна тема поддержания здорового образа жизни. Люди стремятся следить за своим здоровьем, занимаются спортом, а также путешествуют. Они постоянно находятся в поиске различных мест посещения. Красноярский край обладает очень богатой природой. В нашем городе существует проект «Красноярский Хайкинг», который представляет собой сеть промаркированных троп на территории Торгашинского хребта. Появилось множество граждан, желающих сходить в поход как в окрестностях своего города, так и вне городской местности. Существует множество источников, где можно найти справочную информацию о местах посещения и общие тропы, однако, до сих пор нет возможности создания своего индивидуального маршрута по пересеченной местности с оптимальным для конкретного человека треком. Для разработки такой системы, которая бы позволила в автоматизированном режиме строить свои собственные маршруты по выбранным местам посещения с использованием данных gps-навигации, необходимо разработать собственный алгоритм, позволяющий построить кратчайший маршрута от точки А до точки Б.

Задача построения туристического маршрута сводится к задаче поиска кратчайшего пути от одной вершины графа до другой [1]. Данная проблема является одной из самых популярных задач в теории графов. Граф представляет собой абстрактный объект из множества вершин (узлов) и набора ребер, описывающих связи между парами вершин. Маршруты, которые состоят из связанных между собой перекрестков, являются графом.

Методы построения маршрутов применяются на практике в различных сферах. В работе [2] рассмотрены подходы, связанные с разработкой технологии для комплексной обработки данных дистанционного зондирования и векторных карт с целью мониторинга последствий чрезвычайных ситуаций, выявления критичных территорий и предотвращения негативных последствий. Авторы [3] рассматривают применение дискретного алгоритма решения SOTA (Self-organizing Tree Algorithm) и его параллельной версии с применением CUDA при построении надежного кратчайшего пути с использованием возможностей видеокарт. В работе [4] авторами разработана модификация дискретного алгоритма нахождения маршрута движения в зависящей от времени транспортной сети. Авторы демонстрируют эффективность предлагаемого подхода на примере крупномасштабной дорожной сети Самары и достигают скорости построения эффективного маршрута менее 1 с. Также методы построения маршрутов применяются для передачи данных в спутниковых [5], организационно-экономических системах [6], для мониторинга состояния лесов при организации спутникового наблюдения [7; 8] и в других областях данных. В статье рассмотрены различные методы построения маршрутов и предложена эффективная реализация модификации метода Дейкстры для построения туристических маршрутов на территории Торгашинского хребта.

Методы построения маршрутов

Классическая проблема поиска кратчайшего пути в открытой местности была направлением большого числа исследований на протяжении многих лет. В связи с этим существует большое количество различных алгоритмов нахождения пути, многие из которых показывают хорошие результаты в своей области. Исследователи в работе [9] выполнили оценку эффективности 15 алгоритмов поиска кратчайшего пути в реальных дорожных сетях. Авторы рассматривают алгоритмы Беллмана – Форда – Мура, алгоритм Дейкстры и его модификации, алгоритм Пейпа – Левитта и другие. На основе оценки определен набор рекомендуемых алгоритмов для вычисления кратчайших путей в реальных дорожных сетях. Также широко известен алгоритм A* [10], который направлен на уменьшение времени поиска оптимального маршрута за счет исключения менее перспективных направлений поиска на базе алгоритма Дейкстры. Модификации алгоритма Дейкстры применяются во многих практических задачах, например поиск кратчайшего маршрута для туризма в Бали [11]. Рассмотрим наиболее подробно такие алгоритмы, как алгоритм Дейкстры, алгоритм Левита и алгоритм Флойда – Уоршелла.

Алгоритм Дейкстры – один из самых известных алгоритмов для поиска кратчайшего пути [12]. Он позволяет определить кратчайшие пути между вершинами. Реализация заключаетсяв том, что алгоритм на каждом шаге «посещает» одну вершину и пытается уменьшить метки. Работа алгоритма завершается, когда все вершины посещены. У алгоритма Дейкстры имеется ряд достоинств, таких как высокая скорость работы и точность результата. Однако есть и недостаток – сложность в понимании. Вычислительная сложность алгоритма Дейкстры зависит от способа нахождения вершины, хранения множества непосещенных вершин и обновления меток. Отсюда получаем, что реализация в данном методе потребует O(N) и O(1) единиц соответственно. Учитывая, что первая операция выполняется N раз, а вторая в зависимости от построенного графа, получается сложность O(N×N+M), где N – количество вершин, а M – константа, зависящая от построенного графа.

Алгоритм Левита – алгоритм на графах, который находит кратчайшее расстояние от одной из вершин графа до всех остальных [13]. Он также работает для графов с ребрами отрицательного веса. В сравнении с методом Дейкстры метод Левита проигрывает в том, что некоторые вершины приходится обрабатывать повторно, а выигрывает на более простых алгоритмах включения и исключения вершин из множества М1 (М1 – вершины, расстояние до которых вычисляется на текущем шаге алгоритма). Установлено, что для графов с «геометрическим» происхождением, построенных на основе транспортных сетей и реальных расстояний, метод Левита оказывается наиболее быстрым. Помимо этого, он выигрывает и по размеру программы. Сложность алгоритма Левита в худшем случае составляет O(N² × M).  Чтобы достичь такого времени работы необходимо, чтобы в графе ребра располагались в лексикографическом порядке. Более реальной оценкой данного метода является среднее время, а именно сложность O(N × M). Однако на реальных графах алгоритм Левита лишь немногим уступает алгоритму Дейкстры.

Алгоритм Флойда – Уоршелла используется для нахождения кратчайших расстояний между всеми вершинами взвешенного графа без циклов с отрицательными весами с использованием метода динамического программирования [14]. В алгоритме используются две матрицы смежности: матрица расстояний D_k и матрица предшествования S_k, после чего, в течение n итераций, где n – количество узлов в матрице расстояний, а n-я итерация, дается оптимальная / конечная матрица расстояний D_k = n, а также окончательная матрица предшествования S_k = n.

Недостаток алгоритма Флойда – Уоршелла в том, что алгоритм определяет только кратчайшее расстояние между всеми парами вершин, но не сохраняет информацию о кратчайших путях, что необходимо для задач построения маршрута.

По итогу рассмотрения наиболее важных алгоритмов для получения кратчайшего пути в графе, а также анализу их преимуществ и недостатков, обозначим требования, которые необходимы для реализации поиска кратчайшего пути в трехмерном пространстве на территории Торгашинского хребта:

Проведенный анализ показал, что для поиска кратчайшего пути в трехмерном пространстве на территории Торгашинского хребта целесообразно использовать алгоритм Дейкстры, так как он учитывает особенности рассматриваемого процесса. Основными достоинствами алгоритма Дейкстры является высокая скорость работы и точность результата [15].

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

Прежде чем переходить к пошаговому описанию, рассмотрим схему работы алгоритма построения маршрутов по пересеченной местности на территории Торгашинского хребта (рис. 1).

 

Рис. 1. Схема разработанного алгоритма построения оптимального пути

Fig. 1. Scheme of the developed algorithm for constructing various paths

 

В программной реализации существует двенадцать gpx-треков (свободный текстовый формат хранения и обмена данными GPS) уже существующих маршрутов на территории Торгашинского хребта. Для того чтобы извлечь всю необходимую информацию из данных треков, применяется библиотека minidom, которая позволяет проанализировать xml-разметку и выбрать необходимую информацию [16].

Все треки находятся в соответствующей папке tracks. При проходе циклом по этой папке, выполняется посещение каждого маршрута и в соответствующие поля записывается следующая информация: название маршрута, цвет прорисовки и координаты каждой точки маршрута в формате широта, долгота и высота.

В словаре vocab ключам в виде названия маршрута задаются соответствующие gpx-треки. Далее по этому словарю формируется список названий маршрутов и создаются словари: индексы для точек пересечения и графа (distances), список вершин (nodes). Кортежами задаются начальная (st) и конечная (en) точки маршрута для составления нового маршрута – они состоят из координат по y и x – затем они записываются в словарь point.

При проходе циклом по vocab, выполняется проверка условия, являются ли точки st и en начальными или конечными точками существующих маршрутов и в таком случае они удаляются из списка point – этот список позволяет определить требуется ли создавать новые вершины графа для корректной работы алгоритма Дейкстры.

Следующим этапом является создание графа маршрутов и их пересечений. Для этого необходимо соотнести каждый маршрут со всеми остальными, чтобы определить есть ли пересечения, в случае нахождения пересечений зафиксировать их. Создаются списки по каждому маршруту, содержащие соответственно x₁, y₁ и z₁ координаты для первого маршрута и x₂, y₂ и z₂ координаты второго маршрута. Проходя циклом по точкам списков x₁ и x₂, определяется расстояние между точкам. Если это расстояние меньше минимального, то перезаписывается минимальное расстояние на новое и сохраняются индексы найденных точек. Если же маршруты пересекаются, определяется среднеарифметическая точка пересечения (x, y, z). Данный метод позволяет найти точку пересечения маршрута, если gpx-треки не пересекаются, а проходят очень близко друг к другу.

Для нахождения расстояния между двумя точками необходимо изучить форму Земли. Форма Земли может быть описана как сфера, поэтому уравнения для вычисления расстояний на большом круге важны для вычисления кратчайшего расстояния между точками на поверхности Земли и часто используются в навигации [17].

Вычисление расстояния этим методом более эффективно и во многих случаях более точно, чем вычисление его для спроектированных координат, поскольку, во-первых, для этого не надо переводить географические координаты в прямоугольную систему координат и, во-вторых, многие проекции, если неправильно выбраны, могу привести к значительным искажениям длин в силу особенностей проекционных искажений.

Для вычислений используется сфера радиусом 6372795 м, что может привести к меньшей ошибке, чем если считать в прямоугольных системах координат.

Согласно сферической теореме косинусов:

$\mathrm{\Delta }\sigma ={\sin }^{-1}\left\{\sin {\varphi }_1\times \sin {\varphi }_2+\cos {\varphi }_1\times \cos {\varphi }_2\times \mathrm{cos\Delta }\lambda \right\},$                                                       (1)

где ${\varphi }_1,{\lambda }_1,{\varphi }_2,{\lambda }_2$ – широта и долгота двух точек в радианах;  – разница координат по долготе;  – угловая разница.

Для перевода углового расстояния в метрическое, необходимо угловую разницу умножить на радиус Земли, единицы конечного расстояния будут равны единицам, в которых выражены метры.

Описанный метод реализован в функциях: Lenfor и Meters. Функция Lenfor – функция, рассчитывающая длину пути между точками маршрута по x и y без учета высоты, и функция Meters – функция, рассчитывающая расстояние между точками gps-координат с учетом перепада высот, после вычисления расстояния функцией Lenfor.

Алгоритм Дейкстры позволяет определить кратчайшие пути между вершинами. В данной реализации принцип этого алгоритма используется для определения весов ребер, нахождения кратчайшего пути и составляет его из частей gpx-треков. Алгоритм Дейкстры поэтапно формулируется следующим образом:

Шаг 1: задать начальную и конечную точку маршрута.

Шаг 2: создать словарь непосещенных вершин – unvisited, словарь путей до каждой вершины – way, словарь посещенных вершин – visited.

Шаг 3: цикл, пока есть непосещенные вершины. Иначе шаг 10.

Шаг 4: если есть соседи в unvisited, то новый вес пути (newDistance) = текущий вес пути (currentDistance) + вес между вершинами (distance). Иначе шаг 3.

Шаг 5: значение unvisited – список? Если да, взять первое значение списка: dist = dist[0]. Иначе unvisited[neighbour] = newDistance, newPath (новая часть пути).

Шаг 6: записать в словарь путей newPath. А в visited для текущей вершины записать currentDistance.

Шаг 7: удалить текущую вершину из unvisited.

Шаг 8: сформировать кандидатов для новой текущей вершины. Отсортировать newDistance по возрастанию. Получаем новую текущую вершину (path) = currentDistance[1] и текущий путь до нее (currentDistance) = currentDistance[0].

Шаг 9: newPath = path + current (текущая ячейка).

Шаг 10:      получен заполненный словарь путей из стартовой точки.

Шаг 11:      выбрать искомый маршрут по ключу конечной точки.

Шаг 11:      определить какому маршруту принадлежит очередная пара вершин.

Шаг 12:      если индекс начальной точки (lost) > индекса конечной точки (next), копировать эту часть трека. Иначе, идти в обратную сторону трека.

Шаг 13:      собрать оптимальный gps-трек, по заданным точкам.

Экспериментальные исследования

В качестве примера рассмотрим один из вариантов построения маршрута, где начальная точка – гора Тамара с координатами 55.952562 и 92.857231, находящаяся на маршруте «Здоровье», а конечная точка – 2-я Торгашинская видовка с координатами 55.919239 и 92.889939, находящаяся на маршруте «Болгаш». Рассмотрим визуализацию маршрута на рис. 2 (отображен розовым цветом).

 

Рис. 2. Визуализация построенного маршрута

Fig. 2. Visualization of the constructed route

 

На рис. 2 С.Ш. – северная широта, а В.Д. – восточная долгота. Наблюдаем 13 маршрутов разных цветов, расшифруем слева направо: красный – Тропа «Здоровье», фиолетовый – Тропа «Лыжная», зеленый – тропа «Мокрый лог», розовый – построенный маршрут по указанным точкам, оранжевый – тропа «Рыжая», зеленый – тропа «Синильга», желтый – тропа «Сквозная», синий – тропа «Сивая», фиолетовый – тропа «Топ», оранжевый – тропа «Болгаш», коричневый – тропа Спелеологов, фиолетовый – тропа «Кузнецово», синий – тропа «Сказка».

Помимо визуализации, алгоритм построения туристических маршрутов вычисляет длину нового маршрута, максимальную и минимальную высоту на протяжении всего трека и время построения. Таким образом, по построенному маршруту получено: длина маршрута = 10676 м, максимальная высота = 584,53 и минимальная высота = 179,76. На текущий момент в программной системе имеется 38 различных объектов Торгашинского хребта, что охватывает более 95 % точек посещения туристами. При этом алгоритм (система) допускает ввод собственных координат, которые учитываются при построении маршрутов. В таблице приведены характеристики некоторых построенных маршрутов.

 

Примеры построенных маршрутов и их характеристики

	Время построения, с	Расстояние, м	Перепад высот, м
От Тамара до 2-й Торгашинской видовки	0,005457	10 676	404,77
От ск. Сивые до Черной сопки	0,005655	21 642	376,68
От Синильга до Луч	0,004734	10 555	404,77
От СНТ «Загорье-1» до пещ. Мокрая	0,005604	6 371	381,67
От ск. Пропасть до ск. Красный гребень	0,013433	4 188	229,81
От ск. Магда до СНТ «Загорье-2»	0,003422	9 849	266,07

 

Заключение

В результате работы разработан алгоритм построения кратчайшего маршрута от начальной до конечной точки, основанный на алгоритме Дейкстры, позволяющий получить оптимальный gpx-трек, а также имеющий базу существующих маршрутов. Алгоритм применяется в программной системе, реализованной в виде web-сайта и мобильного приложения, который позволяет туристам построить удобные маршруты для посещения Торгашинского хребта. В системе имеется 38 туристических объектов, и построение любого маршрута занимает в среднем 15 мс.

Об авторах

Диана Андреевна Крутько

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

Автор, ответственный за переписку.
Email: krutko.d00@gmail.com

студентка группы БПИ18-01

Россия, 660037, Красноярск, проспект имени газеты «Красноярский Рабочий», 31

Алексей Сергеевич Калашников

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

Email: fangy.ko@gmail.com

студент группы А17-02

Россия, 660037, Красноярск, проспект имени газеты «Красноярский Рабочий», 31

Владимир Викторович Буряченко

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

Email: buryachenko@sibsau.ru

кандидат технических наук, доцент

Россия, 660037, Красноярск, проспект имени газеты «Красноярский Рабочий», 31

Список литературы

Дополнительные файлы