УДК 519.233.5

ПРИМЕНЕНИЕ ТЕОРИИ ГРАФОВ В АНАЛИЗЕ ТРАНСПОРТНОЙ ИНФРАСТРУКТУРЫ АРКТИЧЕСКИХ И ПРИАРКТИЧЕСКИХ РЕГИОНОВ

Зеленина Лариса Ивановна1, Урыков Владислав Андреевич2
1Северный (Арктический) Федеральный Университет имени М.В.Ломоносова, кандидат технических наук, доцент кафедры Прикладной математики и высокопроизводительных вычислений Института математики, информационных и космических технологий
2Северный (Арктический) Федеральный Университет имени М.В.Ломоносова, студент, Институт Математики, информационных и космических технологий

Аннотация
В данной статье рассматривается процесс моделирования на основе теории графов транспортной инфраструктуры региона. На примере Архангельской области проводится анализ состояния транспортной сети и рассматривается целесообразность ее изменения.

Ключевые слова: алгоритм Дейкстры, моделирование транспортных потоков региона, теория графов


THE APPLICATION OF GRAPH THEORY IN THE ANALYSIS OF TRANSPORT INFRASTRUCTURE IN THE ARCTIC AND SUBARCTIC REGIONS

Zelenina Larisa Ivanovna1, Urykov Vladislav Andreevich2
1Northern (Arctic) Federal University named after M.V. Lomonosov, candidate of technical Sciences, associate Professor At Kladno mathematics and highly productive on calculations of the Institute of Math, information and space technologies
2Northern (Arctic) Federal University named after M.V. Lomonosov, student, Institute of Math, information and space technologies

Abstract
This article discusses the process of modeling based on graph theory transport infrastructure of the region. On the example of the Arkhangelsk region, the analysis of the status of the transport network and the feasibility of its changes.

Рубрика: 01.00.00 ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Зеленина Л.И., Урыков В.А. Применение теории графов в анализе транспортной инфраструктуры арктических и приарктических регионов // Современные научные исследования и инновации. 2015. № 8 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/08/56391 (дата обращения: 20.11.2016).

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

где – вершины графа. Если  совпадают, т.е.  то такое ребро называют петлей.
Если граф неориентированный, то множество  пар вершин может быть неупорядоченным, если же граф является ориентированным, то множество пар вершин упорядочено, обозначается буквой , а ориентированные ребра называют дугами. Каждая дуга обозначается так:

где – начало, а  – конец дуги.
Существуют смешанные графы  где  определены аналогично. В таких графах некоторые ребра могут быть как ориентированными, так и неориентированными.
Граф, в котором каждому ребру поставлено в соответствие некое значение, называется взвешенным. Это значение называют весом ребра. Чаще всего данное значение входит в множество вещественных чисел, в данном случае его можно интерпретировать как «длину» или «пропускную способность» соответствующего ребра.
Если ребро e соединяет две вершины u, v, то говорят, что ребро e и вершина u , а также ребро e  и вершина  v инцидентны. Две вершины, инцидентные одному ребру называются соседними или смежными. Ребра, инцидентные одной вершине, также называются смежными.
Существуют несколько способов представления графа:
– в виде таблицы, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке такой матрицы записывается число, указывающее на наличие связи от вершины-строки к вершине-столбцу. В случае взвешенного графа число равняется весу соответствующего ребра. Такую таблицу называют матрицей смежности;
– в виде таблицы, где строки соответствуют вершинам графа, а столбцы соответствуют его ребрам. Ненулевое значение в ячейке указывает на наличие связи между вершиной и ребром. В случае ориентированного графа в ячейку (i,j)ставится «1» в случае, если i является началом дуги j , «-1» если концом и «0» если связь между вершиной и ребром отсутствует. Такую таблицу называют матрицей инцидентности;
– в виде списка, где каждой вершине графа соответствует строка, в которой хранится список смежных вершин. Такую совокупность называют списком смежности;
– в виде списка, где каждому ребру графа соответствует пара вершин, инцидентных ребру. Такой список называется списком ребер.
Используя собранные данные по транспротной системе Архангельской области построим взвешенный граф и использовать алгоритм Дейкстры для обоснования рентабельности возможных проектов реализуем модель в Microsoft Excel. 
Алгоритм голландского ученого Эдсгера Дейкстры позволяет найти кратчайшие пути из одной изначально заданной вершины графа до всех остальных, так что его удобно использовать для задачи поиска оптимального маршрута. 
Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются минимальным расстоянием от вершины источника до конкретной вершины.
Главное ограничение данного алгоритма заключается в использовании исключительно положительных значений ребер, отрицательные веса приведут к некорректному решению. Т.к. весом ребер в модели являются расстояние или средняя скорость, отрицательных значений вес никогда не принимает, что означает, что данный алгоритм можно использовать.
Применительно к данной задаче, алгоритм Дейкстры не имеет существенных преимуществ или недостатков по сравнению другими алгоритмами, которые решают ту же задачу другими способами, например, алгоритмом Левита или алгоритмом Форда-Беллмана, так что на практике возможно использование любого из имеющихся алгоритмов.

Следует отметить, что результаты моделирования транспортной сети на примере Архангельской области были представлена авторами в виде взвешенного графа, где вершины – населенные пункты, а ребра – дороги, имеющие в качестве «веса» 2 параметра: протяженность веток и понижающий коэффициент, определяющий среднюю скорость передвижения.[5,6]

