Гасников А.В., Кленов С.Л., Нурминский Е.А., Холодов Я.А., Шамрай Н.Б. Введение в математическое моделирование транспортных потоков

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

В самом деле, из свойств пуассоновского точечного поля следу-

ет, что условное распределение остаточного времени жизни препят-

ствия при условии, что полное время жизни равно t, совпадает с

равномерным распределением на отрезке [0, t]. В силу леммы 2 ве-

роятность возникновения препятствия в интервале длины dx равна

λm

dx + o(dx), а вероятность возникновения препятствия с фикси-

рованным временем жизни t в интервале длины d x есть λtdQ(t)dx +

+o(dx), что вытекает из леммы 1. Поскольку

λtdQ(t)dx + o(dx)

λm

dx + o(dx)

tdQ(t)

есть условная вероятность возникновения препятствия с фиксиро-

ванным времени жизни t, то плотность распределения остаточного

времени жизни препятствия имеет вид

∞

tdQ(t)

= m

−1

(1 − Q(s))ds = h(s)ds.

Лемма доказана.

В том случае, когда объезд возможен, автомобиль потеряет вре-

мя, которое есть минимум из времени обгона и остаточного времени

жизни препятствия, т.е. α

= min(η, ζ). Теорема доказана.

Обсудим результат. Смысл константы a мы уже пояснили, а кон-

станта b имеет смысл стационарной плотности препятствий в про-

странстве.

Этот результат довольно точен при малой плотности автомоби-

лей, так как около препятствий будет по одному автомобилю. При

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

ся (увеличиваться) в зависимости от средней длины очереди перед

препятствием.

3.3. Снижение средней скорости из-за медленных

автомобилей

Автотрасса описывается действительной осью R. Потоки считают-

ся не очень плотными, поэтому длина автомобиля роли не играет,

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

кой x

(t) ∈ R, где i — индекс, нумерующий автомобили. Каждый

268

автомобиль имеет фиксированный маршрут: место и время въезда

i,in

, t

i,in

, а также предписанное ему место выезда x

i,out

. Но время

выезда t

i,out

зависит от степени загруженности дороги. Мы опреде-

ляем среднюю скорость автомобиля i как

i,out

− x

i,in

i,out

− t

i,in

Есть два типа автомобилей: быстрые и медленные, каждый движет-

ся с постоянной скоростью слева направо. У быстрых автомобилей

скорость v

, у медленных – v

, где v

> v

> 0. Пусть v = v

− v

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

левой скорости v

. Медленные автомобили движутся до пункта на-

значения нигде не останавливаясь, а быстрые до тех пор, пока не

догонят впереди идущий медленный автомобиль. После этого б ыст-

рый автомобиль i движется вместе с этим медлен ным автомобилем j

некоторое случайное время τ

i,j

и затем обгоняет его, сразу набирая

скорость v

. Основное предположение состоит в том, что эти случай-

ные величины независимы и одинаково распределены с функцией

распределения F (s).

Эта функция распределения может быть н айдена статистически

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

ния обгона), так и по статистике препятствий к обгону — плотности

встречного потока.

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

соновским точечным полем Π интенсивности λ, которое было опре-

делено в предыдущем разделе. Нам потребуются также новые обо-

значения. С каждым медленным автомобилем мы свяжем случайное

расстояние, которое ему необходимо проехать. Буд ем предполагать,

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

расстояние ρ

, после чего он съедет с дороги. С.в. ρ

независимы

и одинаково распределены с общей функцией распределения G(r).

С.в. ρ

не зависят также от пуассоновского точечного поля Π. Будем

предполагать существование первых двух моментов с.в. ρ

. Обозна-

чим m

= Eρ

, m

(2)

= Eρ

Медленный автомобиль не встречает на своем пути препятстви й

и проходит свой путь со скоростью v

. Быстрым автомобилям могут

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

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

ленным до тех пор пока медленный автомобиль не доедет до нужного

269

места, после чего быстрый автомобиль мгновенно набирает свою ско-

рость v

. Во втором случае обгон разрешен. Более точно, когд а i-й

быстрый автомобиль догоняет j-й медленный или группу быстрых

автомобилей (следующих за j-м медленным), ему требуется случай-

ное время τ

i,j

для того, чтобы обогнать j-й медленный автомобиль

или всю эту группу автомобилей. При этом время обгона не зависит

от размера группы. С.в. τ

i,j

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

ково распределенными с функцией распределения F (u).

Пусть d = λm



−1

− v

−1



. Введем с.в. β с плотностью распре-

деления g(x) = m

−1

