Использование графов для сетевого анализа в среде ArcMap

Размещено на http://www.allbest.ru/

Ошский технологический университет им. акад. М.М. Адышева

Использование графов для сетевого анализа в среде ArcMap

Кадыркулова Н.К., Мамат уулу Т.

Аннотация

Появление мощных и быстродействующих компьютерных технологий привело к широкому внедрению ГИС в разные области. Современные ГИС позволяют быстро решать задачи по математическому анализу сетевых данных. Эта работа направлена на рассмотрение возможностей использования модулей ГИС в этой области. Актуальность статьи -- использование графов для разработки сетевого анализа в среде ArcMap.

Ключевые слова: геоинформационные системы, граф, сетевой анализ, карты, АркМап.

Abstract

USING GRAPHS FOR NETWORK ANALYSIS IN ARCMAP ENVIRONMENT

The emergence of powerful and fast computer technologies has led to the massive adoption of GIS in various fields. Modern GIS make it possible to quickly solve such problems in the mathematical analysis of network data. This work aims to limit the use of GIS modules in this area. The relevance of the article is the use of graphs to develop network analysis in the ArcMap environment.

Keywords: geographic information systems, graph, network analysis, maps, ArcMap.

Дорожная отрасли являются одной из самых важных отрасли экономики любого промышленно развитого страна. Автомобильные дороги не зря называют «кровеносной системой» любого государства. Они сыграли огромную социальную и экономическую значимость в жизни современных обществ. В Киргизской Республике из-за огромной территориальной протяженности транспортные расходы значительно выше среднемировых. Автодороги -- это очень капитальные, но и весьма рентабельные сооружения [3].

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

Проблема поиска маршрутов в городской сети города Кыргызстана становится все более актуальной. За последние десятки лет исследуют и формируют вопросы построения оптимальных маршрутов транспортных средств. Вводятся неизвестные решения, которые ранее были не известны, а также улучшаются методики решения проблем. Решение данных проблем позволяет осуществлять такой метод расчета маршрутов автомобилей, чтобы обеспечить транспортную маршрутизацию с минимальными затратами материального ресурса. Основной концепцией геоинформационных ГИС является взаимосвязь сведений базы и карт. ГИС является и аналитическим ресурсом, который может работать с каждой координатной связью. В принципе ГИС может анализироваться точно так же, как развитая концепция баз данных. В этом значении ГИС практически представляет собой другую ступень и способ интеграции данных и их структурирования. ГИС позволяет совершенно развивать и формировать картографию. Один из ключевых недостатков обыкновенной карты -- неподвижность карт и ограниченность их вместимости как носителя данных.

ГИС рассматривается как класс информационных режимов с собственными особенностями. Они построены в соответствии с закономерностями геоинформации и методами, используемыми в этой области. В качестве интегрированных и информационных систем ГИС предусматривается для решения различных проблем в науке и использовании на основе использования пространственно-локализованных данных об объектах и явлениях окружающего мира. Одна из более расширенных возможностей современного общедоступного ГИС -- возможности решения определенного перечня задач на коммуникационных графах и дорожных сетях. Такое требование в основном выдвигают пользователи, работающих напрямую с доставкой и перевозкой грузов. Эта работа предназначена для рассмотрения возможностей применения модулей ГИС в данной области. Представление сети дорожного движения в виде графы с картографическими данными предполагает следующие задачи при решении транспортных проблем: проводить эксперимент по вычислению, получение результатов, соответствующих реальным условиям; ознакомиться с информацией о дорожном состоянии; оценивать время выполнения решений данного алгоритма и метода; проводить эксперименты с развертыванием задачи в ЭВМ. сетевой геоинформационный маршрутный

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

Географические информационные системы (ГИС) -- это увлекательное поле деятельности с быстро растущими возможностями для тех, кто знаком с концепциями и технологией. Существует общее заблуждение, что так как ГИС легко доступны и есть во многих организациях, можно только сесть за компьютер и начинать пользоваться ими. Впрочем, ГИС не так просты, как, к примеру, текстовый редактор. Также, как и использование текстового редактора предполагает, что мы можем организовать наши мысль в связной последовательности предложения и абзацев, также ГИС требует знаний языка карт. Привычно мы используем дороги, а если нужно, глядим на атлас мировой политической, физической, экономической границы, связанные с ними цвета, графические символы, текст и, разумеется, стрелка направления в север. Впрочем, большинство из нас не задумываются ни об объёме информации, содержащейся в карте, ни об обобщениях, которые происходят при решения вопроса, в каких деталях входят, а в каких нет. Большая часть этого генерализации зависит от масштаба карт. Чем меньше масштаб и меньше размеры области, отображаемой на карте, тем глубже требуется генерализация для того, чтобы создать картографическую модель. Идея, что карта -- это модель реальности, может быть самым важным для будущего специалиста по ГИС [2].

