авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:     | 1 ||

«Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики На правах ...»

-- [ Страница 2 ] --

Утверждение 2.5. Равновесный поток f в модели кольцевой автомагистрали однознач но определяется любой своей компонентой: например, по компоненте fK все остальные компоненты fi, i = 1,..., K 1 восстанавливаются однозначно.

Ясно, что величины fi монотонно не убывают как функции fK, то же самое можно сказать о величинах fi, i = 0,..., K 1. Вместе с утверждением 2.5 это приводит нас к следующему результату.

Утверждение 2.6. В модели кольцевой автомагистрали при недопустимом входном по токе существует не более одного равновесного потока со въездов r, для которого fi (r) = Fid по крайней мере для одного i.

Доказательство. Пусть существует два различных равновесных потока f 1, f 2 с указанным свойством. Поскольку любая компонента определяет весь равновесный поток (утвержде ние 2.5), то потоки f 1 и f 2 не совпадают ни в одной компоненте. Значит, существуют индексы i1 = i2, такие, что fi1 = Fid fi2, fi2 = fid fi1. Но это противоречит тому, что при увеличе 1 1 1 2 2 нии одной компоненты равновесного потока остальные компоненты не уменьшатся.

d Этот равновесный поток можно найти, отыскав значение потока fK [0, FK ], такое, что вычисленный согласно общему правилу поток f0 совпадает с заданным потоком fK, и хотя бы для одного i выполнено равенство fi = Fid.

После того, как найден равновесный поток с заданными свойствами, если он вообще существует, определяются множества I, Sm как в теореме 2.2, U и C по формулам (2.3), (2.4), индексы iu, ic как в модели незамкнутой автомагистрали. Множество равновесий в m m M пространстве n, как и прежде, представляется в виде декартова произведения E = Em.

m= Если ic iu = 1, то m m Em = {(num1 +1,... nuu, ncc,..., ncm )}, i im im i ic а если ic iu 1, то Em = h h Em, множества Em определены как в теореме 2.2.

m h=iu + m m m Вторая часть множества равновесий Во второй части множества равновесий для рав F d.

новесных потоков справедливы неравенства r r, f F d, то множество равновесий в пространстве n для фиксированных Поскольку f входных потоков r и потоков между ячейками f, согласно теореме 2.2, может состоять лишь из векторов nu и nc, а поскольку для всех i выполнено неравенство fi1 + ri Fis, следующее из неравенства fi Fid, и r r, то C =, поэтому множество E|r, если оно не пустое, состоит из единственного вектора: E|r = {nc }.

Множество E|r не пустое, если U =, то есть для всех i должно выполняться неравен ство fi1 /pf ri /pr, которое, с учетом равенства fi1 +ri = fi /if, равносильно неравенству i i fi1 pf fi /if. При этом для участков без въезда, то есть для таких i, что ri = 0, неравен i ство fi1 /pf ri /pr выполнено автоматически.

i i Заметим, что второй части множества равновесий в любом случае принадлежит точка r = 0, f = 0, n = nc = 0. Есть ли во второй части множества равновесий другие точки, зависит от величины K pf.

= i f i=1 i i : ri А именно, справедливы следующие три утверждения.

Утверждение 2.7. Если 1, то, кроме r = 0, f = 0, других равновесных потоков во второй части множества равновесий нет.

Доказательство. Пусть во второй части множества равновесий существует ненулевой рав новесный поток r, f. Все компоненты ненулевого равновесного потока между ячейками f строго положительны, поскольку, согласно утверждению 2.5, равновесный поток полностью определяется любой своей компонентой.

Поскольку fi1 = fi /if, если ri = 0, и fi1 pf fi /if, если ri 0, то i K pf fK = f0 fK = fK.

i f i=1 i i : ri Поскольку fK 0, то 1. Отсюда следует, что при 1 вторая часть множества равновесий не содержит ненулевых равновесных потоков.

Утверждение 2.8. Если = 1, то множество равновесных потоков во второй части множества равновесий есть однопараметрическое семейство pi fi ()/ f, ri 0, r K 1 i f fi () = pj, ri () = f j=i+1 j 0, ri = 0, ji, rj 0 max, где max = max{ : r() r, f () F d }. Причем если r(max ) = r или хотя бы для одного i выполнено равенство fi (max ) = Fid, то 0 max, поскольку потоки r(max ) и f (max ) принадлежат первой части множества равновесий.

равновесные потоки. Тогда fi1 = fi /if, если ri = 0, и Доказательство. Пусть r, f fi1 pf fi /if, если ri 0. Обозначим i 1, ri = 0, i = f p, ri 0.

i Тогда K K 1 1 2 i pf fK = f0 f1 f2 · · · fK = fK = fK = fK, i f ff f f 1 1 2 i=1 i i=1 i i : ri поэтому все неравенства должны выполняться как равенства: fi1 = i fi /if, или fi / f, ri = 0, i fi1 = p fi / f, ri 0.

f i1 i При этом 0, ri = 0, ri = fi /if fi1 = p fi / f, ri 0.

r i i Ясно поэтому, что множество равновесных потоков есть однопараметрическое семейство r(), f (), описанное в формулировке утверждения, = f0 = fK.

Утверждение 2.9. Если 1, то во второй части множества равновесий не более двух равновесных потоков, один из которых нулевой (r = 0, f = 0), а второй определяется следующим образом. Определим функцию () = f0 (), где fK () =, fi () fi () ri, p f fi1 () = max i1, i = K,..., 1.

if if Уравнение () = имеет ровно два решения, одно из которых = 0, а второе 0.

Если для всех i = 1,..., K выполнено строгое неравенство fi ( ) Fid, то второй нену левой равновесный поток из второй части есть f ( ), в противном случае вторая часть множества равновесий содержит лишь нулевой равновесный поток.

Доказательство. Во второй части множества равновесий в модели кольцевой автомагистра F d, n = nc, поэтому fi fid для всех i. Если ri ri, то ri ri и fi1 /pf = ri /pr, d ли f i i поэтому fi fi fi fi1 = pf ri ri.

= i if if if Если же ri = ri, то fi1 = fi /if ri и выполняется неравенство fi1 /pf ri /pr, поэтому i i fi1 pf fi /if. В обоих случаях i fi fi ri, pf fi1 = max i1. (2.8) if if Положим fK =. Тогда потоки fK1,..., f1, а также f0 определяются однозначно по форму ле (2.8). Для того, чтобы f был равновесным потоком, необходимо и достаточно, чтобы вы полнялось равенство f0 = fK и неравенства fi Fid, i = 1,..., K. При этом ri = fi /if fi [0, ri ].

Условие f0 = fK приводит к уравнению () = из формулировки доказываемого утверждения. Ясно, что нуль является корнем этого уравнения. Функция () есть максимум из 2K линейных по выражений, следовательно, функция (·) непрерывная и выпуклая.

При малых значениях, начиная с нуля, () =, поэтому производная функции () меньше единицы: () = 1. При очень больших значениях производная функции () K 1/if 1. Поэтому существует единственный строго положи больше единицы: () = i= тельный корень уравнения () =. Если f ( ) F d, поток f является равновесным потоком из второй части множества равновесий, если же f ( ) F d, и при этом хотя бы для одного i выполнено равенство fi ( ) = Fid, то f ( ) равновесный поток для первой части множества равновесий.

2.5 Об устойчивости равновесий Поскольку длина очереди q не входит в определение равновесия, необходимо опреде лить, что мы понимаем под устойчивым и неустойчивым равновесием. Для этого наложим некоторые ограничения на значения q в начальный момент времени.

Пусть в начальный момент времени t = 0 в очереди перед каждым въездом i есть d r столько автомобилей, что ri (0) = ri : если ri Ri, то qi (0) = ri /vi, если же ri = Ri, то r qi (0) Ri /vi. Величина n0 в модели незамкнутой автомагистрали также считается длиной d очереди, и для нее в начальный момент должно выполняться аналогичное условие, f0 (0) = f0, здесь и дальше это специально не оговаривается. При таких ограничениях на длину d очереди в начальный момент выполнено неравенство q(t) q(0) и, следовательно, ri (t) ri r для всех t. Действительно, если ri Ri, то di = ri, и если qi (t) qi (0) = ri /vi, то d r qi (t + 1) qi (t) + di ri (t) = qi (t) + di min{vi qi (t), Ri } r r qi (t)(1 vi ) + di qi (0)(1 vi ) + di = qi (0).

r Если же ri = Ri, то di Ri, и если qi (t) qi (0) Ri /vi, то d qi (t + 1) qi (t) + di ri (t) = qi (t) + di Ri qi (t) q0 (t).

Кроме того, если тройка (f, r, n) является равновесием и в начальный момент выполнено равенство rd (0) = r, то f (t) = f, r(t) = r, n(t) = n для всех t = 1, 2,.... Таким образом, вектор n (в случае незамкнутой автомагистрали вектор n не включает компоненту n0, то есть n = (n1,..., nK+1 )) однозначно определяет равновесные потоки f, r. Действительно, если в d d равновесии ri = ri, то в равновесии ri = ri. Если же в равновесии ri ri = ri (0), то d d d в равновесии ri = Ri. Согласно модели узла, если ri (t) ri (t), то при увеличении ri (t) величина ri (t) не изменится. Поэтому имеют смысл следующие определения.

Пусть ne равновесный вектор концентраций. Вектор ne назовем устойчивым рав новесием, если для любого сколь угодно малого 0 найдется 0, такое, что при n(0) ne и rd (0) = r выполнено неравенство n(t) ne для всех t = 1, 2,....

Вектор ne назовем асимптотически устойчивым равновесием, если он является устойчи вым равновесием и для некоторого 0 n(t) ne при t при любом значении n(0) из -окрестности вектора ne.

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

Разберем сначала некоторые частные случаи, а именно, исследуем устойчивость наиме нее загруженного и наиболее загруженного положения равновесия.

2.5.1 Устойчивость наименее загруженного равновесия Исследуем устойчивость равновесия n = nu в модели обычной и кольцевой автострады.

F d, то положение равновесия n = nu Утверждение 2.10. Если равновесный поток f устойчиво как в модели незамкнутой автострады, так и в модели кольцевой автострады.

F d, n = nu, то fis = Fis Fid /if fi /if = fi1 + ri, поэтому в Доказательство. Если f точке n = nu и в небольшой ее окрестности выполнены равенства fi = if vi ni, ri = ri = ri d для всех i.

Поэтому если n(t) находится в небольшой окрестности точки nu и rd (t) = r (и f0 (t) = f d в случае незамкнутой автострады), то ni (t + 1) = ni (t) fi (t)/if + fi1 (t) + ri (t) = ni (t)(1 vi ) + i1 vi1 ni1 (t) + ri, f rd (t + 1) = r и f0 (t + 1) = f0 в модели незамкнутой автострады.