(1 −G(x)) и с.в. γ = min(v

1,1

, β), где равенство

по распределению и с.в. τ

1,1

, β считаются независимыми. Отметим,

что

Eβ =

(2)

Положим c = Eγ.

Теорема 2. С вероятностью 1 при x → ∞

T (x)

→ ¯v

1 + dc

1 + dcv

−1

. (6)

Доказательство. Покажем, что этот случай сводится к рассмот-

ренному случаю v

= 0. Введем систему координат, которая движет-

ся со скоростью v

относительно исходной. Найдем среднюю ско-

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

по формуле (4), подставляя v = v

− v

, b =

λm

, a =

− v

)

−1

λmc

− v

1 + dcv

−1

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

системы координат составит

¯v

− v

1 + dcv

−1

+ v

1 + dc

1 + dcv

−1

4. Критерии образования пробок

в сложных транспортных сетях

Обязательным атрибутом транспортной сети (например, городских

улиц) является граф, где множество V вершин представляет пере-

270

крестки (узлы или пункты обслуживания), а множество ребер L =

= {(i, j)} — отрезки путей без перекрестков. Пусть число перекрест-

ков равно N. Мы предполагаем, что между двумя перекрестками

существует не более одного пути без перекрестков.

Наиболее разработанными являются два класса сетей. С одной

стороны, это (по имени авторов и в порядке увеличения общности)

сети Джексона, BCMP-сети, DB-сети (см., например, [8, 26]). В них

требование (сообщение, автомобиль, работа) обслуживается в каж-

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

узел. С другой стороны, — сети Келли (см. [8]), где каждое требо-

вание имеет заранее фиксированный маршрут. Эти два класса сетей

связаны как общей техникой, так и близостью результатов. Имен-

но они обладают замечательным свойством мультипликативности

— стационарные распределения в них имеют вид так называемой,

продакт-формы. Мы рассматриваем только первый класс сетей.

4.1. Замкнутые сети

Если предполагается, что автомобили не прибывают извне и не убы-

вают вовне, то такая сеть называется замкнутой. Таким образом,

число автомобилей в сети сохраняется и далее обозначается через

M. Движение отдельного автомобиля определяется так. Автомобиль

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

рекресток j. Выбор j определяется стохастической матрицей марш-

рутизации: P = {p

}

i,j=1,...,N

, где p

— вероятность того, что с пе-

рекрестка i автомобиль поедет (после ожидания) на перекресток j

(например, прямо, налево, направо), то есть по улице (i, j).

Стохастическая матрица P определяет конечную цепь Маркова

с дискретным временем, множеством состояний V = {1, ..., N}. Эта

цепь Маркова предполагается неразложимой. В этом случае система

линейных уравнений

ρP = ρ, ρ = (ρ

, ..., ρ

) ⇐⇒

i=1

= ρ

, j = 1, ..., N (7)

имеет единственное решение (с точностью до п роизвольного множи-

теля). Нормированное решение имеет вид

i=1

, i = 1, ..., N.

271

С каждым узлом i ∈ V свяжем функцию µ

) от числа автомоби-

лей n

в i-м узле, где µ

(0) = 0 и µ

) > 0 при n

> 0. Эта функция

характеризует пропускную способность данного узла и определяет

интенсивность выходящего из узла потока автомобилей. Именно ве-

роятность того, что за малый промежуток времени dt из узла i вы-

едет автомобиль, равна µ

)dt + o(dt) при условии, что в узле на-

ходится n

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

будем называть µ

) интенсивностью обслуживания в узле i.

Порядок, в котором пропускаются (обслуживаются) прибываю-

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

Простейший вариант дисциплины обслуживания – это обслужива-

ние в порядке поступления. В узле прибывающие автомобили стано-

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

хали, и узел пропускает автомобили согласно этой очереди. Если в

узле i находится n

автомобилей, то первый автомобиль в очереди

обслуживается с интенсивностью µ

Более общая дисциплина обслуживания – это дисциплина раз-

деления общего ресурса, где под ресурсом в данном случае пони-

мается пропускная способность узла. Согласно этой дисциплине ре-

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

находящимися в данный момент в узле. В общем случае предполо-

жим, что k-й автомобиль в i-м узле обслуживается с интенсивностью

i,k

) ≤ µ

). При этом потребуем, чтобы

k=1

i,k

) = µ

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

между всеми автомобилями в очереди:

i,k

) =

)

В этом случае каждый из n

автомобилей потратит экспоненциаль-

ное время со средним n

−1

) на прохождение этого узла, при усло-

вии, что число автомобилей будет сохраняться равным n

. Если взять