Таким образом, высокое значение имеет разработка и программная реализация алгоритмов для анализа существующей дорожной сети города и определения оптимальных маршрутов движения с разных сторон. Основная цель этой работы -- использование графов для сетевого анализа в среде ArcMap. Создавая различные информационные системы, относящиеся к атласам дорог, маршрутным схемам, техническим схемам устройств, организационным схемам управления, при решении задач сетевой планировки неизбежно возникает необходимость обращаться к графам. Граф позволяет решать множество вопросов: найти наиболее оптимальный маршрут в карте дорог, рассчитать минимальное время для выполнения критического пути, определить, какие элементы должны быть выпущены из строя для отключения всего механизма и так далее. Графы представляют собой важный элемент математической модели в самых разных науках и практиках. Они способствуют наглядному представлению взаимоотношений между объектами и событиями сложных систем. Термин «граф» неоднозначен. Это можно заметить сравнив приводимые определения в различных книгах. Впрочем, во всех указаниях есть что-то общее. Во всяком случае, в графе два множества: множество вершин, много ребер, а для каждой вершины указывается пара верешков, которые являются ребрами. Граф G будет называться парой (V(G), E(G)), в которой V(G) -- является непустым конечным множеством элементов, которые называются вершинами и E(G)- является конечным множеством элементов, которые называются ребрами.

Рассмотрим только конечные графы, т е. такие, где оба множества конечны. Вершины и ребром графа будем называть его элементы. Множество вершин графа G будут обозначены через VG, множество ребер -- EG, число вершин -- n(G), число ребер -- m(G). Графические примеры можно найти в разных науках и практиках. В сетях дорог, труб, электрических цепей, структурной формуле химических соединений, блок-схеме программы возникают графы естественным образом и видно «невидимым глазом».

В математике много причин для возникновения графов. Наиболее явным примером является любая многогранность в трехмерном пространстве. Вершина и ребра многогранника могут быть рассматриваться как вершины и ребра графа. В этом случае мы не будем обращать внимания на расположение многогранных элементов в пространстве, оставив только информацию, какие вершины соединены с ребрами. Если у графа есть ребро e=(a, b), то говорится, что в графе смежны вершины a и b, вершина e случайна каждой вершине a, b, и каждая из которых случайна в этом ребре.

Многочисленные все вершины графа, относящиеся к этой вершине а, называются окрестностями вершины а и обозначены через V(a). Число смежных вершин a, относящихся к вершине а, называется по степени вершины а и обозначается через deg(a).

Ориентированный граф орграф называется парой G=(V, E), где V -- конечный набор, Е -- многочисленные упорядоченные пары разных элементов в V. Впоследствии будем использовать термин «граф» как «обычный граф», а при рассмотрении других типов графов будем оговорить это специально. Для того чтобы задать обыкновенный граф достаточно перечислите его вершины и ребра, каждое ребро представлена парой вершин. Положим, например, VG={a, b, c, d, e, f}, EG={(a,c), (a,f), (b,c), (c,d), (d,f)}.

Таким образом, задан граф G с n(G)=6, m(G)=5. Если граф не слишком большой, то его нагляднее представить можно при помощи рисунка, в котором вершины изображены кружками или другими значками, ребра -- линиями, связующими вершины. При создании дорожки следует учитывать, что направления движения в создаваемом участке дорожки совпадают с порядком создания дороги: от первого перекрестка до конца. На карте отображается найденный путь, а на панели слева выводится его характеристика: длина пути, количество километров пути, рассчитанное время проезда в среднем 60 км/ч; характеристики работы алгоритмов: время и число просмотренных пунктов; и вывод найденного маршрута движения в форме списка дорог по порядку проезда на них [4] (Рисунок 1).

Рисунок 1. Поиск маршрута Западный-ОшТУ

Перед тем, как приступить к созданию сетевого набора, нужно внести информацию по затратным единицам в таблицу атрибутов (Рисунок 2). В анализируемом слое должны быть следующие минимальные показатели атрибутивного состава для каждой области: длину, время прохода, скорость, название дорог и улиц допускается нулевыми значениями.

