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

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

среднюю мощность.

Неотрицательная величина

∗

∫

x (t) dt (12)

является средней длиной очереди за рассматриваемый сег-

мент времени.

Если C - масса потока на контуре, то решение T

∗

уравнения

∗

∫

f (ρ (t)) dt = C (13)

определяет среднее время оборота потока.

Пусть T

∗

min

= min T

∗

, тогда величина

∗

− T

∗

min

∗

min

называется относительной задержкой.

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

Пусть θ(t) — любая бинарная {0, 1} функция, которая обес-

печивает посредством конечного числа переключений перио-

дическое изменение параметров системы, T — период.

Тогда на фазовой кривой каждая точка траектории прохо-

дит четное количество раз в противоположных направлениях

с соответствующей направлению скоростью. При этом отно-

шение скоростей в силу параллельности касательных векто-

ров пропорционально отношению, например первых коорди-

нат |

x|, т.е.

{

(|s − f(ρ)|, f(ρ)), if x > 0,

(0, f(ρ)), if x = 0.

Следовательно, при x > 0 вклад работы траектории в окрест-

ности фиксированной точки x, ρ на взаимно противополож-

ных направлениях равен

(1 − x)f(ρ) + sx)f(ρ) + (s − f(ρ))(1 − x)f(ρ)

√

(s − f(ρ))

+ (f(ρ))

sf(ρ)

√

(s − f(ρ))

+ (f(ρ))

. (15)

Значит, на фазовой траектории наиболее значимыми точками

будут те, для которых достигается максимум M

Аналогично в случае x = 0 получаем

= (1 − x)f(ρ) + sx = f(ρ). (16)

Максимальное значение функции M

(16) часто называют

пропускной способностью транспортной сети. В случае (15)

не зависит явно от длины очереди x

√

(

f(ρ)

− 1)

+ 1

. (17)

Экстремум функции (17) достигается в точках,

где

(

f(ρ)

− 1

)

′

⇔ f

′

(ρ) = 0 или S = f(ρ).

Но поскольку S > max

0≤ρ≤1

f(ρ), то точки экстремума для (16)

и (17) совпадают ρ

∗

= 0 , 5 при условии, что удовлетворяются

ограничения.

Следовательно, в случае x > 0 получаем

0, 5(1 − x) + 1 · x = C, (18)

откуда x = 2C − 1. Значит, при C ≥ 1/2 имеем следующую

оптимальную точку на фазовой плоскости

∗

= 2 C − 1, ρ

∗

= 0, 5. (19)

При C <

в силу

(

f(ρ)

− 1)

= 1

≤ (

f(ρ)

− 1 + 1)

получаем, что

≥ S/(S/f(ρ)) = f(ρ) = M

. (20)

Таким образом, при C <

оптимальная точка на фазовой

плоскости

∗

= 0+, ρ

∗

= C. (21)

Периодические колебания в окрестности точки (19) фазо-

вой плоскости оптимизируют работу потока при C >

и в

правой окрестности точки (21) — в случае C <

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

Рассмотрим множество режимов функционирования узла

следующего вида: пусть

0 < T

< T

+ T

< T

+ T

S < T

+ T

+ ... + T

= T.

Для лепестка с номером i определим (0 ≤ t ≤ T )

(t) =

{

1, T

+ ˙s + T

i−1

< t < T

+ · · · + T

i−1

+ T

0, else.

По прошествии времени T функции периодически повторя-

ются.

Для упрощения предположим, что

≥ C

, i = 1, . . . , n, (22)

т. е. в каждом цикле очередь "рассасывается". Значит, начи-

ная со второго цикла, поведение потоков на каждом лепестке

имеет тот же период T независимо от начальных условий.

С точностью до замены переменных можно считать, что для

∀1 ≤ i ≤ n :

1) в начальный момент масса распределена равномерно по

лепестку ρ

= C

и интенсивность движения f(ρ

);

2) в течение времени 0 < t < T − T

узел перекрыт и на-

капливается очередь со скоростью f(ρ

(t));

3) затем в течение некоторого промежутка (T −T

, T −T

)

0 < α

≤ 1 , происходит "рассасывание"очереди;

4) наконец, при t ∈ [T − T

, T ] масса равномерно распре-

делена по кольцу.

Число α

однозначно определяется параметрами C

и T

1 ≤ i ≤ n.

Обозначим через A(C

, T

, T ) работу потока на лепестке с

номером i. Тогда цель оптимизации состоит в поиске распре-

деления вектора T

, 1 ≤ i ≤ n такого, что

i=1

A(C

, T

, T ) → max = A(C

, ..., C

, T ) (23)

