Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков
Подождите немного. Документ загружается.
358
Рис. 2
Так на рис. 1 два запрещенных маневра:
P
1
= (AM, MC) и P
2
= (BM, MD).
На рис. 2 три запрещенных маневра:
P
1
= (AM
1
, M
1
D) и P
2
= (AM
1
, M
1
M
2
, M
2
F, FG) и P
3
= (M
1
M
2
, M
2
E).
Формальная постановка задачи
Задан ориентированный (для простоты в примерах будем рас-
сматривать неориентированный граф, каждому ребру без стрелок на
рис. 1, 2 соответствуют два ребра в разных направлениях) граф G без
петель и набор запрещенных маршрутов P. Маршрут P
i
– последова-
тельность ребер графа. Запрет проезда по маршруту P
i
означает запрет
проезда по всему маршруту начиная с первого ребра и заканчивая по-
следним. Проезд по любой части маршрута не запрещен. Требуется по-
строить такой граф H, в котором не будет запрещенных маневров. Каж-
дой вершине (ребру) графа G соответствует одна или несколько вершин
(ребер) графа H. Каждому разрешенному пути (чередующаяся последо-
вательность вершин и ребер) в графе G соответствует путь в графе H.
Запрещенному пути в графе не должно соответствовать ни одного пути
в графе H. Разрешенный путь в графе G – путь, не содержащий запре-
щенных маневров. Запрещенный путь в графе G – путь, содержащий
хотя бы один запрещенный маневр.
Все вершины графа G имеют вполне конкретный географический
смысл и находятся в некоторых различных точках земли. Различные
359
вершины графа H могут находиться в одной точке Земли, однако отра-
жать разное состояние.
На рис. 1 знание, что машина находится в точке M, не достаточно
для понимания, куда может ехать машина. В графе H вершине M будет
соответствовать три вершины:
1) если мы приехали из вершины А;
2) из вершины B;
3) из другой вершины.
Рассмотрим граф H для графа, изображенного на рис. 2. Светлым обо-
значены двусторонние дороги. Вершина
1
M
означает, что машина на-
ходится в вершине M
1
и запрещены следующие пути: {M
1
M
2
E, M
1
D,
M
1
M
2
FG}, вершина
2
M
находится в M
2
и запрещен путь M
2
E,
2
M
на-
ходится в M
2
и запрещены пути {M
2
E, M
2
FG}, F' находится в F и запре-
щен путь FG.
360
Используемые сокращения
м – метр, с – секунда, км – километр, ч – час, мин – минута
т.е. – то есть, т.д. – так далее, т.п. – тому подобное
др. – другие, см. – смотри, п. – пункт, пп. – пункты, г. – год
УДС – улично-дорожная сеть
ЗОС – загрязнение окружающей среды
LWR – Лайтхилл–Уизем–Ричардс
АТС – автотранспортное средство (автомобиль)
RRH – Риман–Ранкин–Гюгонио
E-условие – энтропийное условие О. А. Олейник
Г–Я – Гамильтон–Якоби, Г–Я–Б – Гамильтон–Якоби–Беллман
T.V. – total variation (полная вариация)
CTM – Cell Transmission Model (модель клеточных автоматов Даганзо)
IDM – Intelligent Driver Model (модель разумного водителя)
ПДД – правила дорожного движения
CA – Cellular Automata (клеточные автоматы)
СОДУ – система обыкновенных дифференциальных уравнений
КдФБ – Кортевег–де Фриз–Бюргерс
ДМ – Дженерал Моторс
F – free flow, S – synchronized flow, J – wide moving jam
СП – синхронизованный поток
ЛСП – локализованный синхронизованный поток
РСП – расширяющийся синхронизованный поток
МСП – мигрирующий синхронизованный поток
ОП – общей структурой плотного потока
ЕП – единой структурой плотного потока
ЕСП – единая структура синхронизованного потока
ЕОП – единая общая структура плотного потока
РОП – рассасывающаяся общая структура плотного потока
п.н. – почти наверное, н.о.р. – независимые одинаково распределенные
с.в. – случайная(-ые) величина(-ы), д.м.ц. – дискретная марковская цепь
E – Expected value (математическое ожидание), D – Dispersion (дисперсия)
Н.О.Д. – наибольший общий делитель
СЛАУ – система линейных алгебраических уравнений
TASEP – totally asymmetric exclusion process (полностью асимметричные
процессы с запретами)
LCD – linearized chord diagram (линейная хордовая диаграмма)
(R) – множество действительных чисел
(N) – множество натуральных чисел (1, 2, 3, … )
(Z) – множество целых чисел