Применение теории графов в задачах управления дорожным движением

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

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

Автоматизированная система управления дорожным движением — это комплекс технических и программных средств, управляемых человеком и компьютером. Основные задачи современной автоматизированной системы — сбор, хранение и обработка информации о транспортных потоках, состоянии улично-дорожной сети (УДС) и оптимизированное управление дорожным движением [4].

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

«Информационный уровень — сбор и хранение информации об УДС города с дислокацией технических средств организации дорожного движения (ТСОДД) (дорожные знаки, светофоры), разметки и элементов инженерного обустройства дороги. Операционный уровень — обработка оперативных данных о состоянии УДС, технических средствах организации дорожного движения, аварийности и др.

«Управленческий уровень — решение задач контроля правильности установки новых ТСОДД, координированного управления, оптимизации управления транспортными потоками и т. п.

Задачи управленческого уровня наиболее трудно поддаются формализации. К ним можно отнести задачи оптимизации управления транспортными потоками на УДС города в условиях постоянно изменяющихся дорожно-транспортных условий: нахождение всевозможных путей между различными пунктами назначения;

«нахождение кратчайшего пути между пунктами УДС;» определение безопасного маршрута прохождения транспортного потока.

Математическая модель, лежащая в основе автоматизированной системы, может быть построена с применением различных теорий. Например, с использованием принципов объектно-ориентированного программирования. В основе такого подхода лежит принцип описания физических объектов различной природы и взаимодействий между ними [2].

Объектом управления в разработанной системе является транспортный поток N, движущийся по улично-дорожной сети S. Сформулируем задачу управления потоком следующим образом: необходимо организовать движение транспортного потока N таким образом, чтобы выполнялись следующие условия:

• 1. максимальная безопасность движения;
• 2. максимальная пропускная способность перекрестков.

Построим функцию управления F: (Ni, Si, U) (Nj, Si+1), т. е. имея поток Ni на участке схемы Si и воздействуя на него управляющим органом U, получим другой поток Nj на следующем участке Si+1.

Другой метод построения модели УДС — это применение теории графов.

Вершиной графа является внешняя граница перекрестка. Ребро показывает направление движение транспортного потока от одной границы перекрестка до другой. Если движение транспорта в каком-либо направлении запрещено, то вершины не соединяются [4]. Таким образом, УДС можно представить ориентированным графом. Этот граф является циклическим, т.к. существует хотя бы один путь, в котором начальная вершина совпадает с конечной, и при этом данный путь содержит минимум одно ребро. Другими словами, всегда существует путь, по которому можно, выехав из начального пункта, вернуться обратно.

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

Опишем модель УДС в терминах теории графов:

G = (V, E),.

где Vконечное множество, E — бинарное отношение на V, т. е. подмножество множества VxV. Множество E является множеством вершин, а его элемент — вершиной, а множество V является множеством ребер (участков УДС), а его элемент — ребром [6].

Указанная модель позволяет формализовать некоторые понятия предметной области. Точки начала и конца участка (), представляют собой смежные вершины и пересечение участков есть инцидентность ребер и вершины, представляющей начало заданного участка. Уровень сложности перекрестка можно определить суммарной степенью вершин, ограничивающих этот перекресток. Степенью вершины является суммарное количество инцидентных ей ребер. Путь из одной точки УДС в другую, представляется, как путь из вершины u в вершину v и определяется, как последовательность вершин (v0, v1, …, vk), в которой v0=u, vk=v и (vi-1,vi) E для всех i=1,2,…, k. Таким образом, проезд из одной точки в другую по k участкам дороги можно представить, как путь длины k, состоящий из k ребер. Задача нахождения путей между различными точками УДС, сводится к следующему математическому описанию.

Для заданных G = (V, E), u, v V, требуется найти вершины (v0, v1, …, vk) V и ребра (vi-1,vi) E, для всех i=1,2,…, k, где v0 =u, а vk= v. Если такой путь существует, то будем говорить, что вершина v достижима из u по пути p. Запишем это как объект «участок» имеет имманентные свойства, такие как протяженность, ширина проезжей части, полосность и т. д. С другой стороны, рассмотрение транспортного потока, движущегося по этому участку, приводит к появлению дополнительных свойств, являющихся характеристиками этого потока: интенсивность, плотность потока и средняя скорость движения.

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

Одной из задач управления дорожным движением является задача о нахождении кратчайшего пути между заданными точками. В этой задаче дан ориентированный взвешенный граф G = (V, E), с вещественной весовой функцией w: E R, w (u, v) — вес ребра (u, v), а R — множество вещественных значений весовой функции. Вес пути p = (v0, v1, …, vk) определим как сумму весов ребер, входящих в этот путь.

Кратчайший путь из u в v — это любой путь p из u в v, для которого.

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

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