при условии

i=1

= T, (24)

≥ C

/S, i = 1, ...n. (25)

Ясно, что для корректности постановки задачи (22) - (25)

необходимо, чтобы

T ≥ C/S,

где C− полная масса потока на цветке.

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

Задача

A(C

, ..., C

, T ) → max (26)

при условии

i=1

= C (27)

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

боте потока фиксированной массы C на цветке. Например,

достаточное условие того, что решение (25) достигается на

векторе с равными координатами состоит в том, чтобы функ-

ция A была вполне положительной или если бы все Θ

≡ 1 .

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

Поток Инь-Янь

Рассматривается граф с двумя узлами и соединяющими их

ребрами с односторонним движением. Пусть длины ребер рав-

ны 1.

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

дующим вектором:

((x

, ρ

max

), (y

, ρ

)) , i = 1, 2, (28)

где x

– часть ребра, входящего в i-вершину, на котором плот-

ность потока максимальна (накопитель), (y

, ρ

) – остальная

часть ребра и соответствующая плотность потока.

Рис. 41. Инь-Янь

Будем считать, что ρ

max

= 1. Пусть C - масса потока на

графе, константа для замкнутой системы.

Предположим, что

f(u) = u(1 − u) (29)

- интенсивность потока плотности u, 0 ≤ u ≤ 1. Пусть S -

интенсивность убывания потока максимальной плотности пе-

ред соответствующим узлом (перекрестком), R - максималь-

но возможная интенсивность на перекрестке (пропускная спо-

собность).

0 < S < R. (30)

Пусть далее θ

(t) - кусочно-постоянные функции, прини-

мающие значения 0 и 1, которые моделируют светофорную

сигнализацию на соответствующем перекрестке, где "0" – за-

прет движения, а "1" – разрешение.

Таким образом, для параметров (28) системы справедливы

следующие соотношения (i = 1, 2):

≥ 0, y

≥ 0 , (31)

+ y

= 1, (32)

0 ≤ ρ

≤ 1 = ρ

max

, (33)

· 1 + y

· ρ

+ x

· 1 + y

· ρ

= C. (34)

С учетом соотношений (31) – (34) состояние динамической

системы можно описать параметрами x

, ρ

, x

, ρ

, для ко-

торых справедливы следующие дифференциальные соотно-

шения:

(t) =

{

−θ

(t) S + f (ρ

) ; x

> 0,

− θ

(

))

(

) +

(

) (

(

)

− R

)

; x

= 0.

(35)

(ρ

(1 − x

))











(t) S − f (ρ

) ; x

> 0, x

> 0,

(t) S − θ

(t) min (f (ρ

) , R) ; x

> 0 , x

= 0 ,

(t) min (f (ρ

) , R) − f (ρ

) ; x

= 0 , x

> 0 ,

(t) min (f (ρ

) , R) − θ

(t) min (f (ρ

) , R) ; x

= 0 , x

= 0 ,

(36)

˙x

(t) =

