Буслаев А.П., Лебедев А.А., Яшина М.В. Моделирование потоков на графах. Теоретические и вычислительные аспекты. Часть 1. NODE-модель трафика

Подождите немного. Документ загружается.

Московский автомобильно-дорожный

государственный технический университет (МАДИ)

А. П. Буслаев, А. А. Лебедев, М. В. Яшина

Моделирование потоков на графах.

Теоретические и вычислительные аспекты.

Часть 1. NODE — модель трафика

Москва 2011

Оглавление

Введение 5

1 Динамические системы на графах 5

1.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Начало работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.3 Генерация произвольного графа . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 Генерация вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.2 Создание ребер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3.3 Ввод начального количества вещества на ребрах графа . . . . . 11

1.3.4 Ввод матрицы перемешивания в сложных узлах . . . . . . . . . 12

1.3.5 Определение параметра α . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Динамическое моделирование . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5 Коррекция введенной структуры графа . . . . . . . . . . . . . . . . . . 14

1.6 Задания для самостоятельной работы . . . . . . . . . . . . . . . . . . . . 15

2 Динамические системы с управлением 18

2.1 Задачи пакета FlowNetworkB.exe . . . . . . . . . . . . . . . . . . . . . . . 18

2.2 Начало работы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2.1 Создание вершин . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.2 Создание ребер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2.3 Коррекция графа . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.4 Количество вещества . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3 Управление потоками в вершинах . . . . . . . . . . . . . . . . . . . . . . 23

2.4 Запуск моделирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.4.1 Моделирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.4.2 Результаты моделирования . . . . . . . . . . . . . . . . . . . . . . 29

2.5 Поведение модели при нестандартных планах регулирования . . . . . . 30

2.6 Задания для самостоятельной работы . . . . . . . . . . . . . . . . . . . . 32

3 Динамические системы с управлением и заторами 35

3.1 Теоретические основы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1.1 О потоках на транспортном цветке с управлением . . . . . . . . 38

3.1.2 Характеристики потока на элементарном контуре . . . . . . . . 41

3.1.3 Оптимизация работы потока на элементарном контуре . . . . . . 42

3.1.4 Оптимизация работы потока на транспортном цветке . . . . . . 44

3.1.5 Оптимизация массы потока на лепестках . . . . . . . . . . . . . . 45

3.1.6 Динамическая система Инь-Янь с управлением . . . . . . . . . . 45

3.2 Работа с пакетом FlowNetworkC.exe . . . . . . . . . . . . . . . . . . . . . 52

3.3 Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

3.3.1 Одинарный контур с регулятором (светофором) . . . . . . . . . 58

3.3.2 Два контура с общим регулятором . . . . . . . . . . . . . . . . . 60

3.3.3 Четыре контура (лепестка) с распределением потоков в общем

регуляторе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

3.4 Задания для самостоятельной работы . . . . . . . . . . . . . . . . . . . . 69

4 Модель дорожной сети г. Москвы 73

4.1 Установка карты г. Москвы в качестве фона . . . . . . . . . . . . . . . . 73

4.2 Задание узов и ребер графа . . . . . . . . . . . . . . . . . . . . . . . . . 76

4.3 Сохранение промежуточных результатов работы . . . . . . . . . . . . . 78

4.4 Открытие файла для продолжения работы с ним . . . . . . . . . . . . . 78

4.5 Масштабирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.6 Импорт . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4.7 Параметры ребер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

4.8 Параметры узлов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.9 Процесс моделирования . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

4.10 Емкости . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.11 Задания для самостоятельной работы . . . . . . . . . . . . . . . . . . . . 91

5 Комментарии к реализации FlowNetworkMoscow.exe 94

5.1 Файл Program.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.2 Файл AnyClassesAndFunctions.cs . . . . . . . . . . . . . . . . . . . . . . . 94

5.3 Файл ValidatorsLibrary.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.4 Файл Styles.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.5 Файл Node.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.6 Файл EdgeBase.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5.7 Файл RealEdge.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

5.8 Файл Distributor.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