i,1

) = µ

), то получим дисциплину обслуживания в поряд-

ке поступления. Таким образом, интенсивности µ

i,k

) полностью

определяют дисциплину обслуживания в узлах.

Динамика сети описывается с помощью N-мерной марковской

цепи с непрерывным временем ξ(t) = (ξ

(t), i = 1, ..., N), где ξ

(t)

272

— число автомобилей, скопившихся в i-м узле в момент времени t.

Случайный процесс ξ(t) принимает значение в пространстве S

, где

– множество всех таких векторов с неотрицательными целочис-

ленными координатами ¯n = (n

, ..., n

), что n

+ ... + n

= M.

Пусть e

– базисный вектор, в котором i-я координата равна 1,

а остальные координаты равны 0. Из состояния ¯n марковская цепь

ξ(t) может перейти в одно из состояний T

i,j

¯n = ¯n − e

+ e

, i 6= j, с

интенсивностью

α(¯n, T

i,j

¯n) = µ

i,j

, (8)

при условии, что n

6= 0. Переход ¯n → T

i,j

¯n соответствует тому, что,

выехав из узла i, автомобиль поступает в узел j.

Отметим, что марковская цепь ξ(t) однозначно определяется мат-

рицей маршрутизации P и набором интенсивностей обслуживания в

узлах (µ

), i = 1, ..., N).

Пусть ρ = (ρ

, ..., ρ

) – решение уравнения (7), которое рассмат-

ривается как формальное уравнение для интенсивностей ρ

входя-

щих потоков в узлы (в стационарном режиме они равны выходя-

щим). Решая эти уравнения, находим ρ

, и тогда стационарное рас-

пределение ν(n

, ..., n

) марковской цепи ξ(t) будет иметь вид

ν(n

, ..., n

) =

N,M

i=1

(1)µ

(2)...µ

)

, (9)

где нормирующий множитель (малая статсумма)

N,M

+...+n

i=1

(1)µ

(2)...µ

)

что проверяется подстановкой ответа (9) в уравнения Колмогорова

для стационарных вероятностей, см., например, [8, 29].

4.2. Открытые сети

Рассмотрим сеть, состоящую из N узлов. В отличие от замкнутой

сети, общее число автомобилей в сети теперь не фиксировано. Пред-

положим, что извне сети в узел i поступает пуассоновский поток

автомобилей интенсивности λ

, i ∈ {1, ..., N}.

273

Зададим м атрицу маршрутизации P = {p

}

i,j=1,...,N

, где матри-

ца P неразложима и

∀i :

j=1

≤ 1, ∃i

j=1

< 1. (10)

Как и в случае замкнутой сети, p

i,j

— это вероятность того, что из

узла i автомобиль едет в узел j. В отличие от замкнутой сети, добав-

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

сеть. Эта вероятность по определению равна

= 1 −

j=1

Как и в случае замкнутой сети, пусть µ

) — интенсивность об-

служивания в i-м узле. Тогда с интенсивностью µ

i,0

автомобиль

покидает сеть после выхода из узла i.

Мы будем описывать динамику сети с помощью N-мерного слу-

чайного процесса с непрерывным временем η(t) = (η

(t), i = 1, ..., N ),

где η

(t) – число автомобилей в i-м узле в момент времени t. Случай-

ный процесс η(t) является марковской цепью с непрерывным време-

нем и с пространством состояний S, где S – множество N -мерных

векторов с неотрицательными целочисленными координатами ¯n =

, ..., n

Из состояния ¯n марковская цепь ξ(t) может перейти в одно из

состояний T

i,j

¯n = ¯n − e

+ e

, T

i,0

¯n = ¯n − e

, T

¯n = ¯n + e

с интенсив-

ностями

α(¯n, T

i,j

¯n) = µ

i,j

α(¯n, T

i,0

¯n) = µ

i,0

, (11)

α(¯n, T

¯n) = λ

при условии, что T

i,j

¯n, T

i,0

¯n, T

¯n ∈ S.

Таким образом, марковская цепь η(t ) однозначно определяется

триплетом (λ, µ, P ), где λ = (λ

, ..., λ

) – вектор интенсивностей

внешних потоков, µ = (µ

), i = 1, ..., N ) – набор интенсивностей

обслуживания в узлах и P – матрица маршрутизации.

274

Рассмотрим формальное уравнение для интенсивностей входя-

щих потоков в узлы (в стационарном режиме они равны выходя-

щим):

ρ = λ + ρP ⇐⇒ ρ

= λ

k=1

, ∀i. (12)

В силу условия (10) и неразложимости матрицы P это уравнение

