УДК 519.233.5

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

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

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

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


MODELING OF THE TRANSPORT INFRASTRUCTURE OF THE ARCTIC REGIONS

Urykov Vladislav Andreevich1, Zelenina Larisa Ivanovna2
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 of the
2Northern (Arctic) Federal University named after M.V. Lomonosov, student, Institute of Math, information and space technologies of the

Abstract
In this paper attention is paid to the modeling process of road infrastructure on the example of the Arkhangelsk region. In particular, based on the Dijkstra's algorithm is considered program that offers drivers the optimum, from the point of view of minimization of travel time, route.

Рубрика: Математика

Библиографическая ссылка на статью:
Зеленина Л.И., Урыков В.А. Моделирование транспортной инфраструктуры приарктических регионов // Исследования в области естественных наук. 2015. № 6 [Электронный ресурс]. URL: http://science.snauka.ru/2015/06/10204 (дата обращения: 04.05.2017).

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

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

 

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

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

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

Таблица 1 – матрица смежности графа сети для грузовиков

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Мезень

1

-

-

12,83

-

-

-

-

-

-

-

-

-

-

-

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

2

-

-

1,00

4,68

-

-

-

-

-

-

-

-

-

-

Архангельск

3

12,83

1,00

-

-

4,76

7,69

-

-

-

-

-

-

-

-

Онега

4

-

4,68

-

-

-

6,97

-

-

-

-

-

-

-

-

Березник

5

-

-

4,76

-

-

6,88

1,78

-

-

0,16

-

-

-

-

Плесецк

6

-

-

7,69

6,97

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

-

-

-

-

-

-

-

-

-

-

-

-

-

-

 

 

 

 

 

 

 

 

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

 

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

На рабочем листе имеются два раскрывающихся списка, с помощью которых выбираются пункты отправления и прибытия (рисунок 3).

 

Рисунок 3. Использование списка для выбора пунктов отправления и прибытия

Матрицы смежности, с которыми работает макрос, в зависимости от положения переключателя выбирают соответствующие диапазоны: Graph1 и Vertex1 при выборе модели с дополнительными ребрами и Graph2 и Vertex2 в ином случае. Graph1 и Graph2 – обозначение диапазона соответствующих значений матрицы смежности, а Vertex1 и Vertex2 – обозначение множества соответствующих имен вершин (рисунок 4).

Рисунок 4. Диспетчер имен в MS Excel

При нажатии на кнопку запускается макрос и выдается оптимальный маршрут и примерное время в пути (выводится в часах и минутах).

 
Рисунок 5. Пример расчета времени в MS Excel для выбранного маршрута


Библиографический список
  1. Домнин, Л.Н. Элементы теории графов: учеб. Пособие. Изд-во Пенз. Гос. Ун-та, 2007. – 144 с.
  2. Семенов В.В. Математическое моделирование динамики транспортных потоков мегаполиса.  – М.: Институт прикладной математики им. М.В. Келдыша, 2004. - 44 с.
  3. Швецов В.И. Математическое моделирование транспортных потоков: Автоматика и телемеханика 2003.
  4. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структуры данных: Учебник. – Нижний Новгород: Изд-во ННГУ, 2005. 307 с.
  5. Демидова Л.А., Пылькин А.Н. – Программирование в среде Visual Basic for Applications: Практикум. – М.: Горячая линия – Телеком, 2004. – 175 с.
  6. Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Введение в математическое моделирование транспортных потоков: Учебное пособие / Под редакцией Гасникова А.В. – М.: МЦНМО, 2012.
  7. Морозов И. И., Гасников А. В., Тарасов В. Н., Холодовa Я. А., Холодов А.С.  Численное исследование транспортных потоков на основе гидродинамических моделей.
  8. Урыков В.А., Зеленина Л.И. Математические модели транспортных потоков // Современная техника и технологии. 2015. № 6 [Электронный ресурс]. URL: http://technology.snauka.ru/2015/06/6051 (дата обращения: 17.06.2015).


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


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

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

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

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

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