Графы — замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
Наиболее распространенным применением теории графов является решение задачи о нахождении кратчайшего пути между двумя пунктами на карте. Однако, в городе, в ускоряющемся ритме современной жизни, важно как можно быстрее добраться до пункта назначения, а сделать это можно только с учетом режима работы светофоров. В этом случае для нахождения оптимальной схемы движения необходимо использовать взвешенный граф [1], веса которого определяются временем перемещения с учетом времени пересечения перекрестка в зависимости от цвета сигнала светофора
Цель данной работы — исследовать влияние работы светофоров на передвижение по городу и проверить гипотезу о существовании оптимальной схемы движения на основе комбинации маршрута и скорости.
Для достижения поставленной цели необходимо решить следующие задачи:
– построить модель, показывающую поведение «зеленой волны»;
– построить и исследовать дорожный граф с весами, учитывающими режимы работы светофоров;
– найти оптимальную комбинацию маршрут-скорость в условиях реального города.
Объект исследования представляет собой сеть дорог, движение по которой регулируется светофорами, а предмет — зависимость времени поездки от скорости и пути движения.
Основными методами решения поставленных задач являются моделирование и анализ.
Принцип «зеленой волны»
«Зеленая волна» — это система автоматических светофоров, действующих в пределах одной магистрали и сменяющих сигналы через определенные промежутки времени, необходимые для проезда «пачкой» автомобилей расстояния между перекрестками [3]. При этом, конечно, обязательным условием координированного регулирования является поддержание автомобилями расчетной скорости движения.
В странах Западной Европы и в США введение координированного регулирования началось в 30-х годах XX века [2]. В нашей стране первый опытный участок системы координированного регулирования был создан в 1955 г. на Садовом кольце в Москве [3].
В настоящее время существует несколько систем координированного регулирования. Наиболее часто применяются следующие [3]:
а) Прогрессивная система координированного регулирования или, так называемая, «зеленая волна». При этой системе устанавливается, в соответствии с расчетной скоростью движения транспорта, сдвиг во времени подачи одноименных сигналов светофорами на соседних перекрестках. Сигналы это могут быть одинаковой и разной продолжительности при обязательно равном цикле регулирования для всех перекрестков.
б) Гибкая прогрессивная система, при которой цикл работы светофоров изменяется в зависимости от интенсивности движения магистрали в те или иные часы.
в) Синхронная система координированного регулирования — «зеленая улица» с одновременной подачей одноименных сигналов одинаковой продолжительности на всех перекрестках магистрали.
Моделирование «зеленой улицы»
Построим модель перемещения из точки А в точку Б по маршруту со светофорами на перекрестках, работающими по принципу «зеленой улицы».
Для упрощения модели введем следующие допущения:
– у каждого светофора сигналы только двух цветов: красный и зленый;
– время работы сигналов каждого цвета всех светофоров одинаково;
– зеленый сигнал включается одновременно на всех светофорах;
– начало движения по маршруту начинается одновременно с включением зеленого сигнала светофора;
– расстояние между всеми перекрестками одинаковое;
– время проезда перекрестка равно нулю.
Пусть на маршруте от точки А до точки Б встречается четыре перекрестка со светофорами (рисунок 1). Расстояние между перекрестками S.
Рис. 1. Схема маршрута для демонстрации эффекта «зеленой улицы»
Время проезда по маршруту определяется суммой времен проезда одного квартала (от перекрестка до перекрестка) и времен задержки, вызванной остановкой на красный сигнал светофора:
(1)
где
— время проезда по маршруту АБ;
— время проезда одного отрезка маршрута;
— время задержки на светофорах (первом, втором, третьем, четвертом соответственно).
Рассмотрим первый отрезок, когда машина трогается из точки А одновременно с включением зеленого сигнала на светофоре С1. Для того, чтобы понять, при каком сигнале светофора машина подъедет к перекрестку, необходимо оценить, сколько раз изменится цвет сигнала светофора, пока машина едет к нему. Для этого надо рассчитать, сколько времен работы одного цвета сигнала светофора укладывается на времени проезда одного отрезка:
(2)
где
— время работы одного сигнала.
Целая часть n показывает, сколько раз изменился сигнал светофора. Если целая часть n — четное число, то машина приедет к зеленому сигналу светофора (рисунок 2а). Если целая часть n — нечетное число, то машина приедет к красному сигналу светофора (рисунок 2б).
Рис. 2. Схема определения цвета сигнала при подъезде к светофору
Дробная часть n показывает, какую часть времени уже проработал включенный сигнал светофора. Если он красный, то оставшуюся часть машине придется простоять на светофоре, ожидая, когда включится зеленый сигнал. Важно учесть потери времени, связанные с процессами торможения и разгона машины. Приближенно можно считать, что потери времени из-за торможения и разгона составляют примерно 10 секунд при каждой остановке (в источниках литературы [3] для расчета скорости сообщения между точками маршрута в зависимости от максимальной скорости проезда квартала используется средняя задержка перед светофором до 30 сек). Тогда время задержки на светофоре, в случае, если машина приехала к красному сигналу, будет равно:
(3)
где
— дробная часть числа n.
Формула (2) справедлива только в случае, если машина начинает движение одновременно с включением зеленого сигнала светофора (справедливо для первого отрезка маршрута и в случае остановки на красный сигнал светофора). Если машина подъехала к перекрестку при работающем зеленом сигнале, то она продолжает движение не останавливаясь. В этом случае необходимо учесть время, которое уже проработал зеленый сигнал светофора до того, как машина пересекла перекресток (рисунок 2в).
В общем случае формула для определения количества изменений цвета сигнала светофора за время проезда одного отрезка маршрута будет иметь вид:
(4)
где
— время, которое проработал зеленый сигнал светофора до проезда машиной перекрестка.
Для первого отрезка по условию задачи 
, а для следующих, в случае проезда перекрестка без остановки на зеленый сигнал светофора, будет определяться по формуле:
(5)
При этом важно помнить, что , рассчитанное по формуле (5) в результате проезда по отрезку с номером i (на основе значения ni, рассчитанного на этом отрезке), будет дальше, на следующем отрезке с номером (i+1), использоваться для расчета ni+1 по формуле (4).
Для случая, когда машина начинает движение одновременно с включением зеленого сигнала светофора, время, которое уже проработал зеленый сигнал, равно нулю, и тогда формула (4) сводится к формуле (2).
На основе разработанной модели покажем зависимость времени прохождения маршрута от выбранной скорости. Длина каждого отрезка маршрута и время работы сигнала светофора одного цвета задаются в условии и остаются постоянными. Время проезда одного отрезка маршрута определяется по формуле:
(6)
гдеS — длина отрезка маршрута;
V — скорость машины.
Расчеты по формулам (1), (3)-(6) выполнены с помощью программного обеспечения Microsoft Excel.
Расчеты проведены для следующих значений параметров модели:
– длина отрезка маршрута S = 667 м,
– время работы сигнала светофора одного цвета tц = 30 сек,
– скорость движения машины от 35 км/ч до 60 км/ч с шагом 5 км/ч.
В таблице 1 представлен пример результата расчетов с помощью таблицы в Microsoft Excel для скорости 35 км/ч.
Таблица 1
Пример результата расчетов для скорости 35 км/ч
|
Номер отрезка |
1 |
2 |
3 |
4 |
5 |
|
Длина отрезка S, м |
667 |
667 |
667 |
667 |
667 |
|
Время отрезка t, с |
68,76 |
68,76 |
68,762 |
68,76 |
68,76 |
|
Время задержки Δt, с |
0 |
0 |
0 |
34,95 |
- |
|
Время, к-е работал зел.свет tзс, с |
0 |
8,76 |
17,53 |
- |
- |
|
Количество переключений светофора n |
2,29 |
2,58 |
2,88 |
3,17 |
- |
|
Целая часть n |
2 |
2 |
2 |
3 |
- |
|
Четность целой части n |
истина |
истина |
истина |
ложь |
- |
|
Дробная часть n |
0,29 |
0,58 |
0,88 |
0,17 |
- |
|
Общее время tАБ, мин |
6,31 |
||||
Из таблицы 1 видно, что при скорости движения 35 км/ч машина останавливалась на красный сигнал светофора на светофоре С4, и время задержки составило примерно 35 секунд.
В таблице 2 представлены общие результаты расчета для модели «зеленая улица».
Таблица 2
Результаты расчетов по модели «зеленая улица»
|
Скорость, км/ч |
35 |
40 |
45 |
50 |
55 |
60 |
|
Общее время tАБ, мин |
6,31 |
5,01 |
5,56 |
5,47 |
5,39 |
5,33 |
Из таблицы 2 видно, что «зеленая волна» возникает при движении со скоростью 40 км/ч. При движении с этой скоростью машина проезжает все перекрестки на зеленый свет, не возникает задержек из-за остановок, поэтому общее время прохождения маршрута в этом случае минимально. С дальнейшим ростом скорости выше 45 км/ч общее время начинает снижаться, однако даже при движении с максимально разрешенной в городе скоростью 60 км/ч общее время движения на 6 % больше, чем время движения со «скоростью зеленой волны». Конечно, разница не очень велика. Однако, надо учитывать, что эта разница возникла на маршруте длиной всего около 3 км. А в современных мегаполисах обычно приходится проезжать расстояния не менее нескольких десятков километров с большим количеством светофоров.
Поиск оптимальной комбинации маршрут-скорость с учетом режима работы светофоров (поиск «зеленой волны»)
Попробуем применить основы теории графов к решению задачи нахождения оптимального маршрута из пункта А в пункт Б с учетом времени работы светофоров на перекрестках возможных маршрутов.
Критерием оптимальности маршрута будем считать не длину маршрута, а время, необходимое для его прохождения. Только комбинация выбранного маршрута и оптимальной скорости поможет достичь минимального времени перемещения из пункта А в пункт Б, так как при наличии светофоров на перекрестках возможных маршрутов время прохождения маршрута может оказаться минимальным при скорости меньшей максимально разрешенной, если получиться попасть в «зеленую волну» светофоров.
Рассмотрим следующий пример. Перемещение из пункта А в пункт Б возможно по нескольким дорогам, проходящим через перекрестки, движение на которых регулируется светофорами. Представим пункты А и Б, а также перекрестки со светофорами в виде вершин графа, а дороги, их соединяющие, — в виде ребер (рисунок 3).
Рис. 3. Представление дорог между пунктами А и Б в виде графа
Будем использовать при решении задачи взвешенный граф. С учетом выбранного критерия оптимальности маршрута в графе весами ребер будут не расстояния между перекрестками, а время перемещения от одного перекрестка к другому с учетом возможного времени задержки при остановке на красный сигнал светофора.
Рассмотрим более общий случай по сравнению с построенной выше моделью «зеленой улицы». Будем считать, что каждый светофор может иметь отличную от других продолжительность периода работы. Под периодом работы светофора будем понимать суммарное время работы зеленого и красного сигналов. Более того, время работы сигналов разного цвета у одного светофора может отличаться. В этом случае для определения цвета сигнала светофора, при котором машина подъезжает к перекрестку, надо рассчитать, аналогично формуле (4), соотношение вида:
(7)
где
— период работы светофора.
Пусть a — доля времени работы зеленого сигнала в периоде работы светофора, тогда (1-а) — доля времени работы красного сигнала.
Тогда, сравнение дробной части m с долей времени работы зеленого сигнала светофора, позволит определить, цвет сигнала, при котором машина подъезжает к светофору (рисунок 4):
– если {m} < a, то горит зеленый свет;
– если {m} ≥ a, то горит красный свет.
Рис. 4. Схема определения цвета сигнала при подъезде к светофору при разных временах работы сигналов
Тогда, аналогично формулам (3) и (5) время задержки на светофоре и время, которое проработал зеленый сигнал до проезда через перекресток, будут определяться выражениями
(8)
(9)
С учетом изменений, внесенных в модель «зеленой волны», на основе графа, представленного на рисунке 6, и выбранного критерия оптимальности, найдем лучшую комбинацию-скорость для перемещения из пункта в пункт Б.
Исходные данные для решения рассматриваемой задачи представлены в таблице 3 и таблице 4.
Таблица 3
Расстояния между перекрестками
|
Ребро |
АВ |
АГ |
АЕ |
ВД |
ЖБ |
ДБ |
ГД |
ЕЖ |
|
Длина, м |
750 |
460 |
805 |
815 |
400 |
320 |
600 |
500 |
Таблица 4
Параметры работы светофоров
|
Вершина |
В |
Г |
Д |
Е |
Ж |
|
Период, с |
60 |
55 |
65 |
80 |
40 |
|
Доля зеленого света |
0,3 |
0,5 |
0,3 |
0,6 |
0,5 |
Необходимо отметить, что приведенная в таблице 4 доля работы зленого света светофора на перекрестке Д, соответствует направлению проезда перекрестка в направлении от Г к Б (рисунок 3). Соответственно, при проезде этого же перекрестка в направлении от В к Б доля работы зеленого света будет составлять (1–0,3) = 0,7. Это соответствует случаю неравнозначных дорог: дорога от В к Б является главной.
По графу видно (рисунок 3), что существует три маршрута между вершинами А и Б: АВДБ, АГДБ и АЕЖБ. Сравним время прохождения каждого маршрута при разных скоростях движения. Расчеты по формулам (1), (6)-(9) выполнены с помощью программного обеспечения Microsoft Excel. Результаты расчетов приведены в таблице 5.
Таблица 5
Результаты расчета времени (в минутах) прохождения маршрутов между точками А и Б
|
Маршрут |
Скорость, км/ч |
|||||
|
35 |
40 |
45 |
50 |
55 |
60 |
|
|
АВДБ |
3,24 |
2,83 |
2,51 |
2,8 |
2,77 |
2,74 |
|
АГДБ |
2,88 |
2,81 |
2,76 |
2,72 |
2,68 |
2,65 |
|
АЕЖБ |
2,93 |
2,85 |
2,70 |
2,81 |
2,77 |
2,73 |
Из таблицы 5 видно, что оптимальным является маршрут АВДБ при скорости движения по нему 45 км/ч.
Если для определения оптимального маршрута использовать наиболее распространенный критерий — длину маршрута (таблица 3), то лучшим можно было бы считать маршрут АГДБ (SАГДБ = 1380 м, SАВДБ = 1885 м, SАЕЖБ = 1705 м). При этом время прохождения данного маршрута даже при максимальной разрешенной скорости 60 км/ч будет на 6 % больше.
Пример поиска оптимальной комбинации маршрут-скорость в условиях реального города
Можно применить разработанный подход к анализу реальных маршрутов — между домом (пункт А) и КСЦ «Мечта» (пункт Б), где я занимаюсь танцами. Фрагмент карты города Одинцово, с отмеченными на ней возможными маршрутами, и соответствующий им граф представлены на рисунке 8.
Рис. 5. Возможные маршруты от дома до КСЦ «Мечта»
Исходные данные представлены в таблице 6 и таблице 7.
Таблица 6
Расстояния между перекрестками
|
Ребро |
АЗ |
АЕ |
ВГ |
ВЕ |
ЕЖ |
ЖГ |
ГД |
ДБ |
ЖБ |
ЗВ |
|
Длина, м |
543 |
1030 |
1730 |
608 |
453 |
236 |
243 |
245 |
501 |
447 |
Таблица 7
Параметры работы светофоров
|
Вершина |
Д |
Е |
Ж |
З |
|
Период, с |
70 |
80 |
74 |
65 |
|
Доля зеленого света |
0,57 |
0,27 |
0,32 |
0,76 |
Для поиска возможных маршрутов (элементарных цепей) в графе будем использовать подход, называемый «поиск в глубину». Поиск в глубину — один из методов обхода графа, состоящий в том, чтобы идти «вглубь» графа, насколько это возможно [1]. Результат поиска элементарных цепей методом поиска в глубину представлен на рисунке 9.
Рис. 6. Поиск в глубину для поиска элементарных цепей в графе
Итак, существует восемь маршрутов между вершинами А и Б: АЗВГЖБ, АЗВГДБ, АЗВЕЖГДБ, АЗВЕЖБ, АЕВГДБ, АЕВГЖБ, АЕЖГДБ, АЕЖБ.
Сравним время прохождения каждого маршрута при разных скоростях движения (таблица 8).
Таблица 8
Результаты расчета времени пути (в минутах) для реальной среды
|
Маршрут |
Скорость, км/ч |
|||||
|
35 |
40 |
45 |
50 |
55 |
60 |
|
|
АЗВГЖБ |
6,51 |
6,15 |
5,07 |
5 |
3,95 |
3,9 |
|
АЗВГДБ |
6 |
4,81 |
4,66 |
3,84 |
3,49 |
3,58 |
|
АЗВЕЖГДБ |
7,23 |
5,43 |
4,86 |
4,77 |
4,69 |
3,45 |
|
АЗВЕЖБ |
6,34 |
4,49 |
4,57 |
4,5 |
4,45 |
3,53 |
|
АЕВГДБ |
7,69 |
6,03 |
5,14 |
5,12 |
5,1 |
4,32 |
|
АЕВГЖБ |
9,09 |
6,49 |
6,4 |
5,5 |
5,45 |
5,4 |
|
АЕЖГДБ |
5,98 |
4,43 |
3,7 |
3,77 |
3,69 |
3,62 |
|
АЕЖБ |
5,09 |
3,49 |
3,39 |
3,58 |
3,49 |
3,45 |
Из таблицы 8 видно, что оптимальным является маршрут АЕЖБ при скорости движения по нему 45 км/ч. Этот маршрут самый короткий, и был бы выбран лучшим и при «классическом» подходе, однако проведенное исследование показало, что оптимальной для движения по нему является не максимальная скорость. Найденная «зеленая волна» соответствует более безопасной для проезда по городу скорости — 45 км/ч.
Выводы
Применение дорожных графов совместно с принципом «зеленой волны» позволит более эффективно планировать поездки, и при массовом использовании может способствовать повышению безопасности движения.
В ходе выполнения работы сделаны следующие выводы:
– построенная модель «зеленой улицы» показывает возможность сокращения времени пути при снижении скорости движения;
– моделирование разных режимов работы светофоров на разных перекрестках дает возможность построить дорожный граф с весами, зависящими от режима работы светофора и скорости движения, что позволяет получить более реалистичную модель перемещения по дорожной сети города;
– показана возможность существования оптимальной схемы движения на основе комбинации маршрута и скорости, обеспечивающих минимальное время перемещения из одной заданной точки в другую;
– приведен пример оптимальной комбинации маршрут-скорость в условиях реального города;
– показано, что даже при незначительной длине маршрутов и малом количестве светофоров видна результативность предложенного подхода.
Литература:
1 Зыков А. А. Основы теории графов. М.: изд. «Наука», 1987. — 384 с.
2 Метсон Т. М., Смит У. С., Хард Ф. В. Организация движения. Пер. с англ., М.: изд. «Автотрансиздат», 1960. — 464 с.
3 Страментов А. Е., Фишельсон М. С. Городское движение. М.: изд. «Госстройиздат», 1963. — 296 с.
4 Яковлев А. А. Леонард Эйлер. М.: изд. «Просвещение», 1983. — 79 с.
5 Основы теории графов, задача о Кенигсбергских мостах (Л. Эйлер) // Decoder.ru [Электронный ресурс] URL: http://www.decoder.ru/list/all/topic_117/ (Дата обращения 29.11.2019)