Рассмотрим проектирование дополнительных трасс в пределах рассматриваемого региона на примере трассы Архангельск (Мезень) – Нарьян-Мар

В данном случае речь идет о строительстве «с нуля» двухполосной асфальтированной трассы, т.к. на данный момент не существует ни железнодорожной, ни автомобильной, ни даже гравийной или грунтовой дороги, напрямую соединяющие Ненецкий автономный округ с остальной Архангельской областью (зимники не учитываются). Связь осуществляется через авиа и морской транспорт, что не может в полной мере компенсировать отсутствие транспортной инфраструктуры, особенно учитывая, что последний также недоступен зимой. Из-за высокой стоимости доставки продуктов в цены на них в заполярном городе являются одними из самых высоких в стране, так что необходимость автомобильной дороги очевидна. 
Автомобильная трасса, соединяющая с областным центром через Мезень, позволила бы избавить Ненецкий автономный округ от изолированности, стать толчком для развития региона и заметно улучшить уровень жизни населения.
Второй рассматриваемый проект – это асфальтирование автодорожных веток Северодвинск – Онега и Онега – Плесецк
Асфальтовая дорога между Северодвинском и Онегой позволила бы увеличить пропускную способность (и среднюю скорость движения) между Онегой и двумя крупными городами — Архангельском и Северодвинском, исключив пробки и заметно развив транспортную инфраструктуру региона, а дорога Онега–Плесецк позволила бы к тому же соединить два важнейших военных объекта друг с другом, что также важно в нынешней непростой политической обстановке.
Следует отметить, что среднее время в пути среднестатистического грузового автомобиля по маршруту Северодвинск-Онега-Плесецк при соблюдении всех правил по сравнению с нынешним оптимальным маршрутом Северодвинск-Архангельск-Плесецк [5,6] уменьшится чуть менее чем на 25% (рис. 1).

Рисунок 1 –  Граф автомобильных дорог с учетом проектов

Определим матрицу смежности графа (с учетом рассматриваемых проектов):

Таблица 1 – Матрица смежности графа (в час.)

Матрица смежности

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Мезень

1

-

-

12,83

-

-

-

-

-

-

-

-

-

-

7,94

Северодвинск

2

-

-

1,00

2,62

-

-

-

-

-

-

-

-

-

-

Архангельск

3

12,83

1,00

-

-

4,76

7,69

-

-

-

-

-

-

-

-

Онега

4

-

2,62

-

-

-

3,90

-

-

-

-

-

-

-

-

Березник

5

-

-

4,76

-

-

6,88

1,78

-

-

0,16

-

-

-

-

Плесецк

6

-

-

7,69

3,90

6,88

-

-

-

0,07

-

-

-

-

-

Шенкурск

7

-

-

-

-

1,78

-

-

4,67

-

-

2,54

-

-

-

Няндома

8

-

-

-

-

-

-

4,67

-

1,45

-

3,97

2,68

-

-

Каргополь

9

-

-

-

-

-

3,84

-

1,45

-

-

-

-

-

-

Котлас

10

-

-

-

-

8,23

-

-

-

-

-

-

-

0,65

-

Вельск

11

-

-

-

-

-

-

2,54

3,97

-

-

-

3,54

-

-

Коноша

12

-

-

-

-

-

-

-

2,68

-

-

3,54

-

-

-

Коряжма

13

-

-

-

-

-

-

-

-

-

0,65

-

-

-

-

Нарьян-Мар

14

7,94

-

-

-

-

-

-

-

-

-

-

-

-

-

Значения матрицы смежности, с которой будет работать макрос в M.Excel, зависят от выбранного транспорта и коэффициента для соответствующего ребра (рисунок 2).

  

 

Рисунок 2 -  Таблица коэффициентов

            Результаты реализации разработанной модели транспортной инфраструктуры региона [5,6] с учетом новых проектов представлены на рисунке 3:

 Рисунок 3 – Расчет времени в MS Excel для грузовиков с учетом дополнительных веток

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


Библиографический список
  1. Домнин Л.Н. Элементы теории графов: учеб. Пособие. Изд-во Пенз. Гос. Ун-та, 2007. – 144 с.
  2. Швецов В.И. Математическое моделирование транспортных потоков: Автоматика и телемеханика 2003.
  3. Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Введение в математическое моделирование транспортных потоков: Учебное пособие / Под редакцией Гасникова А.В. – М.: МЦНМО, 2012.
  4. Урыков В.А., Зеленина Л.И. Математические модели транспортных потоков // Современная техника и технологии. 2015. № 6 [Электронный ресурс]. URL: http://technology.snauka.ru/2015/06/6051 (дата обращения: 17.06.2015).
  5. Зеленина Л.И., Урыков В.А. Моделирование транспортной инфраструктуры и развитие сельского хозяйства приарктических регионов // Сельское, лесное и водное хозяйство. 2015. № 6 [Электронный ресурс]. URL: http://agro.snauka.ru/2015/06/2461 (дата обращения: 02.07.2015).
  6. Зеленина Л.И., Урыков В.А. Моделирование транспортной инфраструктуры приарктических регионов // Исследования в области естественных наук. 2015. № 6 [Электронный ресурс]. URL: http://science.snauka.ru/2015/06/10204 (дата обращения: 01.07.2015).


Все статьи автора «Зеленина Лариса Ивановна»


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

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться:
  • Регистрация