УДК 656.02+351.811.12

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ИНТЕЛЛЕКТУАЛЬНОЙ СИСТЕМЫ УПРАВЛЕНИЯ ДВИЖЕНИЕМ ТРАНСПОРТА

Соловьев Виктор Владимирович1, Шаповалов Игорь Олегович2, Ваарман Валентина Владимировна3, Пак Марина Игоревна4
1Южный Федеральный Университет, старший преподаватель кафедры систем автоматического управления
2Южный Федеральный Университет, ассистент кафедры систем автоматического управления
3Южный Федеральный Университет, студент кафедры систем автоматического управления
4Южный Федеральный Университет, студент кафедры систем автоматического управления

Аннотация
В данной статье выполнен аналитический обзор алгоритмов поиска пути и выявлены критерии поиска оптимального пути. В соответствии с поставленной задачей был разработан алгоритм поиска оптимального пути с учетом загруженности магистралей. Исследование работы алгоритма выполнялось с использованием интегрированной среды разработки Microsoft Visual Studio.

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


DEVELOPMENT AND RESEARCH OF INTELLIGENT TRAFFIC CONTROL SYSTEM

Soloviev Viktor Vladimirovich1, Shapovalov Igor Olegovich2, Vaarman Valentina Vladimirovna3, Pak Marina Igorevna4
1Southern Federal University, senior lecturer, department of automatic control systems
2Southern Federal University, assistant, department of automatic control systems
3Southern Federal University, student, department of automatic control systems
4Southern Federal University, student, department of automatic control systems

Abstract
This article gives an analytical overview of the way search algorithms and identified criteria for finding the optimal path. In accordance with the task developed an algorithm for finding the optimal way, taking into account congestion highways. Research of the algorithm working was carried out using the integrated development environment Microsoft Visual Studio.

Keywords: algorithm of search of a way, congestion, optimization of traffic


Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Соловьев В.В., Шаповалов И.О., Ваарман В.В., Пак М.И. Разработка и исследование интеллектуальной системы управления движением транспорта // Современные научные исследования и инновации. 2015. № 10 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/10/58241 (дата обращения: 03.06.2017).

