close

Вход

Забыли?

вход по аккаунту

?

Математическое моделирование транспортных потоков на основе схемы с двумя масштабами времени.

код для вставкиСкачать
?? ь 519.8
¬. ї. ? ?А?¬? ®¬
?. ?. ?ї? «?АА»Х
Гї??Гї?»??? ь??
Г?? ?А»??¬їХ»? ??їХ? ????Х¤?
????ь?¬ Хї ?? Х?¬? ? ??Г¤
? ? ¬?Гfl Гї? я ?їЎїГ» ¬??Г?Х»
?????? ??????? ??????? ? 3 (103) 2011
?П ТНЛИ ?У ТЫ
? ??ТЪ?
ВМ М ?И
ЪВ? М Л?ВТНЛИ Ы
М Л?
В?ТЛЪВЪ
¬ ??·У ЪВ ??ТТП ?Ъ?Л?
??ЪТ?П ЛН?У ТНУ ФЛ?ВТНЛВ П У ? ВО Л Ъ??М ТФУ ?ЪМ ?? ФУ ЪУ НУ ?
?
Н?Ы
ФМ УП ?У?У? В, У ТМ У?
?М М ?ВМ ? П У? ВО ЛТО В? У?
?М Л?Б? О Л? В?У П ЛТ? ВП ВФ?В? ЛНЪУ ?-НУ ??ВНЪУ ?. ??ЛЪ??
??ЪТ???БО Л?М ?В ЛБП ВМ ВМ Л??
ФУ ЪУ НВ: ТНУ ?У ТЪМ ?В
? ???НЪВ?ЛТЪЛНЛ Ъ??М ТФУ ?ЪМ ?? Т?В? ТЪ?
, ТЫ
К ВМ ЛВ П ??ЛТЪ??О ВИ, ТП ВМ ? ТЛ?М ?О У ?
Т?
ВЪУЩ У?У?
, ТО Ы
??ИМ ?ИТЪ??ЪЪ??М ТФУ?ЪМ ?? Т?В? ТЪ?
, ТБ?? ?М М ?П ФЫ
М НЪУП М ?БМ ??ВМ Л?, Ъ??М БЛЪМ ?ИФУЪУН Ъ??М ТФУ?ЪМ ?? Т?В? ТЪ?
?В?ВБ?У ?У ? ЛЪ.Ф. ? О ??В?О ЛБ??ЛЛП У ? ВО ЛФ?В? О У К ВМ ТФУ ТУ · ??ТФ???О О ВО Л?
?М Л?М ? М ВТНУ О ёНУ Ф?У ?ВТТУ ?У ?
,
?ТТУ?ЛЛ?У?
?М М ?? Т??ИУМ ?П Л?У ?У? ?. ?ВБЫ
О ёЪ?Ъ? ЪВТЪЛ?У?
?М Л?ФУН?Б??
??Ъ?Щ Щ ВНЪЛ?
М У ТЪё Ф???О О ВО ёМ У И ?
В?ТЛЛ ? О ?П У ? ВО Л?У ?
?М Л??
?ВК ЛП В ?В?О ёМ У ?У
?
?ВП ВМ Л, Л?
У БП У К М У ТЪё Ы
Ф???
О ВМ Л?Ъ??М ТФУ ?ЪМ ?П ЛФУЪУН?П ЛТ?ЛТО У П Ъ??М ТФУ ?ЪМ ?? Т?В? ТЪ?
ФУ ??? Н? 106.
ьО ??В?
?В ТО У ?
?: П ?ЪВП ?ЪЛ?ВТНУ В П У ? ВО Л?У ?
?М ЛВ, Ъ??М ТФУ ?ЪМ ?В ФУ ЪУ НЛ, ТО В? У?
?М ЛВ Б? О Л? В?У П , П ?Т? Ъ?· ?
?ВП ВМ Л, Ы
Ф???
О ВМ ЛВ ФУ ЪУ Н?П Л.
1. Введение
2. Описание модели
Предлагается рассмотреть микроскопическую
модель транспортных потоков на примере крупного
города. В основе модели лежит схема следования за
лидером [7], вычисления происходят аналогично схеме предиктор-корректор [8]. В модели учитываются
различные изменения потока: скоростные характеристики транспортных средств, сужение магистралей, смены сигналов светофоров, случайный старт
транспортных средств, с заданным пунктом назначения, транзитный поток машин через город и т.п.
В качестве топологической основы модели
используется неориентированный граф. Схема
транспортной сети состоит из ребер графа как дорог
и вершин, так и перекрестков. Модель работает по
тактам. Время, соответствующее одному такту системы, обозначим Dt и будем считать сравнимым со
временем реакции водителя, т.е. 1?2 секунды.
??????-?????????????? ?????
Одной из первых задач, способствующей развитию моделирования транспортных потоков, стал
анализ пропускной способности дорог и перекрестков. Пропускной способностью принято считать максимально возможное число транспортных средств,
которое может проехать через сечение дороги за
единицу времени.
Во второй половине 40-х годов и в 50-е годы ХХ века в СССР и США большое внимание было уделено
изучению начально-краевых задач для уравнения
типа закона сохранения. Так, в 1955 г. в работах [1, 2]
была предложена, по-видимому, первая макроскопическая модель однополосного транспортного потока,
названная впоследствии моделью Лайтхилла?Уизема?
Ричардса, в которой поток транспортных средств
рассматривается как поток одномерной сжимаемой
жидкости. После было предложен ряд модификаций
данной модели (модель Танака, модель Уизема, модель
Пэйна и др.).
Микроскопические модели транспортного потока появились несколько позднее. В основе подходов
лежит концепция «о желании придерживаться при
движении безопасной дистанции до лидера». Так, в
1961 году Ньюэллом была предложена модель [3],
которую можно считать первой микроскопической
моделью. В ней постулируется, что для каждого водителя существует «безопасная» скорость движения,
зависящая от дистанции до лидера. Другим важным
классом микроскопических моделей (наряду с моделями оптимальной скорости) являются модели следования за лидером [4?7].
В 1959 г. сотрудники концерна Дженерал Моторс
Д. Газис, Р. Херман, Р. Потс [6] предложили одну из
первых (первыми, по-видимому, были модели А. Рашеля (1950) и Л. Пайпса (1953)) нетривиальных микроскопических моделей однополосного транспортного
потока, с помощью которой можно получить фундаментальную диаграмму.
Ф. Хейт был первым, кто выделил исследование
транспорных потоков в отдельный, самостоятельный
раздел математики.
Сегодня имеется обширная литература по изучению и моделированию автотранспортных потоков.
Несколько академических журналов посвящены исключительно динамике автомобильного движения.
Наиболее крупными являются Transportation Research, Transportation Science, Mathematical Computer Simulation, Operation Research, Automatica, Physical Review E, Physical Reports. Количество публикуемых статей исчисляется сотнями.
На сегодняшний день проблемы исследования
транспортных систем являются крайне важными и
в ряде стран возведены в ранг проблем национальной
безопасности.
37
?????? ??????? ??????? ? 3 (103) 2011
Транспортное средство представляет собой точку
на ребре графа, которая имеет два параметра: xi ?
положение на ребре графа и vi ? скорость.
Так как движение определяется лидером, то будем
считать его скорость известной: стремится к максимальной либо равна нулю перед перекрестком с красным сигналом светофора. Тогда можно спрогнозировать скорости остальных участников движения:
получаем целый спектр задач, лежащих между «эгоистичной» и «дружественной» моделями.
Очевидно, что результатами расчетов будут являться скорости и положения всех транспортных
средств.
xi(t)+vi(t+Dt)Dt?xi+1(t)?vi+1(t+Dt) Dt=Su,
Для проверки соответствия предложенной модели
реальным ситуациям, возникающим при движении
автотранспорта, естественным образом возникает
необходимость построения типичных тестовых
ситуаций. Естественной ситуацией, вытекающей из
самых первых строк формулировки модели, является
ситуация (рис. 1), в которой транспортные средства
движутся по дороге (ребру) в сторону вершины, пересекают ее, и продолжают движение уже по следующей дороге. Система состоит из двух ребер (рис. 1).
На данном этапе светофоры не помещены в вершины, что позволяет транспортным средствам перемещаться с одной дороги на другую без остановок.
Транспортные средства генерируются случайным образом на первом ребре. В качестве пункта назначения
выбирается точка на втором ребре. Данная ситуация
позволяет проверить корректность схемы в части вычисления прогнозируемых положений транспортных
средств через дискретные интервалы времени.
Добавляя светофоры в вершины графа, переходим
к моделированию ситуации (рис. 2), которая получила название «работа Т-образного перекрестка». Отличие этого случая от предыдущего кроме дополнительного ребра, заключается в наличии светофора на
перекрестке (в вершине). В данной ситуации транспортные средства «генерируются» на первой и второй дороге, а их целью является достижение конца
третьей. Красный и зеленый сигналы светофора горят одинаковое количество времени.
Данная ситуация позволяет моделировать образование пробок и вычислять критическую плотность
транспортных средств, при которых возникают пробки. Отметим, что в этой ситуации статистически
показано преимущество «дружественной» модели
перед «эгоистичной». Для получения сравнительных
результатов было использовано 10000 тестов на
каждую из обеих стратегий (табл. 1). При этом загруженность дроги, т.е. количество генерируемых транспортных средств M от 10 до 60 на ребро. Таким образом были получены сравнительные относительные
результаты T1avg / T2avg, где T1avg ? среднее время
прохождения теста с использованием 1й стратегии,
а T2avg ? соответственно 2-й.
Следующая ситуация будет несколько сложнее
(рис. 3). В данном примере рассматривается решетка
из 49 перекрестков (вершин), некоторые из которых
соединены дорогами (ребрами) с другими. Транспортные средства случайным образом генерируются на
случайных дорогах. Каждому из них задается случайный пункт назначения и просчитывается оптимальный маршрут для его достижения. Затем транспортное средство включается в движение. Варьируя количество транспортных средств, генерируемых на
каждом такте системы, можно загружать сеть различным количеством транспортных средств, выявляя
места, в первую очередь подверженные образованию
пробок. Будем называть подобные решетки регионом.
Данная модель позволяет поставить задачу нахождения оптимальной работы светофоров для максимальной «прокачки» транспортных средств через
регион. Без потери общности зададим время работы
(1)
i=1,..., M
где xi(t) и vi(t) ? это положение и скорость транспортного средства в момент времени t, u ? минимально допустимое расстояние между машинами, S ?
параметр, накладывающий ограничение на максимальную скорость, M ? количество транспортных средств
на дороге (ребре).
Следует учесть, что транспортное средство, начинающее движение в момент времени t, вклинивается в поток машин, если ему не мешают другие транспортные средства, т.е. выезд открыт и скорость выезда достаточна, чтобы не совершилось столкновение. Также, транспортное средство, заканчивающее
движение на магистрали, т.е. имеющее конечный
пункт назначения на ребре графа, влияет на движение остальных транспортных средств, участвующих
в движении. Поэтому желательно рассматривать более мелкие моменты времени Dt, считая решение (1)
«предиктором» к решению, к которому в момент
времени t стремятся транспортные средства. В этом
случае временем соответствующим одному шагу
системы будет Dt, значение которого выбирается на
несколько порядков меньше, чем Dt. Таким образом,
предлагается, основываясь на прогнозируемых значениях, полученных в (1), вычислять уточненные значения по следующим формулам:
x i (t + Dt) = x i (t) + v i (t)Dt + a(x i )(
v i (t + Dt) = v i (t) + a(x i )
v i (t + Dt) - v i (t) 2
)Dt (2)
Dt
v i (t + Dt) - v i (t)
Dt ,
Dt
(3)
??????-?????????????? ?????
где vi(t+Dt) найдено из (1), а a(x) ? это коэффициент,
имитирующий сужение дороги, или ограничение ускорения на повороте. Далее, принимая за t уже момент t+Dt, продолжим расчет на следующем шаге.
Отметим, что формула (1) описывает только одну
из возможных стратегий, при которой транспортное
средство ориентировано только на лидера, впереди
идущее транспортное средство, или светофор. Назовем эту стратегию «эгоистичной». Можно предложить и другие стратегии, когда транспортное средство ориентируется не только на лидера, например,
когда предиктор работает согласно выражению:
38
-x i -1(t) - v i -1(t + Dt)Dt + 2(x i (t) + v i (t + Dt)Dt) - x i +1(t) - v i +1(t + Dt)Dt = 0.
(4)
Например, (4) моделирует движение военной
техники в составе колонны. Зная скорость лидера,
мы можем рассматривать (4) как трехдиагональную
систему уравнений. Такая «дружественная» стратегия
позволяет передавать информацию о пробке вверх
по потоку. Отметим, что, считая правую часть (4)
за отрицательное число, например, кратное u, мы
2. Моделируемые ситуации и постановки
оптимизационных задач
Рис. 2. Т-образный перекресток
?????? ??????? ??????? ? 3 (103) 2011
Рис. 1. Пересечение узла
светофоров функцией сдвига фаз относительно
основной частоты колебаний w, b 1,...,b P, где P ? это
число светофоров в регионе. По определенным путям
или направлениям через регион следует транзитный
транспорт (рис. 4) средняя скорость которого при
пересечении региона является целевой функцией, которую нам необходимо максимизировать с помощью
выбора значений фаз.
В результате численных экспериментов с применением случайного поиска для нахождения такого
набора b 1,...,b P, что средняя скорость прохождения
через регион v1avg после поиска оптимального набора
b 1,...,b P была бы больше средней скорости прохождения через регион v0avg до поиска, была показана
возможность заметно улучшить среднюю скорость
прохождения при небольшой загруженности дорог
(табл. 2), например, при количестве транспортных
средств от 1 до 4 на 100 метров. Так же получены
результаты поиска зависимости времени нахождения в стоящем положении tvmin, и при максимальной
скорости tvmax, от загруженности дороги.
Данная задача является в некотором смысле развитием задачи поиска так называемой «зеленой волны».
Вопрос о классе данной оптимизационной задачи
в настоящее время открыт.
3. Распараллеливание при моделировании
и оптимизации движения транспорта
в нескольких регионах
Рис. 3. Регион
Таблица 1
Сравнение стратегий
поведения
M
T1avg / T2avg
10
1.313
20
1.274
30
1.23
40
1.192
50
1.13
60
1.08
4. Заключение
Рис. 4. «Прокачка» через регион
Как показывает опыт вычислений, число контролируемых транспортных средств при подобном моде-
??????-?????????????? ?????
Решение рассмотренных частных задач моделирования и оптимизации естественным образом приводит нас к требованию максимального повышения
производительности вычислений. Как показывают
расчеты, движение в режиме реального времени
транспортных средств в количестве 100 000 единиц
моделируется одним процессором, но задачи моделирования большей размерности и особенно оптимизационные задачи требуют повышения скорости вычислений на порядки.
Например, если речь идет об управлении движением транспорта, то число расчетов по необходимости должно быть велико, и они должны происходить
существенно быстрее.
Наиболее естественная схема распараллеливания? это группировка ребер (дорог) в регионы, где
расчеты происходят независимо, таким образом,
чтобы связи между ними были минимальны и обмен
ограничивался передачей контроля над транспортными средствами, пересекающими границу региона
(рис. 5). На представленной схеме индекс ребра или
вершины отвечает номеру процессора (индекс вершины? это номер процессора, отвечающего за светофоры).
В качестве примера распараллеливания по регионам
можно привести схему районов г. Омска (рис. 6а), на которой приведены три крупных района г. Омска: Советский (I), часть Первомайского (II) и часть Кировского (III).
Соединения между ними осуществляются по единственному мосту и одной магистрали Красный путь.
Интенсивность «серого» (рис. 6б) соответствует насыщенности транспортного потока. По результатам
расчетов можно сделать вывод о соответствии между
модельными «пробками» и «пробками», образующимися на практике.
39
?????? ??????? ??????? ? 3 (103) 2011
Таблица 2
?
tvmin
tvmax
v0avg
v1avg
1
24.5
81.37
10.7
12.3
2
34.8
69.4
9.5
10.7
3
48.56
43.74
8.43
9.52
4
67.13
25.1
7.16
8.04
5
85.79
10.88
6.24
6.89
6
111.2
1.4
5.1
5.57
7
146.4
0
4.78
5.26
Рис. 6а, г. Омск
Рис. 6б, г. Омск
Рис. 5. Разбивка по регионам
лировании может достигать чисел порядка 10 6 и время расчета вариантов движения существенно меньше, чем время реализаций этих вариантов в действительности. Также представляется перспективным перенести часть массовых вычислений на графические
процессоры, выбирая оптимальные размеры региона
или специальным образом распараллеливать вычисления на обычные и графические процессоры [9].
6. Helbing D. Traffic and related self-driven many particle
systems // Reviews of modern physics. 2001. V. 73. No 4. P.
1067?1141.
7. Швецов, В. И. Математическое моделирование транспортных потоков / В. И. Швецов // Автоматика и телемеханика. ? 2003. ? № 11. ? С. 3?46. ? ISSN 0005-2310.
8. Марчук, Г. И. Методы вычислительной математики / Г.
И. Марчук. ? М. : Наука. Главная редакция физико-математической литературы, 1980. ? 536 с.
9. Файзуллин, Р. Т. Применение гибридной суперкомпьютерной системы в задачах криптоанализа / Р. Т. Файзуллин,
А. А. Свенч, И. Г. Хныкин // Доклады ТУСУР. ? Томск :
ТУСУР, 2010. ? №1 (21), ч. 1. ? C. 61?63.
Библиографический список
??????-?????????????? ?????
1. Lighthill M. J., Whitham G. B. On kinematic waves: II.
Theory of traffic flow on long crowded roads // Proc. R. Soc.
London, Ser. A. 1955. V. 229. P. 281?345.
2. Richards P. I. Shock Waves on the Highway // Oper. Res.
1956. V. 4. P. 42?51.
3. Newell G. F. Nonlinear effects in the dynamics of car ?
following // Oper. Res. 1961. V. 9. P. 209?229.
4. Traffic flow theory: A state-of-the-art report. Editors N.H.
Gartner, C. J.1 Messer, A. K. Rathi. Washington DC: Transportation
Research Board, 2001.
5. Kerner B. S. Introduction to modern traffic flow theory and
control. The long road to three-phase traffic theory. Springer,
2009.
40
СОЛОВЬЁВ Вадим Анатольевич, аспирант кафедры
«Комплексная защита информации», радиотехнический факультет.
ФАЙЗУЛЛИН Рашит Тагирович, доктор технических
наук, профессор (Россия), профессор, заведующий
кафедрой «Комплексная защита информации».
Адрес для переписки: e-mail: v.a.solovev@gmail.com
Статья поступила в редакцию 27.06.2011 г.
© В. А. Соловьёв, Р. Т. Файзуллин
Документ
Категория
Без категории
Просмотров
8
Размер файла
333 Кб
Теги
времени, двумя, моделирование, масштабах, потоков, математические, основы, схема, транспортной
1/--страниц
Пожаловаться на содержимое документа