5.9 Файл SourceEdge.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.10 Файл DrainEdge.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.11 Файл Capacity.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

5.12 Файл EdgePainter.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.13 Файл Graph.cs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5.14 Другие файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

6 Задачи по реализации FlowNetworkMoscow 100

6.1 Расчет длины графа . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

6.2 Статистика: распределение ребер в графе по длине и количеству полос 100

6.3 Авторазделение ребер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

6.4 Интерфейс: всплывающие подсказки . . . . . . . . . . . . . . . . . . . . 103

Литература 103

Введение

Описание динамики потоков на улично-дорожных сетях яв-

ляется сложной задачей.

Математическая модель потоков на графе представляет со-

бой систему нелинейных дифференциальных уравнений, где

каждое уравнение соответствует определенной стороне неко-

торого ребра. Состояние потока на стороне ребра описывается

тремя характеристиками: плотностью ρ, интенсивностью q и

скоростью v. Плотность — это отношение количества частиц

(автомобилей) на стороне ребра — в случае транспортных по-

токов это может быть многополосная дорога — к длине ребра.

Интенсивность — количество частиц, проходящих через се-

чение за единицу времени. Скорость потока — это отношение

интенсивности к плотности.

Таким образом, первые две характеристики являются из-

меряемыми величинами. Относительно скорости предполага-

ем, что существует зависимость, определяющая скорость как

функцию плотности и некоторых других факторов.

Распределение потоков в узлах описывается марковской мат-

рицей перемешивания.

Одна из основных задач исследования — устойчивость

движения, наличие стационарных состояний, детектирова-

ние кризисов.

1. Динамические системы на графах.

Пакет FlowNetworkA.exe

1.1. Постановка задачи

Программа FlowNetworkA.exe позволяет моделировать раз-

личные структуры графов и получать характеристики пото-

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

Требуется смоделировать движение потока материи по реб-

рам связного ориентированного графа. По каждому ребру ма-

терия может двигаться в одном или двух направлениях.

Скорость движения зависит от плотности потока на реб-

ре. Если N - количество частиц на стороне ребра длины d, то

x = N/d – плотность потока. При этом 0 ≤ x ≤ x

, x

максимальная плотность потока.

Пусть α – параметр, 0 ≤ α < ∞. Тогда скорость потока

v(x) = v

(

1 −

)

, 0 ≤ x ≤ x

, (1.1)

где v

- максимальная разрешенная скорость.

Интенсивность потока — количество частиц, проходящих

через сечение ребра в единицу времени, — равна

f(x) = xv

= v

(

1 −

)

. (1.2)

Для моделирования автотранспортных потоков можно при-

нять:

1) v

= 60 км/ч (для городского движения);

2) x

= [120 – 140] 1/км.

Генерация графа происходит на прямоугольном поле пик-

селей. Размеры поля: 570 на 570 пикселей. Отсчет ведется от

левого верхнего угла. Для перехода в физические измерения

введем коэффициенты, переводящие пиксели в км:

, p

) → (k

, k

), (1.3)

где k

– количество километров, соответствующее одному пик-

селю по горизонтали и k

– соответственно, по вертикали.

Простой вершиной графа будем называть вершину с од-

ним входом и одним выходом. Любая другая вершина будет

называться кратной. В этом случае перераспределение по-

тока в вершине задается марковской матрицей. Для каждо-

го входного ребра каждой вершины заданы коэффициенты,

определяющие, в каких отношениях будет распределяться по

выходным ребрам материя, приходящая с этого ребра. Тре-

буется визуализировать полученную модель.

В ходе выполнения индивидуального задания необходимо:

1) задать параметры v

и x

;

2) определить вершины;

Рис. 1. Окно программы FlowNetworkA сразу после запуска

3) задать граф, в котором ребра могут быть однонаправ-

ленные или двунаправленные;

4) задать начальное количество вещества на ребрах графа;

5) задать таблицы коэффициентов распределения для каж-

дой вершины;

6) задать параметр α в формуле (1.1) v(x);

7) произвести просчет изменения количества вещества на

ребрах с течением времени.