В связи с возрастающей загруженностью дорог, задачи поиска оптимального маршрута движения транспорта становятся все актуальнее. Эффективное управление движением транспорта в дорожной сети выполняется с использованием системы управления транспортными потоками. Эта система представляет собой комплекс программных и технических средств решения всех видов транспортных проблем на основе современных интеллектуальных технологий, моделей транспортных процессов, специализированного программного обеспечения [1].
В результате увеличения объема транспортного потока увеличивается загруженность дорог на всех участках транспортной сети, усложняется выбор оптимального пути, что усугубляет ситуацию и приводит к увеличению заторов и росту ДТП. Поэтому одним из способов разгрузи дорог является корректное распределение транспортного потока путем внедрения разработанного программного продукта. Сбор и анализ информации о дорожном движении помогают водителям выбирать оптимальный маршрут, а автодорожным службам принимать наиболее эффективные направления развития транспортной сети [2]. 
В литературе представлено немало методов и алгоритмов решения транспортных задач [3–6]. Наибольшую известность приобрели методы поиска маршрута, основанные на переборе вариантов построения траектории среди всех возможных, и выборе оптимального решения: алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Транспортная сеть в алгоритмах формализуется с применением взвешенных графов. Основой этих алгоритмов является метод поиска маршрута, основанного на переборе возможных вариантов построения траектории движения и выборе оптимального решения. Рассмотрим основные особенности перечисленных алгоритмов.
При нахождении кратчайшего пути, как правило, используют алгоритм Дейкстры, который строит кратчайший путь, ведущий от начальной вершины к остальным вершинам графа (если таковой имеется). Результатом работы алгоритма Дейкстры является дерево кратчайших путей, содержащее путь от заданной (начальной) вершины до всех остальных [7].
Основными ограничениями этого алгоритма являются:
– отсутствие в графе петель;
– отсутствие в графе ребер отрицательного веса (в отличие от алгоритма Беллмана-Форда), т.е. если, например, некоторая система предусматривает убыточные для предприятия маршруты, то для работы с ней следует воспользоваться отличным от алгоритма Дейкстры методом.
В алгоритме Беллмана – Форда, разработанном в 1956 году, на взвешенном графе вычисляются пути от одной вершины к всем остальным. Его применяют для графов у которых вес ребра может быть отрицательным. Здесь возникают некоторые затруднения связанные с тем, что каждый проход по пути, в котором сумма весов ребер отрицательная (т.е. по отрицательному циклу), лишь улучшает требуемое значение. В этой связи алгоритм Беллмана-Форда не может быть применен к графам, имеющим отрицательные циклы, но позволяет диагностировать их наличие[8].
В алгоритме Флойда – Уоршелла с использованием метода динамического программирования выполняется поиск кратчайшего пути между всеми вершинами взвешенных графов с отрицательными весами без циклов.
Алгоритм Флойда-Уоршелла является более общим в сравнении с алгоритмом Дейкстры, т.к. последний не работает с отрицательными весами ребер, и, к тому же, классическая его реализация подразумевает определение оптимальных расстояний от одной вершины до всех остальных. Алгоритм содержит три вложенных цикла, т.е. имеет кубическую сложность.
В результате анализа алгоритмов поиска пути установлено, что существующие методы непригодны для использования при разработке интеллектуальной транспортной системы. В виду того, что для ряда практических задач важное значение имеют одновременное выполнение требования минимизации времени поиска и учет некоторого множества ограничивающих факторов.
В ходе исследования и разработки было принято решение использовать алгоритм А* (читается «А-звезда»), который был в дальнейшем модифицирован. С использованием этого алгоритма можно минимизировать затраты времени на движение. Он отличается высокой производительностью за счет эвристики. Основная идея эвристического поиска оптимальных маршрутов строится на использовании дополнительной информации для управления процессом поиска. Дополнительная информация может формироваться на основе эмпирического опыта или в результате предварительного сбора данных о дорожной обстановке. 
Использование эвристики приводит к более быстрому поиску оптимального маршрута, т.к. позволяет сократить количество просматриваемых вариантов при решении задачи [10]. 
Для вычисления оптимального пути с использованием алгоритма «А* модифицированный» будут использоваться два критерия: загруженность и длина пути. Вводятся два параметра для ребер графа: 
– расстояние от предыдущего узла g(x);
– загруженность дороги h(x).
Оценочная функция для каждого участка рассчитывается в виде:

 (1)

где , – степень важности критерия (+=1),
∆l – самый длинный путь между смежными узлами в графе.
Величин h(x) определяется в интервале [0, 1]. Абсолютное значение g(x) не укладывается в этот интервал, поэтому выполняется нормирование, путем деления на ∆l.
В основе исследования лежит транспортная сеть центральной части города Таганрога от пер. Смирновского до пер. Украинского, характеризующаяся высокими пиковыми нагрузками [11].
В определении оптимальности маршрутов имеет решающее значение прогнозируемое время прохождения маршрута , которое рассчитывается по формуле:

 (2)

где g – общая протяжённость маршрута;
vср = 11 м/с – средняя скорость движения транспортного средства в населённом пункте (примерно равно 40 км/ч);
h – общая загруженность маршрута.
В оценочную функцию входят 2 коэффициента. Было необходимо выявить важность того или иного коэффициента. C помощью подбора и бинарного поиска были найдены диапазоны значений в, при которых алгоритм отвечает требованию нахождения оптимального по времени пути. Данное значение коэффициента использовалось в дальнейшем алгоритмом «А* модифицированный» при сравнении с другими алгоритмами.
Разработка алгоритма реализована с использованием языка программирования высокого уровня на ЭВМ. В данной работе исследование проходит в среде С++. Главной задачей разработанного приложения является поиск пути с учетом загруженности магистралей.
Программа разделена на две главных секции – графическое поле слева и набор вкладок справа.
Графическое поле (рис. 1) содержит в себе ориентированный граф рассматриваемой транспортной сети, наложенный поверх карты города, с пронумерованными вершинами (перекрёстками) и рёбрами (участками сети), направление которых определяет допустимое направление движения для большинства видов транспортных средств. В верхнем правом углу графического поля изображён отрезок С-Ю, оформленный в виде компаса и указывающий расположение параллелей.