Доступ к свойствам анализа сетей осуществляется через диалоговое окно Свойства слоя, открывшееся в окне анализа сетей. Основная вкладка -- Настройки анализа. Здесь можно установить главные параметры, необходимые для выполнения задач:

импеданс -- это параметр, обычно, времени или расстояния, который необходимо минимизировать при расчетах маршрута;

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

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

развороты по перекресткам -- определение разрешенных вариантов разворота: любое положение, перекресток и тупик, только перекресток, без перекрестков; тип выходных форм -- определение отображения итогового маршрута;

иерархия -- при включении этой опции приоритет уделяется дорогам высшего класса;

игнорирование недействительных мест -- при включении этой опции недействительные месты сети отбросаются из анализа;

ограничения -- список ограничения поездок, учитываемых при анализе;

направление -- настроить создание справок по стоимости поездки.

Рисунок 2. Называние остановки по маршрутам

На вкладке «Агрегация» отметить атрибут, например длина маршрута, который поможет анализировать полученные результаты (Рисунок 3).

Рисунок 3. Граф дорог г. Ош

Набор сетей, являющийся графом дорог, создается внутри геоданных базы в одном классе с линейным темой дорог. С помощью модуля ArcCatalog создается сетевой набор. Мастер настройки задаёт основные конфигурации и характеристики сетей. Граф дороги в среде ArcGIS строится по линейному слою дорог и включает 3 типа элемента: ребра (Edges) -- это сегменты линейные; соединения (Junctions) -- это точечные соединения; повороты (Turns) -- это линейные объекты, которые моделируют правила поворачивания.

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

Стоимость (Cost) -- суммирует значения по элементам. хотя бы один параметр стоимости пути или времени.

Признак (Descriptor) -- содержит общую сведения, например названия улиц и дорог.

Иерархия (Hierarchy) -- делит сеть, прежде всего, для ускоренного анализа сетей.

Ограничение (Restriction) -- обычно ограничивает определенные перемещения элементов сетевого блока, но также может быть установлено предпочтение или отсутствие элемента.

ГИС -- является оптимальной платформой для решения сложных транспортных задач. Системы транспорта с их распределением территорий являются идеальными объектами автоматизации с геоинформационными системами. Особенностью использования ГИС и разработки алгоритмов поиска маршрутов в городской улице является современное и эффективное решение задач. Дальнейшее расширение возможностей геоинформационной системы может быть осуществлено за счет реализации работы с результатами поиска, добавления дополнительных атрибутов дорог и формирования на их основе новых критериев поиска.

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

1. Справочная энциклопедия дорожника (СЭД). Т 1: Строительство и реконструкция автомобильных дорог. Т 1. 2005. 646 с.

2. Симонова А. В. Геоинформационные системы и Интернет. Ярославль: Издательский дом ЯГТУ, 2018. 55 с.

3. Капралов Е. Г., Кошкарев А. В., Тикунов В. С.Основы геоинформатики. М.: Академия, 2004. 352 с.

4. Кадыркулова Н. К. Алгоритм поиска и оптимизация маршрутов движения в уличнодорожной сети города с использованием ГИС-технологий // Известия Ошского технологического университета. 2015. №2. С. 82.

5. ДеМерс М. Географические информационные системы. М.: Дата+, 1999. 490 с.

6. MapInfo Professional. New York, 2000. 760 с.

7. Upton G., Fingleton B. Spatial data analysis by example. V. 1: Point pattern and quantitative data. John Wiley & Sons Ltd., 1985.

References

1. Spravochnaya entsiklopediya dorozhnika (SED) (2005). 1: Stroitel'stvo i rekonstruktsiya avtomobil'nykh dorog. (in Russian).

2. Simonova, A. V. (2018). Geoinformatsionnye sistemy i Internet. (in Russian).

3. Kapralov, E. G., Koshkarev, A. V., & Tikunov, V. S. (2004). Osnovy geoinformatiki. Moscow. (in Russian).

4. Kadyrkulova, N. K. (2015). Algoritm poiska i optimizatsiya marshrutov dvizheniya vulichno-dorozhnoi seti goroda s ispol'zovaniem GIS-tekhnologii. Izvestiya Oshskogo tekhnologicheskogo universiteta, (2), 82. (in Russian).

5. DeMers, M. (1999). Geograficheskie informatsionnye sistemy. Moscow. (in Russian).

6. MapInfo Professional (2000) New York, 760 с.

7. Upton, G., & Fingleton, B. (1985). Spatial data analysis by example. Volume 1: Point pattern and quantitative data. John Wiley & Sons Ltd.

Размещено на Allbest.ru