{

−θ

(t) S + f (ρ

) ; x

> 0,

(1 − θ

(t)) f (ρ

) + θ

(t) (f (ρ

) − R)

; x

= 0.

(37)

(ρ

(1 − x

))











(t) S − f (ρ

) ; x

> 0, x

> 0,

(t) S − θ

(t) min (f (ρ

) , R) ; x

= 0 , x

> 0 ,

(t) min (f (ρ

) , R) − f (ρ

) ; x

> 0 , x

= 0 ,

(t) min (f (ρ

) , R) − θ

(t) min (f (ρ

) , R) ; x

= x

= 0 .

(38)

В уравнениях (35)-(38) использовано обозначение

(A − B)

= {A − B, A > B; 0, A ≤ B} .

Уравнения (35), (37) описывают динамику накопителей пе-

ред перекрестками в зависимости от функции управления θ

(t) ,

i = 1, 2. Уравнения(36),(38) отображают изменение массы на

основных частях звеньев в зависимости от состояния нако-

пителей ("пуст"( ⇐⇒ x

= 0), "непуст"( ⇐⇒ x

> 0)) и

функций управления перекрестками.

Рис. 42. Кратный узел

Цель работы состоит в исследовании свойств решений си-

стемы (35)-(38) в зависимости от параметров. В частности,

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

сценариев управления θ

(t) , i = 1, 2?

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

ного управления потоком, т.е. оптимизации управления по

мере получения информации о состоянии системы. Важный

частный случай: узлы 1 и 2 (рис. 41) моделируют пересекаю-

щиеся направления движения на одном перекрестке (рис. 42).

При этом естественно предположить, что

(t) + θ

(t) ≡ 1, (39)

т.е. в текущий момент времени одно направление открыто,

другое закрыто.

Как управлять таким перекрестком?

Простейший случай

Пусть в (35)-(38)

(

)

≡ θ

(

)

≡ 1, (40)

max f (s) ≤ min (S, R) = S. (41)

Система (35)-(38) принимает вид

˙x

(t) =

{

−s + f (ρ

) ; x

> 0

0; x

= 0

(42)

(ρ

(1 − x

))

{

s − f (ρ

) ; x

> 0, x

≥ 0

f (ρ

) − f (ρ

) ; x

= 0 , x

≥ 0

(43)

˙x

(t) =

{

−s + f (ρ

) ; x

> 0

0; x

= 0

(44)

(

− x

))

{

s − f (ρ

) ; x

≥ 0 , x

> 0

f (ρ

) − f (ρ

) ; x

≥ 0, x

= 0 .

(45)

Предположим, что в начальный момент заданы значения

1,0

, ρ

1,0

) , (x

2,0

, ρ

2,0

) .

Тогда из (42) следует, что либо x

≡ 0, либо x

(t) убывает

монотонно к нулю с отделенной от нуля скоростью, т. е. об-

ратится в нуль за конечное время. Аналогичное верно и для

(t). Таким образом,

(t) ≡ x

(t) ≡ 0, (46)

начиная с некоторого момента T

. Поэтому из (42)-(45) сле-

дует, что при t ≥ T

{

˙ρ

= f (ρ

) − f (ρ

)

˙ρ

= f (ρ1) − f (ρ

) .

(47)

При этом тождество (34) обращается в

+ ρ

≡ C. (48)

Система (47)-(48) исследована в [1], где установлено, что

при

C < ρ

max

= 1 (49)

для любых начальных условий решения сходятся к равновес-

ной точке

≡ ρ

≡

а при C > ρ

max

= 1 для любых начальных условий решение

(47)-(48) за конечное время выходит на границу

(ρ

≡ 1 , ρ

= C − 1) ∨ (ρ

= C − 1, ρ

≡ 1) ,

что соответствует затору.

Рис. 43. Перекресток 1-2

Тождественное управление и элементарный контур

Предположим, что

(t) ≡ θ

(t) ≡ θ(t) (50)

– периодические функции, причем на периоде T = T

+ T

имеется лишь одна перемена значения, т. е.

(t) = 1, 0 < t < T

; 0, T

< t < T , i = 1, 2.

Соотношение (41) предполагаем справедливым. Рассматри-

ваемый случай может быть интерпретирован следующим об-

разом.

На рис. 43 узлы 1 и 2 относятся к одному перекрестку, ко-

торый пересекает внешний по отношению к рассматриваемой

замкнутой системе поток.

Динамическая система (см. рис. 43) состоит из двух несвя-

занных контуров. Если положить θ

(t) = 1 − θ(t), то получим

элементарную систему с накопителем (рис. 44).

Для простоты будем считать, что x

= 1; ρ

max

, S и f(ρ)

определены ранее. Имеем следующие соотношения:

˙x

{

−θ

(t)S + f(ρ

); x

> 0,

(1 − θ

(t)) f (ρ

) ; x

= 0 .

(51)

(ρ

)

{

(t) S − f (ρ

) ; x

> 0,

− (1 − θ

(t)) f (ρ

) ; x

= 0.

(52)

Рис. 44. Элементарный контур

В зависимости от значения θ

получаем два вида автоном-

ных систем: если θ

= 1 , то

˙x

(t) =

{

−s + f (ρ

) ; x

> 0

0; x

= 0 ,

(53)

если θ

= 0 , то

(ρ

)

{

s − f (ρ

) ; x

> 0

0; x

= 0 .

(54)

Поскольку (ρ

)

= ˙ρ

+ ρ

˙y

= ρ

(1 − x

) − ρ

˙x

то при x

> 0

˙ρ

(1 − x

) = ˙ρ

+ (s − f (ρ

)) = (s − f (ρ

)) (1 − ρ

) ,

т.е.

{

˙ρ

(1−ρ

)

(1−x

)

(s − f (ρ

))

˙x

= − (s − f (ρ

))

, if x

> 0 . (55)

Из (55) следует, что

dρ

= −

(1 − ρ

)

(1 − x

)

откуда

(1 − ρ

) (1 − x

) = C. (56)

На квадрате области допустимых значений 0 ≤ x

, ρ

≤ 1

семейство (56) имеет вид, показанный на рис. 45.

В силу условия (41) x

монотонно убывает при открытом

узле (θ

≡ 1) .