Количество вещества на каждом ребре в каждый момент

выводится в числовом виде и отображается на графе в виде

толщины линии этого ребра (т. е. производится визуализа-

ция). В случае, если количество вещества на ребре достигнет

критического максимального значения, моделирование оста-

навливается.

Кроме того, реализованы возможности изменения положе-

ния вершин графа (и, соответственно, изменения длины ре-

бер) и удаления ребер и вершин (со связанными с ними реб-

рами).

1.2. Начало работы

Для того, чтобы начать работу, нужно запустить програм-

му FlowNetworkA.exe. На рис. 1 показан начальный интер-

фейс программы.

Основное меню содержит следующие три опции:

—

Файл

- обслуживает операции открытия новых и со-

храненных структур графа и потоков на нем, а также сохра-

нения созданных моделей. Отметим, что при каждом вызо-

ве опции открывается новое графическое окно, т.е. возможна

параллельная обработка нескольких моделей одновременно в

разных окнах;

—

Окно

- фиксирует и отображает имена открытых гра-

фических окон;

—

Упорядочить окна

- позволяет изменять геометриче-

ское расположение открытых графических окон относитель-

но фона и друг друга.

На рис. 2 показано подменю опции

Файл

Рис. 2. Подменю опции файл

Опция Новый открывает окно для создания модели и вво-

да ее параметров.

Опция Открыть позволяет выбрать с диска и открыть со-

храненную структуру модели - файл *.ptk (собственный фор-

мат данных). После выбора мышью файла - структуры моде-

ли соответствующий граф отображается в открытом графи-

ческом окне.

Опция Выход прекращает работу программы.

Рис. 3. Подменю опции Упорядочить окна

Опция

Упорядочить окна

изначально не имеет подменю.

Оно начинает генерироваться при открытии графических окон

в предыдущем пункте меню.

На рис. 3 показано подменю опции

Упорядочить окна

1.3. Генерация произвольного графа

Предположим, что необходимо создать новый граф. Тогда

следует выбрать в меню команду

Файл

→

Новый

При этом открывается графическое окно с полем отобра-

жения графа и блоком текстовых полей для введения необхо-

димых парамеров моделирования, рис. 4.

Рис. 4. Окно для создания и редактирования нового графа

1.3.1. Генерация вершин

Для того, чтобы создать вершину графа в нужной позиции

поля, нужно навести курсор с помощью мыши в нужное место

и нажать левую клавишу мыши. При этом возникает окно с

запросом имени вершины, рис. 5.

Рис. 5. Ввод вершины

В текстовом поле необходимо ввести имя вершины и на-

жать кнопку ОК . Как правило, именем вершины является

ее порядковый номер, но можно ввести и буквенные симво-

лы. После нажатия кнопки ОК появляется желтая точка,

обозначающая вершину и рядом с ней - ее имя, рис. 6.

1.3.2. Создание ребер

Для того, чтобы создать ребро, надо щелкнуть на началь-

ной вершине и, не отпуская кнопки мыши, перевести курсор

на другую вершину. При этом появится черная стрелка в ука-

занном направлении и возникнет текстовое окно с запросом

имени ребра, рис. 7. Заметим, что в информационном поле

появилось описание ребра, см. выделенный овал на рис. 7.

Можно сделать ребро двунаправленным. Для этого надо

щелкнуть на оконечной вершине ребра и, не отпуская кнопки

Рис. 6. Введенные вершины

мыши, перевести курсор на начальную вершину. После этого

появится стрелка с противоположным направлением зелено-

го цвета. Имя ребра снова задавать не нужно, оно одно для

обоих направлений рис. 8.

1.3.3. Ввод начального количества вещества на ребрах графа

Открытие соответствующего диалогового окна производит-

ся командой

Граф

→

Ввод количества вещества на ребрах

Для каждого ребра можно задать количество материи на

нем, движущейся в прямом и, возможно, обратном направле-

ниях, рис. 9. Количество вещества на ребре не должно пре-

вышать длины ребра, умноженной на x

После этого количество вещества на ребрах графа будет

показано толщиной линии, рис. 10.