Рисунок 1 – Графическое поле программы

Набор вкладок в правой части окна разделяет по вкладкам следующие функциональные возможности программы:
– поиск пути – позволяет пользователю настроить поиск маршрута и увидеть результаты алгоритмических расчётов (рис. 2);
– участки – отображает информацию об участках транспортной сети и позволяет указать их загруженность (рис. 3);
– перекрестки – отображает координаты узлов транспортной сети (рис. 3).
Параметры компонентов графа транспортной сети загружаются при открытии программы из базы данных.


Рисунок 2 – Вкладка «Поиск пути»


Рисунок 3 – Вкладки «Участки» и «Перекрестки»

Для нахождения и построения программой оптимального маршрута от одной точки до другой пользователю необходимо указать в полях “Начало пути” и “Конец пути” номера начальной и конечной вершин графа, изображенного на графическом поле, а так же выбрать один из трёх алгоритмов в поле “Алгоритм”: А* (А-звезда) модифицированный, Беллмана-Форда и Флойда-Уоршелла. Затем нажать кнопку “Поиск”.
Для проверки корректности работы алгоритма была построена диаграмма сравнения результатов алгоритмов по времени прохождения маршрута (рис. 4).


Рисунок 4 – Сравнение результатов выбранных алгоритмов

Были заданы случайные значения параметра загруженности участков транспортной сети и проведен поиск маршрута при разных начальных и конечных точках. При работе алгоритма А* время прохождения маршрута сократилось примерно на 25%. Полученные результаты свидетельствуют о явном преимуществе алгоритма А* (модифицированный) над двумя другими выбранными алгоритмами: Беллмана-Форда и Флойда-Уоршелла.


Библиографический список
  1. Семенов В.В. Математическое моделирование динамики транспортных потоков мегаполиса. – М., 2004. – 44 с.
  2. Кичеджи В. Н., Хатояма К. Москва. Транспортные проблемы мегаполиса. – М.: ДПК Пресс, 2010. – 284 с.
  3. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = Introduction to Algorithms. – 2-е изд. – М.: «Вильямс», 2006. – С. 1296.
  4. Ананий В. Левитин. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. – М.: «Вильямс», 2006. – С. 189—195.
  5. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87-90, 1958.
  6. L. R. Ford, Jr., D. R. Fulkerson. Flows in Networks, Princeton University Press, 1962.
  7. Ананий В. Левитин. Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. – М.: «Вильямс», 2006. – С. 189—195.
  8. R. Bellman: On a Routing Problem // Quarterly of Applied Mathematics. 1958. Vol 16, No. 1. C. 87-90, 1958.
  9. Соловьев В.В., Пак М.И. Анализ методов поиска кратчайшего пути. МОЛОДЕЖЬ, НАУКА, ИННОВАЦИИ. Материалы II Всероссийской научно – практической конференции. Том I. – Грозный: ГГНТУ, 2013. -404 с.
  10. Соловьев В.В., Пак М.И. Поиск кратчайшего пути с учетом загруженности дорог. Современные информационные технологии: тенденции и перспективы развития. Материалы конференции; Южный федеральный университет. – Ростов – на – Дону: Издательство Южного федерального университета, 2014. – 440 с.
  11. Соловьев В.В., Косенко О.В., Ваарман В.В. Формализация задачи движения транспорта. Современные технологии, естествознание и педагогика – СТЕПь-2013* /  Сборник трудов II  Всероссийской научной конференции молодых ученых,  аспирантов и  студентов. –  Элиста: Издательство Южного федерального университета , 2013 – 348 с.


Все статьи автора «Соловьев Виктор Владимирович»


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

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

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

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

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