имеет единственное решение, которое можно представить в виде

ρ = λ +

∞

n=1

λP

Далее рассмотрим случай, когда интенсивности обслуживания

) ≡ µ

не зависят от числа автомобилей в узлах. Введем на-

грузки в узлах по формуле

, i = 1, ..., N.

Следующую теорему можно найти, например, в [8, 20], она назы-

вается иногда теоремой Гордона—Ньюэлла.

Теорема 3. Марковская цепь η(t) является эргодической тогда и

только тогда, когда для всех i = 1, ..., N будет r

< 1. При этом

стационарное распределение цепи имеет вид

σ(n

, ..., n

) =

i=1

(1 − r

Из этой теоремы легко следует, что средние длины очередей в

стационарном режиме равны

1 − r

Если в некоторых узлах i

, ..., i

нагрузка строго больше 1, то

марковская цепь η(t) является транзиентной (см., например, [33]).

Это свидетельствует о том, что средние очереди в узлах i

, ..., i

стремятся к бесконечности с течением времени. Подробный анализ

открытых сетей дан в работе [19]. В частности показано, что в уз-

лах, где нагрузка больше 1, средние очереди увеличиваются линейно

с ростом времени. При этом найдены скорости роста средних очере-

дей.

275

4.3. Алгоритм вычисления критической нагрузки

в замкнутых сетях

Этот раздел основан на работе [18]. Мы рассмотрим последователь-

ность замкнутых сетей J

, N = 1, 2, ... Сеть J

состоит из N узлов и

M = M(N) автомобилей. Интенсивности обслуживания в узлах сети

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

i,N

) ≡ µ

i,N

. Пусть P

= {p

i,j,N

}

– матрица маршрутизации в N -й сети; P

предполагается неразло-

жимой.

Пусть ρ

= ( ρ

1,N

, ..., ρ

N,N

) – вектор с положительными компо-

нентами, удовлетворяющий уравнению

= ρ

. (13)

Относительные нагрузки в узлах определяются как

i,N

= C

−1

i,N

где τ

i,N

= µ

−1

i,N

и C

= max

i=1,...,N

i,N

. О чевидно, что

i,N

∈ [0, 1].

В соответствии с (9) стационарное распределение числа автомо-

билей ξ

i,N,M

в узлах сети J

равно

N,M

(ξ

i,N,M

= n

, i = 1, ..., N) =

N,M

i=1

i,N

где нормирующий множитель (малая статсумма)

N,M

+...+n

i=1

i,N

. (14)

Многие важные характеристики сети выражаются через статсумму.

Упражнение 3. Показать, что среднее число автомобилей в i-м

узле в стационарном режиме равно

i,N,M

= Eξ

i,N,M

i,N

N,M

∂Z

N,M

∂r

i,N

. (15)

276

Ниже мы будем требовать слабую сходимость относительных на-

грузок r

i,N

. Точнее, определим выборочную меру на отрезке [0, 1]:

(A) =

i:r

i,N

∈A

где A – произвольное борелевское множество из отрезка [0, 1]. Пред-

положим, что при N → ∞ меры I

слабо сходятся к некоторой

вероятностной мере I заданной на отрезке [0, 1].

Нас будет интересовать случай больших N, M, точнее N, M → ∞,

причем так, что

→ λ = const, то есть удельное число автомобилей

на один узел постоянно. Именно это число определяет существование

пробок.

Замечание 1. Интересно найти конкретные последовательности

растущих графов, для которых предельная мера I явно описывает-

ся. Некоторые примеры, где мера I одноточечна см. в ссылках к

работе [18], см. также с. 157–160 в [29].

В терминах предельной меры I мы найдем критическое значе-

ние плотности λ

, так что при λ < λ

средние длины очередей

равномерно ограничены. Если λ ≥ λ

, то в узле с максимальной

относительной нагрузкой средняя длина очереди стремится к беско-

нечности, что означает возникновение пробки.

Положим

h(z) =

1 − zr

dI(r),

где z ∈ C \ [1, +∞). Функция h(z) строго возрастает на [0, 1). Обо-

значим

= lim

z→1−

h(z).

Будем предполагать, что λ

> 0.

Теорема 4. • Если λ < λ

, то средние очереди равномерно огра-

ничены: существует такая константа B, что m

i,N

< B, ра в-

номерно по N ≥ 1 и 1 ≤ i ≤ N.

• Если λ ≥ λ

и i( N ) удовлетворяет условию r

i(N),N

= 1, то

i(N),N

→ ∞, при N → ∞ т.е. пробки будут в тех узлах, где

нагрузка максимальна.

277