Файл: The shortest route search using roadgraph module for qgis geographic information system ishmukhametov R.pdf

16
THE SHORTEST ROUTE SEARCH USING ROADGRAPH MODULE FOR QGIS
GEOGRAPHIC INFORMATION SYSTEM
Ishmukhametov R.
ПОИСК КРАТЧАЙШЕГО МАРШРУТА C ПОМОЩЬЮ МОДУЛЯ
ROADGRAPH ДЛЯ ГЕОИНФОРМАЦИОННОЙ СИСТЕМЫ QGIS
Ишмухаметов Р. А.
Ishmukhametov R. THE SHORTEST ROUTE SEARCH USING ROADGRAPH MODULE FOR QGIS GEOGRAPHIC INFORMATION SYSTEM / Ишмухаметов Р. А. ПОИСК КРАТЧАЙШЕГО МАРШРУТА C ПОМОЩЬЮ МОДУЛЯ ROADGRAPH ДЛЯ ГЕОИНФОРМАЦИОННОЙ СИСТЕМЫ QGIS
Ишмухаметов Рустем Айдарович / Ishmukhametov Rustem – студент магистратуры,
кафедра математического моделирования, факультет математики и информационных технологий,
Стерлитамакский филиал
Башкирский государственный университет, г. Стерлитамак
Аннотация: задача о поиске кратчайшего пути на графе может быть интерпретирована по-
разному и применяться в различных областях. Одной из областей применения являются
картографические сервисы и различные геоинформационные системы, такие как QGIS, ArcGIS,
GRASS. Поиск кратчайшего пути в геоинформационной системе QGIS реализован при помощи модуля
Roadgraph, доступного по умолчанию при установке QGIS. В статье дается обзор модуля и его
применения для поиска кратчайшего пути на векторных картах OpenStreetMap.
Abstract: the problem of finding the shortest path in the graph can be interpreted in different ways and used in
various fields. One of the areas of application are various map services and geographic information systems,
such as QGIS, ArcGIS, GRASS. Find the shortest path to the QGIS geographic information system is
implemented by means module Roadgraph, available by default when you install QGIS. The article gives an
overview on the module and its application to search for the shortest path on vector maps of OpenStreetMap.
Ключевые слова: геоинформационные системы, графы, маршрут.
Keywords: geoformation systems, graph, route.
Неоспорим тот факт, что теория графов тесно связана со многими разделами математики. Одной из основных задач теории графов является задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь - задача о кратчайшем пути [1].
Поиск кратчайшего пути хорошо реализован в QGIS, свободной геоинформационной системе.
Roadgraph — расширение свободной ГИС с открытым исходным кодом Quantum GIS, позволяющее осуществлять поиск оптимального маршрута на заданном графе дорог. Этот модуль доступен по умолчанию при установке QGIS и его необходимо лишь активировать.
Рис. 1. Поиск кратчайшего пути в QGIS
В качестве слоя дорог можно использовать любой линейный векторный слой в формате, поддерживаемом QGIS. Две линии, имеющие общую точку, считаются связанными между собой, для примера возьмем shape файл OpenStreetMap.

17
Основные возможности расширения Roadgraph:

расчет маршрута, его протяженности и времени пути;

оптимизация по критерию расстояния или времени;

экспорт маршрута в векторный слой.
При использовании слоя дорог, в котором присутствуют артефакты в виде небольших разрывов между вершинами полилиний, необходимо установить «топологический порог». Топологический порог (или топологическая толерантность) — это расстояние между двумя соседними вершинами, при котором они интерпретируются как одна и та же вершина графа. Эта величина должна быть как можно меньше (чем меньше — тем лучше). Не стоит полагаться на параметр топологической толерантности как на панацею, лучше, если Ваши данные будут приведены к «правильному» виду.
В атрибутивной таблице слоя могут присутствовать и использоваться в работе расширения следующие поля:

скорость движения по участку дороги — числовое поле

направление движения — любой тип, приводимый к строке.
Модуль может правильно обрабатывать дороги с разным характером движения: одностроннее или двустороннее. Для этого необходимо, чтобы в атрибутивной таблице слоя присутствовало поле с указанием типа дороги. Его нужно выбрать в выпадающем списке «Поле направления» с настроек модуля и задать значения для прямого, обратного и двустороннего движения. Под прямым направлением понимается движение в порядке создания точек линии, от первой точки к последней.
Соответственно, обратное направление — это движение от последней точки линии к первой. Эти два варианта задают односторонние дороги [2].
Рис. 2. Настройки расширения Roadgraph
Если значение какого-либо поля не задано, или поле отсутствует — используется значение по умолчанию, изменить которое можно в настройках расширения.
Нажатие на кнопку «Рассчитать» запустит поиск кратчайшего маршрута с использованием критерия оптимизации, заданного выпадающим списком «Критерий».
Базовый функционал модуля вынесен в отдельную библиотеку network-analysis, что делает возможным использование алгоритмов сетевого анализа реализованных в модуле из Консоли Python
QGIS, а также в своих расширениях.
Литература
1. Евстигнеев В. А. Глава 3. Итеративные алгоритмы глобального анализа графов. Пути и покрытия //
Применение теории графов в программировании / Под ред. А. П. Ершова. Москва: Наука. Главная редакция физико-математической литературы, 1985. 352 с.
2. Documentation
QGIS
1.8.
[Электронный ресурс].
Режим доступа: http://docs.qgis.org/1.8/en/docs/user_manual/plugins/ plugins_road_graph.htm l/ (дата обращения:
22.12.2016).