d Следовательно, n(t + 1) nu = A(n(t) nu ), где f 1 v1 ··· 0 0 0 K vK f 1 v1 1 v2 ··· 0 0 f 2 v2 1 v3 · · · 0 0 A=.....

..

.....

.

.....

· · · 1 vK 0 0 0 f · · · K1 vK1 1 vK 0 0 в модели кольцевой автострады. В модели незамкнутой автострады n(t) обозначает вектор (n1 (t), · · ·, nK (t)), n(t + 1) nu = A(n(t) nu ), матрица A такая же, как в модели кольцевой автомагистрали, но правый верхний элемент a1K = 0, то есть матрица A нижнетреугольная.

Как в модели незамкнутой автострады, так и в модели кольцевой автострады опера = |x1 | + · · · + |xK |. Действительно, в обоих случаях тор A не увеличивает норму x K k k f if )vi )|xi | (|(1 vi )xi | + |i1 vi1 xi1 |) (1 (1 |xi | = x 1.

Ax = i=1 i=1 i= Отсюда сразу же следует, что положение равновесия n = nu при f F d устойчиво.

2.5.2 Устойчивость наиболее загруженного положения равновесия в модели кольцевой автострады Будем исследовать устойчивость наиболее загруженного положения равновесия в моде ли кольцевой автомагистрали, а именно, f = 0, r = 0, n = N.

Величина определяет устойчивость положения равновесия f = 0, r = 0, n = N.

А именно, имеет место следующее утверждение.

Утверждение 2.11. Положение равновесия f = 0, r = 0, n = N устойчиво, если и только если 1, и асимптотически устойчиво, если и только если 1.

Доказательство. В окрестности положения равновесия f = 0, r = 0, n = N состояние системы на шаге t + 1 зависит от состояния системы на шаге t линейно:

ni (t + 1) = ni (t) + fis (t) fi (t)/if = ni (t) + wi (Ni ni (t)) fi (t)/if, где s fi+1 (t), ri+1 = 0, fi (t) = f s p f (t), ri+1 0.

i i+ Обозначим 1/ f, ri+1 = 0, i i = pi / f, ri+1 0.

i K i. Обозначим (t) = N n(t). Тогда Отметим, что = i= i (t + 1) = i (t) wi i (t) + i wi+1 i+1 (t), то есть (t + 1) = A(t), где 1 w1 1 w2 ··· 0 0 1 w 2 2 w 3 ··· 0 0 1 w3 ··· 0 0 0 0 A=..

....

..

.....

.

..... ··· 1 wK 0 0 0 K1 wK ··· 1 wK K w 1 0 0 Все элементы матрицы A неотрицательны.

Если = 0, то i = 0 по крайней мере для одного i. Пусть, например, K = 0. Тогда матрица A верхнетреугольная, на главной диагонали стоят числа 1 wi (0, 1), следова тельно, At 0 при t, следовательно, (t) 0 при t для любого значения (0), то есть положение равновесия = 0 (n = N ) асимптотически устойчиво. Действительно, рас смотрим матрицы D = diag(1 w1,..., 1 wK ), S = A D. Матрица S верхнетреугольная, с нулями на главной диагонали, следовательно, S K = 0. Поэтому при t K, t N K t t Ctk Dtk S k, A = (D + S) = k= где Ctk биномиальный коэффициент:

t (t 1)... (t k + 1) t!

Ctk = tk.

= k!(t k)! k!

Далее, tk Dtk 0 при t, поскольку Dtk = diag((1w1 )tk,..., (1wK )tk ) и tk xtk при t, если |x| 1. Следовательно, At 0 при t.

Пусть 0. Тогда матрица A является неразложимой, и к ней можно применить тео рему Фробениуса Перрона (см. [44], глава XIII): существует положительное собственное значение матрицы A, такое, что все остальные собственные значения матрицы A не пре восходят его по модулю, этому собственному значению соответствует собственный вектор с положительными компонентами.

Рассмотрим характеристический многочлен матрицы A K K K K A () = det(E A) = ( 1 + wi ) ( 1 + wi ) i w i = wi.

i=1 i=1 i=1 i= Максимальное по модулю положительное собственное значение матрицы A является наи большим корнем характеристического многочлена A (). Заметим, что K K A (1 min wi ) = A (1) = (1 ) wi 0, wi, i i1 i= функция A () монотонно возрастает при 1 mini wi, и A () + при +. Сле довательно, для максимального корня характеристического многочлена A () выполнены следующие условия:

1, 1, то = 1, если = 1, 0 1 mini wi 1.

1, Кроме того, собственному значению соответствует собственный вектор с положительными компонентами. Отсюда сразу же следует, что при 1 положение равновесия = (n = N ) неустойчиво. Если же 1, то для любого (0), 0 (0), справедливо неравенство 0 (t) ( )t. Следовательно, положение равновесия = 0 (n = N ) устойчиво при 1 и асимптотически устойчиво при 1.

2.5.3 Устойчивость произвольного положения равновесия В силу монотонности системы (лемма 1.1), для выяснения устойчивости любого поло жения равновесия ne необходимо проверить лишь точки n ne и n ne.

Лемма 2.3. Для любого положения равновесия ne вектор n(t + 1) зависит от n(t) линейно в областях {n ne } { n ne }, {n ne } { n ne } для некоторого малого 0.

Точнее, n(t + 1) ne = A+ (n(t) ne ), если n ne, n ne, и n(t + 1) ne = A (n(t) ne ), если n ne, n ne, где A, A+ матрицы с неотрицательными компонентами.

Доказательство. Пусть f e, re равновесные потоки, соответствующие равновесию ne.

Рассмотрим область {n ne } { n ne }. Мы считаем, конечно, что ne N.

= maxi |xi |, и под В качестве нормы возьмем максимум модулей компонент вектора, x берем из следующих соображений. В любом случае, Ni ne. Если ne Ni Fis /wi, то i i Ni Fis /wi ne, а если ne Fid /(if vi ), то Fid /(if vi ) ne.

i i i Если fis (ne ) fi1 (ne ) + ri, то d fis (ne ) fi1 (ne ) ri d.

f wi + i1 vi f При таких, если n ne, то fis (n) fis (ne ) wi, fi1 (n) fi1 (ne ) + i1 vi1, d d поэтому по-прежнему выполнено неравенство fis (n) fi1 (n) + ri.

d Если же, напротив, fis (ne ) fi1 (n) + ri, условия на следующие. Если ri pr fis (ne ), то d i ri ne, Ni i r pi w i d тогда в рассматриваемой области выполняется равенство ri (t) = ri при ri (0) = ri. Если fi1 (ne ) pf fis (ne ), то d i pf fis (ne ) fi1 (ne ) d i, pf wi + i1 vi f i d тогда fi1 (t) = fi1 (t).

При указанных ограничениях на потоки f (t), r(t) в области {n ne } { n ne } определяются следующим образом.

1. Если fis (ne ) fi1 (ne ) + ri, то d s ne Ni Fis /wi, F i, i fis (t) fi1 (t) + ri (t) = = wi (Ni ni (t)), ne Ni F s /wi.

i i Поток fi1 (t) определяется следующим образом.

• Если ri pr fis (ne ), то i s ne Ni Fis /wi, Fi, i s fi1 (t) = fi1 (t) ri = i + r wi (Ni ni (t)), ne Ni F s /wi.

i i • Если fi1 (ne ) pf fis (ne ), то d i f d i1 vi1 ne Fi1, d Fi1, i d fi1 (t) = fi1 (t) = f f v ni1 (t), f vi1 ne F d.

i1 i i1 i1 i • Иначе s ne Ni Fis /wi, F i, i fi1 (t) = pf fi1 (t) = pf s i1 i wi (Ni ni (t)), ne Ni F s /wi.

i i 2. Если же fis (ne ) fi1 (ne ) + ri, то ri (t) = ri, d f d i1 vi1 ne Fi1, d Fi1, i d fi1 (t) = fi1 (t) = f vi1 ni1 (t), f vi1 ne F d.

i1 i i1 i Поскольку потоки f (t), r(t) зависят от n(t) линейно, то и n(t+1) зависит от n(t) линейно, поэтому n(t + 1) ne = A+ (n(t) ne ), где A = {a+ }j=1,...,K a+ = 0, если |i j| 1 (в модели ij i=1,...,K ij кольцевой магистрали элементы aK1 и a1K могут быть ненулевыми), v, fis (ne ) fi1 (ne ) + ri, f vi1 ne Fi1, f f d d i i1 i1 i + ai,i1 = 0, иначе, 1 w, f s (ne ) f d (ne ) + r, ne N F /w, i i i i i i i i 1 vi, fi+1 (ne ) fid (ne ) + ri+1 или fid (ne ) pf fi+1 (ne ), s s i + ai,i = if vi ne Fid, i (2.9) 1, иначе, wi+1 / f, fi+1 (ne ) fid (ne ) + ri+1, ri+1 pr fi+1 (ne ), s s i+ i ne Ni+1 Fi+1 /wi+1, s i+ a+ = pf wi+1 /if, fi+1 (ne ) fid (ne ) + ri+1, ri+1 pr fi+1 (ne ), s s i,i+1 i+ i fid (ne ) pf fi+1 (ne ), ne Ni+1 Fi+1 /wi+1, s s i+ i 0, иначе.

В модели кольцевой автострады aK1 и a1K определяются по формулам для ai,i+1 и ai,i1.

Область {n ne } { n ne } рассматривается аналогично. Считаем, что ne 0.

В любом случае, ni для всех i. Если if vi ne Fid, то ne Fid (if vi ). Если i i wi (Ni ne ) Fis, то ne (Ni Fis wi ).

i i Если fis (ne ) fi1 (ne ) + ri, то d fi1 (ne ) + ri fis (ne ) d.

f wi + i1 vi При этом fi1 (t) + ri (t) = fis (t). Если ri pr fis (ne ), то ne (Ni ri /(pr wi )). Если i i i fi1 (ne ) pf fis (ne ), то d i fi1 (ne ) pf fis (ne ) d i.

i1 vi1 + pf wi f i При таких ограничениях на потоки f (t), r(t) в области {n ne } { n ne } определяются по следующему правилу.

1. Если fi1 (ne ) + ri fis (ne ), то d Fis, ne Ni Fis /wi, i fis (t) fi1 (t) + ri (t) = = wi (Ni ni (t)), ne Ni F s /wi.

i i Поток fi1 (t) определяется следующим образом.

• Если ri pr fis (ne ), то i s ne Ni Fis /wi, Fi, i s ri = i + fi1 (t) = fi1 (t) r wi (Ni ni (t)), ne Ni F s /wi.

i i • Если fi1 (ne ) pf fis (ne ), то d i f d i1 vi1 ne Fi1, d Fi1, i d fi1 (t) = fi1 (t) = v ni1 (t), f vi1 ne F d.

f f i1 i i1 i1 i • Иначе Fis, ne Ni Fis /wi, i pf fi1 (t) pf s fi1 (t) = = i1 i wi (Ni ni (t)), ne Ni F s /wi.

i i 2. Если fi1 (ne ) + ri fis (ne ), ri (t) = ri, то ri (t) = ri, d d f d i1 vi1 ne Fi1, d Fi1, i fi1 (t) = vi1 ni1 (t), f vi1 ne F d, f i1 i i1 i d и при этом ri+1 (t) = ri.

Потоки f (t) и r(t) зависят от n(t) линейно, поэтому n(t + 1) ne = A (n(t) ne ). Элементы матрицы A определяются так же, как элементы матрицы A+, но в формулах (2.9) все строгие неравенства следует заменить на нестрогие и наоборот.

Положение равновесия ne устойчиво в том и только в том случае, если все элементы матриц (A± )t равномерно ограничены для всех t = 1, 2,..., и асимптотически устойчиво, если (A± )t 0 при t. Эти условия равносильны следующим. Положение равнове сия ne устойчиво, если и только если все собственные значения матриц A± по модулю не превосходят 1, а собственным значениям, равным по модулю 1, соответствует ровно столько собственных векторов, какова их кратность. Положение равновесия ne является асимптоти чески устойчивым, если все собственные значения матриц A± по модулю строго меньше 1.

Из леммы 2.3, а именно, из вида матриц A±, вытекают следующие факты, справедливые как для матрицы A+ (все знаки ± заменяются на + ), так и для матрицы A (все знаки ± заменяются на ).

Утверждение 2.12. Если a± = 0, то a± ± ± i1,i1 = 1 vi1. Если ai,i+1 = 0, то ai+1,i+1 = i,i 1 wi+1. Следовательно, если a± = 1, то a± = a± = 0.

ii i1,i i+1,i Утверждение 2.13. Для каждого i по крайней мере одна из двух величин a±, a± равна i+1,i i,i+ нулю.

2.5.3.1 Устойчивость равновесий в модели незамкнутой автострады Используя утверждения 2.12, 2.13, можно сразу же показать, что все положения равно весия в модели незамкнутой автострады являются устойчивыми, но не все асимптотически устойчивыми.

Теорема 2.4. В модели незамкнутой автострады любое положение равновесия является устойчивым.

Доказательство. Покажем, что для любого положения равновесия диагональные элементы матриц A+ и A, и только они, являются собственными значениями.

Рассмотрим, к примеру, матрицу EA+ (для матрицы A+ доказательство аналогично).

В модели незамкнутой автострады a+ = 0, j = K, j = K 1 и a+ = 0, i = K, i = Kj iK K 1. Кроме того, согласно утверждению 2.13, по крайней мере одна из величин a+ K,K1, a+ + K1,K равна нулю. Следовательно, ( aKK ) единственный ненулевой элемент матрицы (E A+ ) или в своей строке, или в своем столбце. Следовательно, det(E A+ ) = K = ( a+ )K1, где i определитель матрицы, стоящей на пересечении первых i строк и KK i столбцов матрицы (E A+ ). Как и для минора K, несложно показать, что i = ( K a+ )i1. Кроме того, очевидно, 1 = (a+ ). Поэтому det(E A+ ) = + i=1 (a11 ). Таким ii образом, диагональные элементы матрицы A+, и только они, являются ее собственными значениями.

Все диагональные элементы матрицы A+ положительны и не превосходят единицы.

Диагональным элементам, равным единице, a+ = 1, соответствуют собственные векторы ii (0,..., 0, 1, 0,..., 0), где единственный ненулевой элемент стоит в i-й позиции. Действительно, если a+ = 1, то, согласно утверждению 2.12, a+ + i1,i = ai+1,i = 0, все остальные элементы ii i-го столбца матрицы A+, кроме a+, нулевые, поскольку матрица A+ трехдиагональная.

ii Таким образом, собственному значению 1 матрицы A+ соответствует ровно столько линейно независимых собственных векторов, какова его кратность.

Это доказывает устойчивость любого положения равновесия в модели незамкнутой ав тострады.

Если же среди диагональных элементов хотя бы одной из матриц A± есть единица, то рассматриваемое положение равновесия не является асимптотически устойчивым.

Вспомним, что множество равновесий в модели незамкнутой автострады представляет собою односвязное множество. То есть, если множество равновесий содержит более одной точки, то в окрестности каждого равновесия есть другие равновесия, поэтому ни одно рав новесие не является асимптотически устойчивым. Таким образом, равновесие может быть асимптотически устойчивым, только если оно единственно. С другой стороны, собственные значения матриц A±, соответствующих единственному равновесию ne, по модулю строго меньше 1. Действительно, пусть, например, у матрицы A+ есть собственное значение 1. Как уже было показано, ему соответствует собственный вектор вида = (0,..., 0, 1, 0,..., 0).

Тогда для некоторого малого положительного вектор ne + также является равновесием.

Таким образом, справедлива следующая теорема.

Теорема 2.5. В модели незамкнутой автострады положение равновесия асимптотически устойчиво, если и только если оно единственно.

2.5.3.2 Устойчивость равновесий в модели кольцевой автострады Квадратную матрицу A назовем устойчивой, если все ее собственные значения по мо дулю не превосходят единицы, а собственным значениям, по модулю равным единице, соот ветствует ровно столько линейно независимых собственных векторов, какова кратность этих собственных значений. Квадратную матрицу A назовем асимптотически устойчивой, если все ее собственные значения по модулю строго меньше единицы.

В дальнейшем, если утверждение формулируется для матрицы A = {aij }j=1,...,K, то i=1,...,K имеется ввиду как матрица A+, так и матрица A. Для напоминания будем обозначать это так: A = A±.

Лемма 2.4. Пусть aij = 0 для некоторого i и для всех j = i, то есть aii единственный ненулевой элемент в своем столбце. Тогда диагональные элементы матрицы A = A±, и только они, являются ее собственными значениями, и матрица A является устойчивой.

При этом матрица A является асимптотически устойчивой, если все ее диагональные элементы строго меньше единицы.

Доказательство. Пусть, к примеру, aKK единственный ненулевой элемент в своем столбце (в общем случае этого можно добиться сдвигом индексов). Как в доказательстве теоремы 2.4, можно показать, что определитель матрицы E A равен произведению ее диагональных элементов, поэтому диагональные элементы матрицы A, и только они, являются собствен ными значениями этой матрицы. При этом диагональные элементы, равные 1, являются единственными ненулевыми элементами в своем столбце, и им соответствуют линейно неза висимые собственные вектора вида (0,..., 0, 1, 0,..., 0).

Следовательно, матрица A является устойчивой. Асимптотически устойчивой матри ца A является лишь в том случае, если все ее диагональные элементы строго меньше 1.

Пусть для любого i один из элементов ai1,i, ai+1,i не равен нулю. Пусть, например, aK1,K = 0. Согласно утверждению 2.13, aK,K1 = 0, значит, при i = K 1, aK2,K1 = 0.

Рассуждая таким образом, мы придем к тому, что ai1,i = 0, ai+1,i = 0 для всех i. Аналогично, если a2,1 = 0, то a1,2 = 0, потому, при i = 2, a3,2 = 0, и так далее: ai+1,i = 0, ai1,i = 0.

То есть, если в каждом столбце матрицы A по крайней мере два ненулевых элемента, то ненулевыми являются (а) либо главная диагональ, и диагональ снизу под главной, а также f f элемент a1,K, и в этом случае ai,i1 = i1 vi1, aii = 1 vi. Либо (б) не нулевые лишь главная диагональ, диагональ сверху от главной, и элемент aK,1. В этом случае ai,i+1 = wi+1 /if или ai,i+1 = pf wi+1 /if, aii = 1 wi.

i Случай (а) разобран в доказательстве утверждения 2.10. Матрица A в этом случае устойчивая. Более того, несложно показать, что матрица A асимптотически устойчивая. Это можно доказать, например, используя теорему Фробениуса Перрона.

Случай (б), фактически, разобран в доказательстве утверждения 2.11. Устойчивость матрицы A в этом случае зависит от величины K K ai,i+ (A) =.

wi i=1 i= А именно, матрица A является устойчивой, если и только если (A) 1, и асимптотически устойчивой, если (A) 1.

Таким образом, справедлива следующая теорема.

Теорема 2.6. В модели кольцевой автострады положение равновесия ne является неустой чивым, если и только если одно из чисел (A ), (A+ ) строго больше единицы. Положение равновесия ne является асимптотически устойчивым, если (A± ) 1 и все элементы главных диагоналей матриц A± строго меньше единицы.

В частности, если в положении равновесия ne хотя бы для одного i справедливо нера венство ne Ni Fis /wi, то это положение равновесия является устойчивым.

i 2.6 Примеры Примеры, как и в предыдущей главе, будут для незамкнутой и кольцевой автомаги страли с двумя основными ячейками, K = 2. Схемы таких автомагистралей приведены на рис. 1.7 на стр. 30.

Расчеты к примерам в этой и в следующей главе выполнены с помощью программы [45].

Незамкнутая автомагистраль На рис. 2.1 приведены проекции траекторий системы на пространство (n1, n2 ) плотностей в основных ячейках автомагистрали, широкими линиями и небольшими незакрашенными кругами выделены точки множества равновесия.

N N n2 n n1 n 0 (а) Строго допустимый входной поток (б) Допустимый, но не строго, входной по d d ток, f1 = f1 = F1, f2 = f2 = F N N n2 n n1 n 0 (в) Недопустимый входной поток, (г) Недопустимый входной поток, d d d d f1 f1 = F1, f2 = f2 = F2 f1 = f1 = F1, f2 = f2 F Рис. 2.1. Траектории системы и положения равновесия в модели незамкнутой автострады Все траектории начинаются на границе прямоугольника 0 ni Ni, i = 1, 2. В на чальный момент времени число автомобилей на въездах таково, что выполнены равенства d d f0 (0) = f0, ri (0) = ri, i = 1, 2.

Здесь и во всех примерах к этой главе вся внутренность прямоугольника, состоящего из равновесных точек, как, например, на рис. 2.1б, состоит лишь из равновесных точек.

Отметим, что в модели незамкнутой автомагистрали с двумя основными ячейками вы полнено равенство f2 = f2, если, конечно, в третьей ячейке нет сужения, то есть F3 F2.

d Для строго допустимого входного потока fi = fi F1, i = 1, 2, для любого допустимого потока fi = fi Fid, i = 1, 2.

В примерах на рис. 2.1 коэффициенты приоритета пропорциональны пропускным спо собностям. Посмотрим, как зависит множество равновесий и траектории системы от коэффи циентов приоритета (рис. 2.2). Рассмотрим два крайних случая: нулевые приоритеты въездов (рис. 2.2а) и нулевые приоритеты основных ячеек автомагистрали (рис. 2.2б). Входной поток d d недопустимый, f1 = F1, f2 = F2, сужений нет, F1 = F2 = F3. Если у въездов нулевые прио ритеты, pr = 0, i = 1, 2, то fi = fi, i = 1, 2, если же нулевые приоритеты у основных ячеек, i pf = pf = 0, то f1 f1, f2 = f2.

0 N N n2 n n1 n 0 (б) pf = pf = (а) pr = pr = 1 2 0 Рис. 2.2. Влияние коэффициентов приоритета на траектории системы и равновесия Кольцевая автомагистраль На рис. 2.3 представлены примеры траекторий системы и множеств положений равновесия в модели кольцевой автомагистрали с двумя ячейками. При 1 положение равновесия n = N асимптотически устойчиво, при 1 неустойчиво. При = 1 множество равновесий содержит отрезок, начинающийся в точке n = N (см. утвер ждение 2.8).

N N n2 n n1 n 0 (а) Строго допустимый входной поток, 1 (б) Недопустимый входной поток, N N n2 n n1 n 0 (в) Строго допустимый входной поток, = 1 (г) Недопустимый входной поток, = N N n2 n n1 n 0 (д) Строго допустимый входной поток, 1 (е) Недопустимый входной поток, Рис. 2.3. Траектории системы и равновесия в модели кольцевой автострады Глава Управление состоянием автомагистрали при помощи выделенных полос В этой главе представлена модель автомагистрали с выделенными полосами. Предла гается алгоритм управления коэффициентами расщепления потоков в узлах посредством изменения стоимости въезда в платные полосы, поддерживающий выделенные полосы в состоянии свободного движения, насколько это возможно при условии максимального ис пользования пропускной способности выделенных полос. При построении управления суще ственно используются результаты первых двух глав, касающиеся пропускной способности автострады и структуры множества равновесий.

3.1 Модель автомагистрали с выделенными полосами Модифицируем модель автомагистрали из § 1.2. В каждой ячейке есть l1 выделенных и l2 обычных полос. Параметры и переменные, относящиеся к выделенным полосам, обознача ются верхним индексом = 1, а относящиеся к обычным полосам верхним индексом = 2.

Схема модели автомагистрали с выделенными полосами приведена на рисунке 3. qi+ qi n1 n n i1 i+ i n2 n2 n i1 i i+ Рис. 3.1. Схема модели автомагистрали с выделенными полосами Пропускные способности Fi, вместимости Ni, коэффициенты приоритетов p, пропуск i ные способности выездов Si, и, следовательно, пропускные способности Fi,d, Fi,s, = 1, 2, пропорциональны числу выделенных и обычных полос в ячейке: Fi = Fi l /(l1 + l2 ), = 1, 2, Ni = Ni l /(l1 + l2 ), = 1, 2, и так далее.

Схема узла автомагистрали, не являющегося источником или стоком, представлена на рис. 3.2.

ri, p r d i Si fi1,s fi1, p1,f 1,d i fi1, p2,f 2,d fi2,s i Si Рис. 3.2. Схема узла в модели автомагистрали с выделенными полосами Требуемые исходящие и допустимые входящие потоки определяются как в модели ав томагистрали без выделенных полос:

d r ri (t) = min{vi qi (t), Ri }, fi,d (t) = min{if vi n (t), Fi,d }, = 1, 2, i fi,s (t) = min{wi (Ni n (t)), Fi,s }, = 1, 2.

i Водители могут выбрать выделенные или обычные полосы только в момент въезда на автомагистраль. Управление устанавливает стоимость въезда на платные полосы для каждо го въезда. Для некоторых категорий транспортных средств (например, общественный транс порт или автомобили с несколькими пассажирами) стоимость въезда на выделенные полосы может быть снижена вплоть до нуля. Выбор водителя зависит от текущего состояния вы деленных и обычных полос, от стоимости въезда на выделенные полосы, а также от цены времени для конкретного водителя. Об этом речь пойдет позже. Управление, таким образом, 1 на каждом шаге определяет коэффициенты расцепления i, i для потока со въездов. Разу 1 2 1 меется, i, i 0, i + i = 1. Стоимость въезда на платные полосы может быть ограничена как снизу (например, условие неотрицательности), так и сверху (задана максимальная сто имость въезда в платные полосы). Пусть Bi множество пар коэффициентов расщепления 1 (i, i ), соответствующих допустимым ценам въезда на выделенные полосы в узле i.

Определение потоков в узле Выясним, как вычисляются потоки со въездов и из преды дущих ячеек в текущие. Шаг по времени t не упоминается для упрощения изложения.

Нужно определить потоки со въездов в выделенные и обычные полосы ri, = 1, 2, и потоки между соседними ячейками в выделенных или обычных полосах fi1, = 1, 2.

d Если в рассматриваемом узле нет въезда или ri = 0, потоки между соседними ячейками 1 fi1 и fi1 вычисляются независимо:

fi1 = min{fi1, fi,s },,d = 1, 2, 1 потоки со въезда, если въезд есть, нулевые: ri = ri = 0.

d Если же в рассматриваемом узле въезд есть, и ri 0, то вычисляются потенциальные 1 потоки i, i : если i = 0, то i = 0, иначе i pr i = min max fi,s, fi,s fi,d d i, i ri, = 1, 2.

i pr + i1 p,f f i i 1 Потенциальный поток i это поток ri со въезда в выделенные полосы, при условии, если 2 нет ограничений со стороны обычных полос. Аналогично, i это поток ri со въезда в обычные полосы, если нет ограничений со стороны выделенных полос. Ограничения могут 1 2 1 1 2 появиться, поскольку потоки ri и ri связаны коэффициентами расщепления: ri /i = ri /i.

Определим величины 1, i = 0, = = 1, 2, i /( rd ), 0, ii i i и i = min{1, 2 }. Ясно, что 1, поэтому i 1.

i i i Наконец, потоки ri и fi1 вычисляются по формуле d fi1 = min{fi1, fi,s ri },,d ri = i i ri, = 1, 2.

3.2 Построение управления Будем строить управление для модели незамкнутой автомагистрали. Предполагаем, что нулевой ячейки нет, а в первую ячейку автомобили попадают только со въезда перед первой ячейкой. Цель управления, как уже упоминалось, состоит в том, чтобы привести выделенные полосы в состояние свободного движения и поддерживать их в этом состоянии, насколько это возможно при условии максимального использования пропускной способности выделенных полос.

На шаге t известно текущее состояние системы, то есть векторы n(t) и r(t), но нет информации о будущем, то есть, о входных потоках di (t + t), t = 0, 1, 2,....

3.2.1 Оценивание множества допустимых коэффициентов расщепления Зная ограничения на цену въезда в платные полосы, можно оценить множество допусти мых коэффициентов расцепления Bi, оценивая распределение стоимости времени в очередях перед въездами и ожидаемое время в пути по платным и бесплатным полосам. Под сто имостью времени конкретного водителя мы понимаем ту сумму, которую водитель готов заплатить за уменьшение времени поездки на единицу времени.

Распределение стоимости времени во входном потоке можно оценивать статистически, путем опросов и на основании исторических данных, то есть по реальным решениям води телей. Это сделано, например, в работах [46–48] на основе моделей дискретного выбора [49].

Вполне вероятно, что распределения стоимости времени различны для разных въездов и зависят от дня недели и времени суток.

Пусть для каждого въезда известна функция распределения цены времени Pi (p), то есть для любого p определена доля участников движения в очереди перед i-м въездом Pi (p), цена времени которых не превышает p. Ясно, что Pi (0) = 0, функция Pi (·) не убывает, и Pi (p) при p.

Пусть ij (t) доля водителей в очереди перед въездом в i-ю ячейку на шаге t, которые покинут автомагистраль на съезде в конце j-й ячейки, j i. Если этой информации о j1 K f f s k, если j k, и i,K+1 = маршрутах нет, положим ij = j k. Пусть стоимость k=i k=i времени водителей не зависит от маршрутов.

Скорость движения в ячейке i платных ( = 1) или бесплатных ( = 2) полос в момент времени t есть скорость свободного движения vi, если n (t) = 0, и vi (t) = fi,out (t)/n (t) = i i = fi (t)/(if n (t)), если n (t) 0. Здесь fi,out (t) суммарный исходящий поток для ячейки i i i платных или бесплатных полос на шаге t. Время в пути от начала i-й ячейки до выезда из j-й ячейки при текущих условиях по платным ( = 1) или бесплатным ( = 2) полосам есть j Tij (t) = k=i (vi (t)). Пусть на въезде i в момент времени t установлена стоимость въезда в платные полосы pi (t) 0. Тогда водители, въезжающие на автомагистраль с i-го въезда и выезжающие на j-м выезде, выберут платные полосы, если их цена времени не меньше 2 pi (t)/(Tij (t) Tij (t)). Доля таких водителей в очереди перед въездом определяется функцией 2 2 распределения стоимости времени, а именно, ij (t) = Pi (pI (t)/(Tij (t) Tij (t))) доля во 1 дителей, выбирающих бесплатные полосы, ij (t) = 1 ij доля водителей, выбирающих платные полосы, среди всех водителей, въезжающих на автомагистраль через i-й въезд и 2 планирующих выехать на j-м съезде. Ясно, что, если Tij (t) Tij (t), то все водители выберут 1 бесплатные полосы, то есть ij (t) = 0, ij (t) = 1. Коэффициенты расщепления для потока с K+ i-го въезда, таким образом, определяются по формуле i (t) = j=i ij ij (t).

Оценивание зависимости коэффициентов расщепления от стоимости въезда в платные полосы, однако, может быть неточным. С другой стороны, можно не оценивать стоимость времени и время в пути для каждого маршрута, а подбирать стоимость въезда в платные по лосы динамически, ориентируясь на желаемые и реальные потоки. Такой подход развивается в работе [33].

3.2.2 Условие максимального использования пропускной способности платных полос Управлять состоянием автомагистрали, с платными полосами или без них, имеет смысл лишь в том случае, когда входной поток d не является строго допустимым, то есть доста точно велик. Действительно, если входной поток строго допустимый, то состояние системы сходится к единственному положению равновесия nu, а в этом положении равновесия ав томагистраль не загружена, то есть скорость движения максимальна. Если же входящий поток не является допустимым, то неизбежно возникнут заторы в основных ячейках авто магистрали или на въездах. Пропускную способность платных полос важно использовать полностью, иначе будут расти заторы на въездах и, таким образом, даже водители, готовые заплатить за въезд в платные полосы, будут вынуждены ожидать в очереди перед въездом на автомагистраль.

Для максимального использования пропускной способности платных полос можно пред ложить по крайней мере два условия: условие минимизации скорости роста очереди перед въездами или условие максимизации суммарного входящего потока для основных ячеек ав тострады. Разберем оба условия.

3.2.2.1 Минимизация скорости роста очереди 1 Определим множество пар коэффициентов расщепления (i (t), i (t)) Bi (t), миними зирующих скорость роста длины очереди перед i-м въездом на шаге t, или, что эквивалентно, 1 максимизирующих i (t, i (t), i (t)). Напомним, что Bi (t) множество наборов коэффициен тов расщепления, соответствующих допустимым ценам. Будем считать, что множество Bi (t) не пусто и замкнуто.

Шаг по времени t упоминаться некоторое время не будет для упрощения изложения.

1 1 1 1 1 2 1 1 2 Обозначим Bi = {i : (i, 1 i ) Bi }. Ясно, что B = {(i, i ) : i Bi, i = 1 i }.

Обозначим = max i (i, 1 i ), 1 i 1 i Bi A1 = Arg max i (i, 1 i ).

1 i 1 Bi i определить множество A1.

Наша цель i Несложно видеть, что (i ), = 1, монотонно невозрастающие функции, непре i рывные на полуинтервале (0, 1] и полунепрерывные сверху в точке i = 1. Действительно, для i (0, 1] f,s f,d fi,s pr (i ) = min max, i d i i,1.

i ri i pr + p,f d i ri i i При этом (i ) 0 при i (0, 1], если pr = 0 и fi,s fi1.

,d i i Обозначим i = max{i [0, 1] : (i ) = 1}.

i Ясно, что i = min{1, max{0, a }}, где i,s,d fi fi pr = 0,, i d ri ai =,s,d,f,s max fi fi1, fi pi1, pr 0.

i pr d d ri ri i Рассмотрим следующие случаи.

1. i + i 1. В этом случае 1 (i ) = 2 (i ) = 1 и, следовательно, i (i, i ) = 1 для 1 2 1 2 1 i i 2 1 2 i = 1 i, i [1 i, i ] (рис. 3.3).

= 2 (1 i ) i = 1 (i ) i 0 2 1 1 i i i 1 Рис. 3.3. Максимизация i при i + i Если Bi [1 i, i ] =, то = 1, A1 = Bi1 [1 i, i ].

2 1 2 i i В противном случае справедливо по крайней мере одно из условий Bi [0, 1 i ] =, Bi [ i, 1] =. Если Bi [0, 1 i ] =, определим a1 = max(Bi [0, 1 i ]). Если 1 2 i Bi [ i, 1] =, определим a1 = min(Bi [ i, 1]).

1 i Если определены обе величины a1, a1, то = max{i (a1, 1 a1 ), i (a1, 1 a1 )}, A1 = i i i i i i i i = {i B : i (i, 1 i ) = } {a1, a1 }.

1 1 i i i Если же определена лишь одна из величин a1, a1, то она является единственным эле i i ментом множества A1, а есть значение функции (i, 1 i ) в точке i = a1 или 1 1 i i i i = a1 соответственно.

i 1 2 1 2 1 2 1 2. i + i 1. В этом случае i (i, i ) 1 для всех i, i 0, i + i = 1, поэтому 1, то есть, поток с i-го въезда будет ограничен в любом случае.

i (a) Если pr = 0 и fi,s fi1, = 1, 2, то i = i = 0 и (i, 1 i ) = 0 для всех i.

,d 1 2 1 1 i Значит, = 0, A1 = Bi.

i i (b) Пусть выполнено по крайней мере одно из неравенств pr 0, fi,s fi1, = 1, 2.

,d i i. Если i = 0 и 1 (1) lim2 +0 2 (2 ) (рис. 3.4), то A1 = max Bi, = 2 ( 2 i i i i i max Bi ).

= 1 (i ) i = 2 (1 i ) i 0 1 i Рис. 3.4. Максимизация i при i = 0, 1 (1) lim2 +0 2 (2 ) 2 i i ii. Если i = 0 и 2 (1) lim1 +0 1 (1 ) (рис. 3.5), то A1 = min Bi, = 1 i i i i = 1 (min Bi ).

i = 2 (1 i ) i = 1 (i ) i 0 1 i Рис. 3.5. Максимизация i при i = 0, 2 (1) lim1 +0 1 (1 ) 1 i i iii. В противном случае выполнены неравенства 1 (1 i ) 2 2 (2 ), 2 (1 i ) 1 1 (1 ).

lim lim i i i i 2 2 +0 1 1 + i i 1 1 1 2 Рассмотрим функцию (i ) = i (i ) i (1 i ). Поскольку каждая из функ ций (i ), = 1, 2, строго убывает и непрерывна при i (0, 1], то функ i 1 ция (i ) также строго убывает и непрерывна при i (0, 1). Кроме то 1 го, lim1 1 +0 (i ) 0, lim1 12 0 (i ) 0. Следовательно, уравнение i i i i 1, 1, 1 (i ) = 2 (1 i ) имеет единственное решение i, причем i ( i, 1 i ) 1 1 i i (рис. 3.6).

= 1 (i ) = 2 (1 i ) i i 0 1 1, 2 1 i i i i Рис. 3.6. Максимизация i при 1 (1 i ) lim2 2 +0 2 (2 ), 2 (1 i ) lim1 1 +0 1 (1 ) 2 i i i i i i 1, 1, 1, 1, Если i Bi, то = 1 (i ) = 2 (1 i ), A1 = {i }. Иначе по крайней i i i i 1, 1, 1, 1 1 мере одно из множеств Bi [0, i ], Bi [i, 1] не пусто. Если Bi [0, i ] = 1, 1, =, определяем a1 = max(Bi [0, i ]). Если Bi [i, 1] =, определяем 1 i 1, a1 = min(Bi [i, 1]). Далее величина и множество A1 определяются как i i i в пункте 1.

Пусть множество Bi является отрезком. Тогда множество A1 также является отрезком, i или содержит только одну точку. Если множество A1 является отрезком, то значения потоков i с i-го въезда в выделенные полосы ri, соответствующие элементам i из множества A1, 1 i ri = ri (i ) = i ri, 1 1 1 1d i 1,min 1,max 1,min 1,max = ri (min A1 ), ri = ri (max A1 ).

образуют отрезок [ri, ri ], где ri i i 3.2.2.2 Максимизация суммарного входящего потока Шаг по времени t не упоминается. Суммарный входящий поток для основных ячеек автомагистрали в узле i есть i = ri + ri + fi1 + fi1 = min{ri + fi1, fi1,s } + min{ri + fi1, fi2,s }.

1,d 2,d 1 2 1 2 1 Требуется определить число и множество A1 :

i = max i (i ), 1 i Bi A1 = Arg max i (i ).

i 1 Bi i Нам понадобится следующее утверждение.

Утверждение 3.1. Поток ri является монотонно неубывающей функцией коэффициента расщепления i, = 1, 2, непрерывной на полуинтервале [0, 1). В точке i = 1 функция ri (i ) полунепрерывна сверху.

Доказательство. Докажем утверждение для = 1. Для = 2 утверждение доказывается аналогично.

Как было показано, ri = i i ri, i = min{1, 2 }. Поскольку функции монотонно не 1 1d i i i 1, 2 возрастают по i и i = 1 i, отрезок [0, 1] можно разбить на две части точкой i, такой, 1, 1, что 2 (1 i ) 1 (i ) при i [0, i ] и 2 (1 i ) 1 (i ) при i (i, 1].

1 1 1 1 1 i i i i 1, Поскольку 2 (1 i ) является неубывающей функцией, то на отрезке [0, i ] функция i 1, ri (i ) = 2 (1 i )i ri также не убывает. На полуинтервале (i, 1] выполнено равенство 1 1 1 1d i 1 1 1 1 1 ri (i ) = i (i ), а функция i (i ) также является неубывающей.

Непрерывность на интервале (0, 1) и полунепрерывность сверху в точке i = 1 вытекает из аналогичных свойств функции i (i ), а непрерывность в нуле следует из вида функции d 1 ri (i ) и ограниченности функции i (i ).

Если выполнены оба неравенства fi1,s fi1 и fi2,s fi1 или равенство ri = 0, то 1,d 2,d d i = = min{fi1, fi1,s } + min{fi1, fi2,s } вне зависимости от значений коэффициентов рас 1,d 2,d i щепления i, i, то есть A1 = Bi.

1 2 i Если pr = 0 и fi1,s fi1, но fi2,s fi1, то при 0 Bi A1 = {0}, = fi1,s +min{fi2,s, fi1 + 1,d 2,d 2,d i i i + ri };

иначе A1 = Bi, = fi1,s + fi1. Аналогично, если pr = 0 и fi2,s fi1, но fi1,s fi1, то 2,d 2,d 1,d d i i при 1 Bi A1 = {1}, = min{fi1,s, fi1 + ri } + fi2,s ;

иначе A1 = Bi, = fi1 + fi2,s.

1,d 1,d 1 d i i i Пусть ri 0, и выполнено по крайней мере одно из неравенств fi1,s fi1, fi2,s fi1, а 1,d 2,d d если pr = 0, то выполнены оба эти неравенства.

i Случай max{0, fi1,s fi1 }+max{0, fi2,s fi1 } ri 1,d 2,d d В этом случае максимум суммар ного входящего потока есть fi1,s + fi2,s и достигается при ri max{0, fi,s fi1 }, = 1, 2.

,d Обозначим 1 = min{i : ri (i ) max{0, fi1,s fi1 }}, 1,d 1 1 i 1 = 1 max{i : ri (i ) max{0, fi2,s fi1 }}.

2,d 2 2 i Покажем, что 1 1.

i i 1, Утверждение 3.2. Справедливо неравенство 1 i 1, где i i max{0, fi1,s fi1 } 1,d 1, i =.

max{0, fi1,s fi1 } + max{0, fi2,s fi1 } 1,d 2,d Доказательство. Действительно, если i (i ) = 1, то ri = i ri max{0, fi1,s fi1 }, 1, 1, d 1,d ri = (1 i )ri max{0, fi2,s fi1 }, следовательно, (i ) = fi1,s + fi2,s. Пусть i (i ) 1.

1, s 2,d 1, 1, Если i (i ) = 1 (i ), то i 0, ri + fi1 = fi1,s, 1, 1, 1, 1 i 1, 1, 1 i 1,d 1 i max{0, fi1,s fi1 } max{0, fi2,s fi1 }, 2,d 2 ri = ri 1, 1, i i следовательно, ri +fi1 = fi2,s. Аналогично, если i (i ) = 2 (1i ), то также справедливы 1, 1, 2 i равенства ri + fi1 = fi2,s, ri + fi2 = fi1,s.

2 2 1 1, 1, Следовательно, 1 i и 1 i.

i i Если Bi [1, 1 ] =, то A1 = Bi [1, 1 ], = fi1,s + fi2,s.

1 i i i i i i Утверждение 3.3. Если pr 0 или выполнены неравенства fi,s fi1, = 1, 2, то функция,d i i (i ) является строго возрастающей при i [0, 1 ) и строго убывающей при i (1, 1].

1 1 i i Доказательство. Докажем, что функция i (i ) является строго возрастающей на полуин тервале [0, 1 ). Строгое убывание на полуинтервале (1, 1] доказывается аналогично.

i i При i 1 справедливы неравенства ri (i ) fi1,s fi1, ri (1i ) max{0, fi2,s fi1 }, 1,d 2,d 1 1 1 2 i значит, i = 2, i i (i ) = fi1 + ri (i ) + fi2,s = fi1 + 2 (1 i )i ri + fi2,s.

1,d 1,d 1 1 1 1 1d i Функция 2 (1 i ) является монотонно неубывающей и ненулевой при указанных условиях, i значит, функция ri (i ) = 2 (1 i )i ri, а также функция i (i ) являются строго возраста 1 1 1 1d i ющими на полуинтервале (0, 1 ].

i Из только что доказанного утверждения следует, что если Bi [1, 1 ] =, то максими i i затор функции (i ) на множестве Bi следует искать среди величин a1 = max(Bi [0, 1 ]), 1 1 i i a1 = min(Bi [1, 1]). По крайней мере одна из величин a1, a1 определена.

i i i i Случай max{0, fi1,s fi1 } + max{0, fi2,s fi1 } ri 0 В этом случае максимум 1,d 2,d d суммарного входящего потока есть min{fi1, fi1,s } + min{fi1, fi2,s } + ri и достигается при 1,d 2,d d 1 2 d 1 1 ri +ri = ri, то есть при i = 1. Как было показано в п. 3.2.2.1, множество {i : i (i, 1i ) = = 1} либо пусто, либо является отрезком или точкой. В нашем случае это множество является 2 отрезком, поскольку оно включает в себя отрезок [1 i, i ], где max{0, fi,s fi1 },d i = min 1,, = 1, 2, d ri 2 и 1 i i. Обозначим 1 = max{i : 1 (i ) = 1}, 1 i i 1 = 1 max{i : 2 (i ) = 1}.


2 i i Мы уже, фактически, доказали, что 1 1 i i 1.

2 i i Если Bi [1, 1 ] =, то A1 = Bi [1, 1 ], = min{fi1, fi1,s } + min{fi1, fi2,s } + ri.

1,d 2,d 1 1 d i i i i i i Несложно доказать утверждение, формулировка которого в точности совпадает с фор мулировкой утверждения 3.3, но для других значений 1, 1. Из этого утверждения бу i i дет следовать, что, как и в предыдущем случае, если Bi [1, 1 ] =, то максимиза i i тор функции (i ) на множестве Bi следует искать среди величин a1 = max(Bi [0, 1 ]), 1 1 i i a1 = min(Bi [1, 1]), по крайней мере одна из которых определена.

i i 3.2.3 Координация управления на въездах Прежде чем строить управление, вычислим некоторые вспомогательные величины. Во первых, найдем максимальный контролируемый уровень концентраций (см. § 1.3.1) для вы 1, деленных полос, точнее, соответствующие ему потоки f 1, : fK+1 = FK+1, fi1, = min{Fi1,d, fi+1 /i+1 }, 1, f i = K,..., 1.

Пусть i1 i2 · · · iM индексы участков со въездами. Обозначим iM +1 = K + 2. Опре делим максимальные равновесные потоки для выделенных полос f 1,e следующим образом:

fi1,e = fi1,, fi1,e = if fi1, i = im + 1,..., im+1 1. Несложно видеть, что f 1,e f 1,. Вектор 1,e m m концентраций n1,e, соответствующий вектору потоков f 1,e и состоянию свободного движения, определяется так: n1,e = fi1,e /(if vi ), i = 1,..., K + 1. Обозначим i im+1 n1,e.

1,e N (im, im+1 ) = i i=im На каждом шаге вычисляем число автомобилей между соседними въездами im+1 n1 (t), n (t, im, im+1 ) = i i=im 1,min 1,max диапазон потоков со въездов для выделенных полос [rim (t), rim (t)];

оцениваем исходящие потоки s1 (t), i = 1,..., K, и потоки fi1 (t), m = 1,..., M, при r1 (t) = r1,min (t).

i m Модифицируем диапазон потоков со въездов r1 (t) следующим образом.

1. Чтобы не перераспределять потоки со въездов в состоянии свободного движения, если 1 2 1 1 i (t) + i (t) 1 и i (t) l1 /(l1 + l2 ), положим i (t) = max{1 i (t), l1 /(l1 + l2 )} и 1,max пересчитаем ri (t).

2. Если fi1,d1 (t) + rim (t) min{fi1,s (t), fi1,e /ifm }, уменьшаем rim (t):

1,max 1,max m m m rim (t) = max{rim (t), min{fi1,s (t), fi1,e /ifm } fi1,d1 (t)}.

1,max 1,min m m m Потоки со въездов rim (t) определяются согласно следующему алгоритму.

1. n = 0, m = M, M = 1.

Величина n обозначает текущий суммарный избыток плотности, то есть числа авто мобилей;

n обновляется на каждом шаге.

2. Вычислить n1 (t, im, im+1 ;

m ) = n1 (t, im, im+1 ) m N 1,e (im, im+1 ) и обновить n:

im+1 n n + n (t, im, im+1 ;

m ) + fi1 1 (t) fi1 1 (t) s1 (t).

i m m+ i=im 3. Определить rim (t):

1,min 1,max rim (t) = max{rim (t), min{rim (t), n}} 4. Если m = 1, стоп.

5. Обновить n:

n max{0, n + rim (t)}.

6. Вычислить m1 :

m1 = min{1, (fi1,s (t) rim (t))/fi1,e1 }.

m m 7. Уменьшить m на единицу и перейти к шагу 2.

То, что ограничения на суммарное число автомобилей между въездами и ограничения на суммарный входящий поток для участка между соседними въездами достаточно для при ведения каждой ячейки в состояние свободного движения и удержания в нем, будет доказано позже.

1 2 Коэффициенты расщепления i (t), i (t) восстанавливаются по потоку со въезда ri (t) довольно просто.

• Если ri (t) = 0 или (t) = 0, то ri (t) = ri (t) = ri (t) независимо от коэффициентов d 1 i 1 расщепления i (t), i (t).

• Иначе i (t) = ri (t)/ri (t), i (t) = 1 i (t), где ri (t) = (t)ri (t).

1 1 2 1 d i Замечание. Можно изменить модель узла, разрешив перестроение из обычных полос в вы деленные, также за плату. Условие максимального использования пропускной способности в виде максимизации суммарного входящего потока для основных ячеек автомагистрали ограничивает множество цен въезда в выделенные полосы автомагистрали, Далее, коор динируя при необходимости управление в узлах, как это описано выше, для каждого узла выбирается цена. Целью при этом является ограничение суммарного числа автомобилей между соседними контролиуемыми узлами не выше заданного уровня и ограничение сум марного входящего потока для платных полос.

3.3 Обоснование алгоритма управления Покажем, что если выделенные полосы автомагистрали в некоторый момент t находятся в состоянии свободного движения, причем n1 (t) n1,e, то это неравенство будет сохранено предложенным алгоритмом управления, если не возникнет существенных ограничений со стороны обычных полос и если входные потоки di будут не слишком большими.

Поскольку везде речь идет только о выделенных полосах, и состояние бесплатных полос не учитывается, верхний индекс 1 упоминаться не будет. По сути, приведенные ниже теоремы справедливы также для модели автострады без выделенных полос.

Теорема 3.1. Пусть n(t) ne и для всех ячеек со въездами im, m = 1,..., M, выполнено неравенство rim (t) fiem /ifm fid 1 (t). Тогда n(t + 1) ne.

m Доказательство. Покажем, что для ячеек со въездом im неравенство rim (t) fiem /ifm fid 1 (t) возможно, то есть fiem /ifm fid 1 (t) 0. Для первой ячейки это неравенство, m m очевидно, выполнено, поскольку f0 (t) 0. Поскольку n(t) ne, то fid (t) fie для всех i.

d С учетом равенства fiem = fi и неравенства f e f, получаем m fiem /ifm fid 1 (t) fiem /ifm fiem 1 fi /ifm fi 1 0.

m m m Далее, в условиях теоремы fi (t) = fid (t) = if vi ni (t) для всех i, для всех ячеек со въез дом im выполнены неравенства fim 1 (t) + rim (t) fiem /ifm, а для ячеек i без въезда ri (t) = и выполнено неравенство fi1 (t) fi1 fie /if. Поэтому e ni (t + 1) = ni (t) fi (t)/if + fi1 (t) + ri (t) ni (t)(1 vi ) + fie /if ne (1 vi ) + fie /if = ne.

i i Если же в начальный момент времени неравенство n(t) ne не выполнено, можно доказать теорему 3.2.

Равновесным назовем поток f между ячейками, такой, что f F d, f0 = 0 и существует вектор потоков со въездов r, такой, что ri = 0, если в ячейке i нет въезда, и ri 0, если на участке i есть въезд, и fi1 + ri = fie /if, i = 1,..., K + 1.

e Теорема 3.2. Пусть f e равновесный поток, но не обязательно максимальный равновес ный поток, определенный в § 3.2.3. Пусть на каждом шаге t выполнены неравенства im+1 1 im+1 ne ni (t) i i=im i=im для каждой пары соседних въездов (im, im+1 ), и fim 1 (t) + rim (t) fiem /ifm, fism (t) fiem для каждой ячейки со въездом im.

Тогда для любого 0 найдется момент времени T = T (), начиная с которого будут выполняться неравенства ni (T + t) ne + для всех i и для всех t = 0, 1, 2,..., где i ne = fie /(if vi ).

i Доказательство. Преобразуем модель так, чтобы в ячейках не было съездов. Для этого пропускную способность Fis, максимальное число автомобилей Ni, входной поток di, про пускную способность въезда Ri число автомобилей в основных ячейках автомагистрали ni (t) i1 f и на въездах qi (t) умножим на поправочный коэффициент µi = j=1 (j ), а пропускную способность для исходящего потока Fid умножим на µi+1. Для измененной системы (величи ны, к ней относящиеся, будем обозначать символом ) d d d fi1 (t) = min{vi1 ni1 (t), Fi1 } = µi fi1 (t), fis (t) = min{wi (Ni ni (t)), Fis } = µi fis (t), d r d ri (t) = min{vi qi (t), Ri } = µi ri (t), следовательно, fi1 (t) = µi fi1 (t), ri (t) = µi ri (t), поэтому ni (t + 1) = µi ni (t + 1), qi (t + 1) = = µi qi (t + 1), то есть, исходная система эквивалентна преобразованной. Компоненты рав новесного потока fie также умножаются на µi+1. Неравенства fim 1 (t) + rim (t) fiem /ifm, fism (t) fiem 1 из условий теоремы переходят в неравенства fim 1 (t) + rim (t) fiem, fism (t) im+1 1 im+1 1 im+1 µ1 ni (t) fiem 1, а неравенство ne переходит в неравенство ni (t) i i i=im i=im i=im im+1 1 µi ne. Поэтому теорему можно доказывать для автомагистрали без съездов, но для i i=im im+1 1 im+1 ne на неравенство ni (t) этого нужно заменить неравенство i i=im i=im im+1 1 im+1 i ne, i ni (t) i i=im i=im i1 f где 1 2 · · · K+1 0, а точнее, i = µ1 = j.

i j= Итак, будем считать, что на автомагистрали нет съездов, то есть if = 1 для всех i. При этом неравенство Fid if Fis по-прежнему может выполняться строго. Если на автомаги страли нет съездов, то для равновесного потока fiem = fiem +1 =... = fiem+1 1.

Рассмотрим участок между соседними въездами, im и im+1. Рассмотрим кластеры яче ек, в которых плотность превышает ne. Несложно показать, что один кластер не может i распадаться на два или более, и правая граница кластера может передвигаться лишь вправо (вправо означает в направлении увеличения индексов ячеек ). Кроме того, кластеры могут исчезать, но не могут появляться (а появляться они могли бы лишь в ячейке со въездом, то есть слева), поскольку fim 1 (t) + rim (t) fiem, по условию теоремы.

Будем исследовать поведение системы после того момента, когда число кластеров и их правые границы перестанут меняться. Если между соседними въездами im, im+1 не останется кластеров, то, очевидно, hm (t) = 0 и теорема доказана. Пусть i правая граница первого m (слева) кластера. Применяя лемму 1.1 о монотонности, считая ячейку i въездом к ячей m ке i + 1, можно показать, что lim inf t ni (t) ne при i i. Действительно, даже если в m i m начальный момент ni (0) = 0 при i i im+1, и fi (t) fie, то ni (1) 0 = ni (0), следо m m m вательно, ni (t + 1) ni (t) для всех t и для всех i i im+1, поэтому последовательность m векторов (ni +1 (t),..., nim+1 1 (t)) сходится к минимальному равновесию, соответствующему m входному потоку fie, то есть к (ne +1,..., nem+1 1 ).


im i m Обозначим im+1 max{0, ni (t) ne }.

hm (t) = i i=im Нужно доказать, что hm (t) 0 при t. Несложно видеть, что величина hm (t) неотри цательна и не возрастает при увеличении t. Действительно, ячейки, в которых ni (t) ne, i составляют кластеры, входящий поток для каждого кластера не превышает fiem, а исходящий поток не меньше этой величины. Следовательно, у последовательности чисел {hm (t)} су t= ществует неотрицательный предел. Пусть limt hm (t) = 0. Будем рассматривать систе му с того момента, когда ni (t) ne (im+1 im )1 im+1 i /2 для всех i = i +1,..., im+1 1.

i m Поскольку мы предполагаем, что hm (t), то im i (ni (t) ne ) = 0 i i=im i (ni (t) ne ) + i (ni (t) ne ) + i (ni (t) ne ) = i i i ii, ii, ni (t)ne m m i ni (t)ne ni (t)ne i i (ni (t) ne ) + im+1.

im i ii, m ni (t)ne i Таким образом, на каждом шаге t выполнено неравенство im+ (ne ni (t)). (3.1) i 2im ii, m ni (t)ne i Покажем, что первый слева кластер перестанет существовать через конечное время. Дей ствительно, не реже, чем каждые (i im ) шагов число автомобилей в кластере уменьшится m не менее чем на im+ ifm... if 1 = 0.

2im (i im ) m m Это связано с неравенством (3.1), из которого следует, что на каждом шаге t среди ячеек im,..., i 1 по крайней мере в одной ni (t) ne im+1 /(2im (i im )), поэтому не больше, m i m чем через (i im ) шагов входящий поток для кластера будем снижен не менее чем на.

m Следовательно, через hm (t)(i im )/ шагов первый кластер существовать уже не будет.

m Но это противоречит нашему предположению об установившемся числе кластеров и об уста новившихся правых границах кластеров. Поэтому hm (t) 0 при t, что доказывает теорему.

Замечание. В условиях теоремы 3.2 неравенство im+1 1 im+1 ne ni (t) i i=im i=im можно заменить на условие im+1 1 im+1 ne.

ni (t) lim sup i t+ i=im i=im На шаге 3 алгоритма управления делается попытка выполнить оба неравенства из усло im+1 1 im+1 ne и fim 1 (t) + rim (t) fiem /ifm. Если сделать ni (t + 1) вий теоремы 3.2, i i=im i=im это невозможно, на шаге 6 уменьшается равновесный поток для ячеек выше по течению, что при не слишком больших входных потоках вверх по течению может со временем привести к снижению входящего потока fim 1 для ячейки im.

3.4 Примеры Приведем примеры работы алгоритма управления с условием минимизации скорости роста очереди для автомагистрали с одним и с двумя въездами. Отметим, что для первого въезда условие минимизации скорости роста очереди всегда эквивалентно условию макси мизации суммарного входящего потока для основных ячеек автомагистрали.

Автомагистраль с одним въездом Схема автомагистрали с одним въездом, в самом начале автомагистрали, приведена на рис. 3.7.

n n n1 n1 K+ K 1 q ··· n2 n2 n2 n K K+ 1 Рис. 3.7. Схема автомагистрали с одним въездом Автомагистраль имеет одну платную и одну бесплатную полосу. Параметры всех ячеек, такие как пропускная способность Fi, скорость свободного движения vi и скорость роста затора wi, максимальное число автомобилей в ячейках Ni, одинаковы для всех ячеек, кро ме последней. Пропускная способность последней ячейки меньше пропускной способности остальных ячеек:

F1 = F2 = · · · = FK FK+1, = 1, 2, то есть в конце автомагистраль сужается. Все параметры платной и бесплатной полосы одинаковые: Fi1 = Fi2, Ni1 = Ni2 для всех i.

Первый сценарий: разгрузка платной полосы. Входной поток d0 постоянный и равен 1 суммарной пропускной способности последней ячейки: d0 = FK+1 + FK+1. В начальный мо мент платные и бесплатные полосы находятся в равновесии, соответствующем потокам со въездов r0 = FK+1, которые являются допустимыми, но не строго допустимыми. Часть ячеек в начале автомагистрали находятся в состоянии свободного движения (n (0) = n,u, i i ), i i остальные ячейки загружены (n (0) = n,c, i i ).

i i На рис. 3.8 показано изменение состояния системы под действием управления, перерас пределяющего входной поток, чтобы разгрузить платные полосы.

По оси абсцисс время в минутах, по оси ординат номер ячейки. Цветом обозначена плотность, то есть число автомобилей в ячейках: чем темнее цвет, тем больше плотность. На графике сверху состояние платной полосы, снизу бесплатной. Если в начальный момент автомагистраль заполнена больше, чем наполовину, то есть i K/2, то полная разгрузка платных полос невозможна (рис. 3.8а). Если же в начальный момент автомагистраль запол нена меньше, чем наполовину, то есть i K/2, то через конечное число шагов платные полосы будут полностью разгружены, некоторые ячейки в начале бесплатных полос могут остаться незагруженными (рис. 3.8б).

Второй сценарий: временно недопустимый входной поток. В начальный момент входной 1 поток допустимый, но не строго допустимый: d(0) = FK+1 + FK+1. С 5 до 30 минут входной 1 2 1 поток недопустимый: FK+1 + FK+1 d(t) F1 + F1, а затем снова допустимый, но не строго.

В начальном положении автомагистраль не загружена: n (0) = n,u, = 1, 2 для всех i. Когда i i входной поток становится недопустимым, начинают загружаться бесплатные полосы, а если 1 входной поток очень большой, d(t) FK+1 +F1, то и платные полосы начинают загружаться, как это и происходит на рис. 3.9. Когда входной поток становится снова допустимым, но не строго, платные полосы начинают разгружаться, а бесплатные загружаются по-прежнему, но только до тех пор, пока платные полосы не разгрузятся полностью.

(а) В начальный момент автомагистраль загружена больше, чем наполовину (б) В начальный момент автомагистраль загружена меньше, чем наполовину Рис. 3.8. Разгрузка платной полосы автомагистрали с одним въездом Рис. 3.9. Временно недопустимый входной поток Автомагистраль с двумя въездами Схема автомагистрали с двумя въездами, в начале и в середине автомагистрали, изображена на рис. 3.10.

qi n n n1 n i1 K+ i q ··· ··· n2 n2 n2 n i1 i K+ Рис. 3.10. Схема автомагистрали с двумя въездами Сценарий: разгрузка платной полосы. Входной поток допустимый, но не строго допусти мый, в начальный момент система находится в состоянии равновесия, часть ячеек в начале автомагистрали свободны, остальные загружены. На рис. 3.11 показано изменение состо яния платной и бесплатной полосы. Несмотря на то, что между первым и вторым въездом, находящимся ровно в середине автомагистрали, все ячейки свободны, поток с первого въезда также перераспределяется, что ускоряет разгрузку платной полосы.

Рис. 3.11. Разгрузка платной полосы автомагистрали с двумя въездами Заключение В работе получены следующие основные результаты.

1. Предложены понятия пропускной способности и уровня загруженности автострады для дискретной модели кольцевой и незамкнутой автострады. Получен способ вычисления пропускной способности кольцевой и незамкнутой автострады.

2. Описано множество положений равновесия в моделях незамкнутой и кольцевой ав тострады. Доказано, что в модели незамкнутой автострады все равновесия являются устойчивыми. Получен критерий устойчивости равновесий в модели кольцевой авто страды.

3. Предложен алгоритм управления состоянием незамкнутой автострады с помощью вы деленных платных полос. Цель управления поддерживать выделенные полосы в со стоянии свободного движения, при условии максимального использования их пропуск ной способности.

По-видимому, способ вычисления пропускной способности и структуру множества рав новесий незамкнутой автомагистрали можно обобщить на любую транспортную сеть без циклов. Исследование положений равновесия в модели кольцевой автомагистрали показы вает, что свойства транспортной сети существенно меняются при появлении в ней циклов.

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

Что касается алгоритмов управления состоянием автострады как при помощи платных полос, так и другими способами (например, ограничивая потоки со въездов), следует раз работать систему оценки и сравнения эффективности алгоритмов управления в реальных условиях. Например, обработав данные о работе алгоритма, скажем, в течение дня, мож но построить оптимальное управление для этого дня и сравнить результат с показателями оцениваемого алгоритма управления.

Автор благодарит своего научного руководителя академика Александра Борисовича Кур жанского за постановку задачи и постоянное внимание к работе, Александра Александро вича Куржанского (PhD) за плодотворные обсуждения, доцента А. В. Гасникова за ценные замечания и В. Д. Ширяева за помощь в вычитке диссертации.

Работа выполнена при финансовой поддержке РФФИ (гранты 12-01-00261-а и 13-01 90419-Укр_ф_а) и программы Государственная поддержка ведущих научных школ (грант НШ-2239.2012.1).

Список литературы 1. Gazis D. C., Herman R., Potts R. B. Car-Following Theory of Steady-State Trac Flow // Operations Research. — 1959. — Vol. 7, issue 4. — Pp. 499–505.

2. Newell G. F. Nonlinear eects in the dynamics of car following // Operations Research. — 1961. — Vol. 9, no. 2. — Pp. 209–229.

3. Gazis D. C., Herman R., Rothery R. W. Nonlinear Follow-the-Leader Models of Trac Flow // Operations Research. — 1961. — Vol. 9, issue 4. — Pp. 545–567.

4. Treiber M., Hennecke A., Helbing D. Congested trac states in empirical observations and microscopic simulations // Physical Review E. — 2000. — Vol. 62, issue 2. — Pp. 1805–1824.

5. Nagel K., Schreckenberg M. A cellular automaton model for freeway trac // Journal de Physique I. — 1992. — Vol. 2, no. 12. — Pp. 2221–2229.

6. Математическое моделирование движения автотранспортных потоков методами меха ники сплошной среды. Двухполосный транспортный поток: модель Т-образного пере крестка, исследование влияния перестроений транспортных средств на пропускную спо собность участка магистрали / Н. Н. Смирнов [и др.] // Труды Московского физико технического института. 2010. Т. 2, № 4. С. 141 151.

7. Piccoli B., Garavello M. Trac Flow on Networks. — American Institute of Mathematical Sciences, 2006. — (AIMS Series on Applied Mathematics).

8. Введение в математическое моделирование транспортных потоков / А. В. Гасников [и др.] ;

под ред. А. В. Гасникова. М.: Изд-во МЦНМО, 2013.

9. Beckmann M., McGuire C. B., Winsten C. B. Studies in the economics of transportation. — Yale University Press, 1956.

10. Nesterov Y., de Palma A. Stationary dynamic solutions in congested transportation net works: summary and perspectives // Networks and Spatial Economics. — 2003. — Vol. 3, no. 3. — Pp. 371–395.

11. Ortzar J. de Dios, Willumsen L. G. Modelling Transport. — John Wiley & Sons, 2011.

u 12. Automatic Calibration of the Fundamental Diagram and Empirical Observations on Capac ity / G. Dervisoglu [et al.] // 8th Annual Transportation Research Board Meeting. — 2009.

13. Куржанский А. А., Куржанский А. Б., Варайя П. Роль макромоделирования в ак тивном управлении транспортной сетью // Труды Московского физико-технического института. 2010. Т. 2, № 4. С. 100 118.

14. Lighthill M. J., Whitham G. B. On Kinematic Waves. I. Flood Movement in Long Rivers // Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. — 1955. — Vol. 229, no. 1178. — Pp. 281–316.

15. Lighthill M. J., Whitham G. B. On Kinematic Waves. II. A Theory of Trac Flow on Long Crowded Roads // Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. — 1955. — Vol. 229, no. 1178. — Pp. 317–345.

16. Richards P. I. Shock waves on the highway // Operations Research. — 1956. — Vol. 4, no. 1. — Pp. 42–51.

17. Greenshields B. D. A study of trac capacity // Proceedings of the Fourteenth Annual Meeting of the Highway Research Board. Vol. 14. — 1935. — Pp. 448–477. — (Highway Research Board Proceedings).

18. LeVeque R. J. Numerical Methods for Conservation Laws. — Birkhuser, 1992.

a 19. Гельфанд И. М. Некоторые задачи теории квазилинейных уравнений // Успехи мате матических наук. 1959. Т. XIV, 2 (86). С. 87 158.

20. Олейник О. А. О единственности и устойчивости обобщенного решения задачи Коши для квазилинейного уравнения // Успехи математических наук. 1959. Т. XIV, (86). С. 165 170.

21. Lax P. D. Hyperbolic Systems of Conservation Laws and the Mathematical Theory of Shock Waves. — Society for Industrial and Applied Mathematics, 1973.

22. Годунов С. К. Разностный метод численного расчета разрывных решений уравнений гидродинамики // Математический сборник. 1959. Т. 47(89), № 3. С. 271 306.

23. Курант Р., Фридрихс К., Леви Г. О разностных уравнениях математической физики // Успехи математических наук. 1941. № 8. С. 125 160.

24. Daganzo C. F. The cell transmission model: a dynamic representation of highway trac con sistent with the hydrodynamic theory // Transportation Research Part B: Methodological. — 1994. — Vol. 28, no. 4. — Pp. 269–287.

25. Daganzo C. F. The cell transmission model, part II: Network trac // Transportation Re search Part B: Methodological. — 1995. — Vol. 29, no. 2. — Pp. 79–93.

26. Aurora Road Network Modeler. — URL: http://code.google.com/p/aurorarnm/.

27. Jin W. L., Zhang H. M. On the distribution schemes for determining ows through a merge // Transportation Research Part B: Methodological. — 2003. — No. 6. — Pp. 521–540.

28. Ni D., Leonard J. D. A simplied kinematic wave model at a merge bottleneck // Applied Mathematical Modelling. — 2005. — Vol. 29, no. 11. — Pp. 1054–1072.

29. A generic class of rst order node models for dynamic macroscopic simulation of trac ows / C. M. Tamp`re [et al.] // Transportation Research Part B: Methodological. — 2011. — Vol.

e 45, no. 1. — Pp. 289–309.

30. Arnott R., Small K. The Economics Of Trac Congestion // American Scientist. — 1994. — Vol. 82, no. 5. — Pp. 446–455.

31. de Palma A., Lindsey R. Trac congestion pricing methodologies and technologies // Trans portation Research Part C: Emerging Technologies. — 2011. — Vol. 19, no. 6. — Pp. 1377– 1399.

32. Hearn D. W., Ramana M. V. Solving congestion toll pricing models // Equilibrium and Advanced Transportation Modeling / ed. by P. Marcotte, S. Nguyen. — 1998. — Pp. 109– 124.

33. State-dependent pricing for real-time freeway management: Anticipatory versus reactive strategies / J. Dong [et al.] // Transportation Research Part C: Emerging Technologies. — 2011. — Vol. 19. — Pp. 644–657.

34. Varaiya P. Congestion, ramp metering and tolls // Philosophical transactions of the royal society A. — 2008. — Vol. 366. — Pp. 1921–1930.

35. Kurzhanskiy A. A. Modeling and Software Tools for Freeway Operational Planning: Ph.D. the sis / Kurzhanskiy Alex A. — EECS Department, University of California, Berkeley, 2007.

36. Behavior of the cell transmission model and eectiveness of ramp metering / G. Gomes [et al.] // Transportation Research Part C: Emerging Technologies. — 2008. — Vol. 16, no. 4. — Pp. 485–513.

37. Kurzhanskiy A. A., Varaiya P. Active trac management on road networks: a macroscopic approach // Philosophical Transactions of The Royal Society, Part A. — 2010. — Vol. 368. — Pp. 4607–4626.

38. Gomes G., Horowitz R. Optimal freeway ramp metering using the asymmetric cell transmis sion model // Transportation Research Part C: Emerging Technologies. — 2006. — Vol. 14, no. 4. — Pp. 244–262.

39. Zhang L., Levinson D. Optimal freeway ramp control without origin–destination informa tion // Transportation Research Part B: Methodological. — 2004. — Vol. 38, no. 10. — Pp. 869–887.

40. Muralidharan A., Horowitz R. Imputation of Ramp Flow Data for Freeway Trac Simula tion // Transportation Research Record. — 2009. — Vol. 2099. — Pp. 58–64.

41. Дорогуш Е. Г. Вычисление пропускной способности и уровня загруженности кольце вой автомагистрали // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2013. № 3. С. 16 24.

42. Дорогуш Е. Г. Математичское моделирование транспортных потоков на кольцевой ав тостраде // Сборник статей молодых ученых факультета ВМК МГУ. 2011. Вып.

8. С. 54 68.

43. Дорогуш Е. Г. Динамическая модель транспортных потоков на кольцевой автостраде // Доклады Академии Наук. 2013. Т. 453, № 4. С. 363 367.

44. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1966.

45. Gomes G. BeATS: Berkeley’s Advanced Trac Simulator. — URL: https://github.com/ calpath/beats.

46. Small K. A., Winston C., Yan J. Dierentiated Road Pricing, Express Lanes, and Carpools:

Exploiting Heterogeneous Preferences in Policy Design // Brookings-Wharton Papers on Urban Aairs. — 2006. — Pp. 53–96.

47. Brownstone D., Small K. A. Valuing time and reliability: assessing the evidence from road pricing demonstrations // Transportation Research Part A: Policy and Practice. — 2005. — Vol. 39. — Pp. 279–293.

48. Patil S., Burris M., Shaw W. D. Travel using managed lanes: An application of a stated choice model for Houston, Texas // Transport Policy. — 2011. — Vol. 18, no. 4. — Pp. 595– 603.

49. Train K. Discrete Choice Methods with Simulation. — Cambridge University Press, 2009.

Список иллюстраций 1 Фундаментальная диаграмма в непрерывной модели транспортных потоков. 1.1 Схема узла транспортной сети............................ 1.2 Схема простого узла.................................. 1.3 Схема узла-разветвления............................... 1.4 Схема узла-слияния.................................. 1.5 Схема модели автомагистрали............................ 1.6 Схема узла в модели автомагистрали........................ 1.7 Схемы автомагистралей с двумя основными ячейками.............. 1.8 Карты уровней загруженности кольцевой и обычной автомагистрали..... 2.1 Траектории системы и положения равновесия в модели незамкнутой автострады 2.2 Влияние коэффициентов приоритета на траектории системы и равновесия.. 2.3 Траектории системы и равновесия в модели кольцевой автострады....... 3.1 Схема модели автомагистрали с выделенными полосами............. 3.2 Схема узла в модели автомагистрали с выделенными полосами......... 1 Максимизация i при i + i 1..........................

3.3 Максимизация i при i = 0, 1 (1) lim2 +0 2 (2 )...............

3.4 i i Максимизация i при i = 0, 2 (1) lim1 +0 1 (1 )...............

3.5 i i Максимизация i при 1 (1 i ) lim2 2 +0 2 (2 ), 2 (1 i ) lim1 1 +0 1 (1 ) 2 3.6 i i i i i i 3.7 Схема автомагистрали с одним въездом...................... 3.8 Разгрузка платной полосы автомагистрали с одним въездом.......... 3.9 Временно недопустимый входной поток....................... 3.10 Схема автомагистрали с двумя въездами...................... 3.11 Разгрузка платной полосы автомагистрали с двумя въездами..........

Pages:     | 1 ||
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.