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

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

При z ∈ C \ [1, +∞) положим

(z) = −λ(1 + ε

) ln z −

i=1

ln(1 − zr

i,N

), (16)

S(z) = −λ ln z −

ln(1 − zr ) dI(r),

где λ(1 + ε

) =

Введем производящую функцию (большую статсумму):

(z) =

∞

M=0

N,M

i=1

1 − zr

, |z| < 1.

По формуле Коши и формуле (16) имеем следующее выражение для

статсуммы (14):

N,M

2πi

(z)

M+1

dz =

2πi

exp(NS

(z))

dz, (17)

где γ = {z ∈ C : |z| = σ < 1}. Для средних, согласно (15), имеем

i,N

2πiZ

i,N

1 − zr

i,N

exp(NS

(z)) dz. (18)

Можно показать, что для стационарного распределения длин очере-

дей справедлива формула

N,M

(ξ

1,N,M

= n

, ..., ξ

K,N,M

= n

) =

2π iZ

−1

i=1

(1 − zr

i,N

)(zr

i,N

)

exp(NS

(z))dz.

(19)

В доказательстве теорем этого раздела существенную роль игра-

ет метод перевала (см. [27]), точнее его обобщение, поскольку функ-

ция в показателе экспоненты зависит от N . Из уравнения

∂S

(z)

∂z

= 0 (20)

находятся точки перевала. Пусть z

0,N

– корень этого уравнения, ле-

жащий в интервале (0, 1).

278

Упражнение 4. Показать, что все корни уравнения (20) действи-

тельны и положительны. Всегда существует единственный ко-

рень, лежащий в интервале (0, 1).

Пусть z

– корень уравнения

h(z) =

⇔

∂S(z)

∂z

= 0, (21)

лежащий в интервале (0, 1).

Упражнение 5. • Доказать, что при всех λ существует пре-

дел lim

N→∞

0,N

= z

(λ) > 0.

• Если λ < λ

, то z

(λ) – корень уравнения (21); z

(λ) строго

возрастает по λ, z

(λ) ∈ (0, 1), lim

λ→λ

cr−

(λ) = 1.

• Если λ ≥ λ

, то z

= 1.

В следующей теореме мы находим асимптотику статсуммы и пре-

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

Теорема 5. Пусть λ < λ

• При N → ∞ статсумма Z

и свободная энергия F

ln Z

имеют следующие асимптотики:

∼

exp(NS

0,N

))

2πNS

′′

)

, F

ln Z

∼ S(z

• Если при i = 1, ..., K существуют пределы r

= lim

N→∞

i,N

то

lim

N→∞

i,N

1 − z

lim

N→∞

N,M

(ξ

1,N,M

= n

, ..., ξ

K,N,M

= n

) =

i=1

(1 −z

)(z

)

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

щую из независимых очередей.

279

Доказательство теорем 4 и 5. Мы приведем более общий ре-

зультат, из которого будут следовать теоремы 4 и 5. Пусть U

(v) =

= {z ∈ C : |z − v| < d}. Рассмотрим контур γ = {z ∈ C : |z| = z

(λ)}.

Теорема 6. Пусть λ < λ

и f (θ, z), θ ∈ Θ, – семейство функ-

ций голоморфных в кольце {z ∈ C : z

(λ) − δ

< |z| < z

(λ) + δ

}

при некотором δ

> 0, равномерно ограниченных в этом кольце и

таких, что для заданного достаточно малого ǫ > 0 существует

такое δ

> 0 и такая ненулевая действительная константа f

что |f(θ, z)/f

− 1| < ǫ при z ∈ U

2δ

), θ ∈ Θ.

Тогда при достаточно больших N, равномерно по θ ∈ Θ

2πi

f(θ, z) exp( N S

(z))dz =

exp(NS

0,N

))

2πNS

′′

)

(1 + ζ

где |ζ

| < 25ǫ.

Доказательство этой теоремы основано на применении метода пе -

ревала (saddle-point method)(см. [27]). Отличие от стандартной ситу-

ации состоит в том, что функция в показателе экспоненты зависит от

N. Подробное доказательство можно найти в оригинальной статье

[18].

Доказательство теоремы 5. Используя теорему 6, докажем пер-

вый пункт теоремы 5. Согласно (17) имеем

N,M

2πi

exp(NS

(z))

dz,

где γ = {z ∈ C : |z| = z

(λ)}. Положив f (θ, z) = z

−1

, f

= z

−1

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

ǫ > 0 при достаточно больших N

exp(NS

0,N

))

2πNS

′′

)

(1 + ζ

), |ζ

| < 25ǫ. (22)

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

нием формулы (18) для средней очереди и формулы (19) для сов-

местного распределения длин очередей.

Упражнение 6. Доказать третье утверждение теоремы 5, ис-

пользуя теорему 6 и формулы (18), (19).

280

Доказательство теоремы 4. Чтобы доказать первый пункт тео-

ремы 4, рассмотрим семейство функций

f(θ, z) =

1 − zθ

, θ ∈ Θ = [0, 1], A > 0, f

Зафиксируем малое ǫ > 0 и выберем σ

, A =

16z

(1−z

)ǫ

. По теореме

6 имеем для достаточно больших N и всех θ ∈ Θ

2π i



1−zθ



exp(NS

(z)) dz =

A exp(NS

0,N

))

√

2π N S

′′

)

(1 + ζ

), |ζ

| < 25ǫ.

Разделив на Z

и применив (22) к правой части получившегося ра-

венства, получим при достаточно больших N

A +

2πi

1 − zθ

exp(NS

(z)) dz = A (1 + ζ

′

), |ζ

′

| < 30ǫ.

Из последнего равенства и формулы (18) сле дует равномерная огра-

ниченность m

i,N

Докажем второе утверждение теоремы 4. Для этого потребует-

ся следующее свойство монотонности: при любых M

≥ M

> 0 и

любом N ≥ 1 выполнено m

i,M

≥ m

i,M

Поскольку z

(λ) строго возрастает по λ, z

(λ) ∈ (0, 1) и

lim

λ→λ

−

(λ) = 1,

то функция

(λ)

1 − z

(λ)

монотонно возрастает и стремится к ∞, когда λ ր λ

. Поэтому для

любого m > 0 существует такое λ

′

= λ

′

(m) < λ

, что

(λ

′

)

1 − z

(λ

′

)

= m + 1.

Без ограничения общности можно считать, что i(N ) ≡ 1 и r

1,N

= 1. Если взять M

′

(N) = [λ

′

N], то по теореме 5

lim

N→∞

1,M

′

(N),N

(λ

′

)

1 − z

(λ

′

)

281

Следовательно, при достаточно больших N

1,M

′

(N),N

(λ

′

)

1 − z

(λ

′

)

− 1 = m.

Но M/N → λ ≥ λ

> λ

′

, поэтому при достаточно больших N имеем

M(N ) ≥ M

′

(N). По свойству монотонности m

1,N

= m

1,M(N ),N

≥

≥ m

1,M

′

> m для достаточно больших N . Это доказывает, что

1,N

→ ∞.

Технические обобщения и математические проблемы. Мы

предполагали мгновенное перемещение между перекрестками. При

этом не учитываются времена д вижения по улицам. Это допущение

однако легко устраняется усложнением графа. Именно введением до-

полнительных вершин u

, соответствующих улицам, и средних вре-

мен τ

=µ

−1

пребывания на улицах. В терминах теории очередей это

значит, что улицы рассматриваются как узлы обслуживания с бес-

конечным числом обслуживающих устройств и врем я обслуживания

экспоненциально распределено со средним τ

=µ

−1

Отметим, что результаты раздела 4.1 могут быть обобщены на

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

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

типа (i = 0) и µ

0,N

(n) = nν

– интенсивность обслуживания в этом

узле. Пусть ρ

= (ρ

0,N

, ..., ρ

N,N

) – решение уравнения (13). Тогда

относительные нагрузки определим по формуле

i,N

0,N

i,N

так что r

0,N

= 1. Согласно (9), стационарное распределение длин

очередей имеет вид

N,M

(ξ

i,N,M

= n

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

N,M

(M −

i=1

i,N

где

N,M

+...+n

≤M

(M −

i=1

i,N

и большая статсумма сети равна

(z) = e

i=1

1 − zr

i,N

282

Положим

i,N

, w = zp

, p

= max

1≤i≤N

i,N

Тогда

(w) = e

w/p

i=1

1 − wq

i,N

В предположении, что p

N → α > 0 при N → ∞ мы може м найти

критическое значение плотности λ по формуле

= α

−1

+ lim

w→1−

1 − wq

dI(q),

где, как и раньше, мера I есть слабый предел при N → ∞ выбороч-

ных мер

(A) =

i:q

i,N

∈A

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

В работе [21] для замкнутых сетей аналогичные результаты по-

лучаются для случая более общей зависимости интенсивностей от

длин очередей в узлах.

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

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

ного света одна для всех направлений. Необходимо вместо вершины

i, соответствующей перекрестку, ввести несколько вершин (i, d), где

d перечисляет возможные направления движения на перекрестке i.

Это конечно налагает ограничение на соответствующие времена об-

служивания τ

i,d

в новых вершинах типа

i,d

= τ

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

на пробка. Интереснее рассмотреть ситуацию, когда в разных местах

графа одновременно возникает много пробок.

283

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

ры можно оценить. Именно на практике статистические оценки па-

раметров p

, µ

имеют вид (например, для постоянных µ

)

∼

(T )

, µ

(T ),

где N

(T ) — число автомобилей, повернувших за время T на пере-

крестке i в направлении j.

Практически интересна прежде всего задача оптимизации све-

тофоров, которая может достигаться выбором τ

i,d

, и за счет изме-

нения матрицы P подсказками о выборе маршрута. Более того, в

экспоненциальной модели многие случайные величины независимы,

и, значит, полностью игнорируется проблема синхронизации свето-

форов.

Следует сказать, что проблема светофоров в стохастическом кон-

тексте только начинает изучаться, и постановки задач там должны

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

ных моделях. Однако пока нет понимания (а тем более вывода) связи

жидкостных транспортных моделей со стохастическими (как в ста-

тистической физике).

284

Литература

1. Хейт Ф. Математическая теория транспортных потоков.

М.: Мир, 1966.

2. Renyi A. On two mathematical models of the traﬃc on a divided

highway // Journal of Applied Probability. 1964. V. 1. P. 311–320.

3. Solomon H., Wang P. Nonhomogeneous Poisson ﬁelds of random

lines with applications to traﬃc ﬂow // Proc. Sixth B erkeley Symp.

on Math. Statist. and Prob. 1972. V. 3. P. 383–400.

4. Solomon H. Geometric Probability. Philadelphia: SIAM, 1978.

5. Daley D., Vere-Jones D. An Introduction to the Theory of Point

Processes V. 1. Springer, 2003.

6. Кокс Д., Смит В. Теория восстановления. М.: Мир, 1967.

7. Cox D. R., Isham V. Point processes. Chapman and Hall, 1980.

8. Kelly F. Reversibility and stochastic networks. N.Y.: Wiley, 1979.

9. Caceres F., Ferrari P., Pechersky E. A slow-to-start traﬃc model

related to a M/M/1 queue // Journal of Statistical Mechanics:

Theory and Experiment. 2007. [arXiv:0703709 cond-mat].

10. Иносэ Х., Хамада Т. Управление дорожным движением.

М.: Транспорт, 1983.

11. Traﬃc ﬂow theory: A state-of-the-art report. Editors Gartner N. H.,

Messer C. J., Rathi A. K. Washington DC: Transportation Research

Board, 2001.

12. Blank M. Ergodic properties of a simple deterministic traﬃc ﬂow

model // J. Stat. Phys. 2003. V. 111. P. 903–930.

13. Jost D., Nagel K. Probabilistic Traﬃc ﬂow breakdown in stochastic

car following models // Traﬃc and Granular Flow. 2005 V. 03.

Part 2. P. 87–103.

14. Lotito P., Mancinelli E., Quadrat J.-P. A min-plus derivation

of the fundamental car-traﬃc law // Automatic Control IEEE

Transactions. May 2005. V. 50. N 5. P. 699–705.

285

15. Kerner B. S. Introduction to modern traﬃc ﬂow theory and control.

Berlin: Springer, 2009.

16. Замятин А. А., Малышев В. А. Накопление на границе для од-

номерной стохастической системы частиц // Проблемы передачи

информации. 2007. Т. 43. № 4. С. 68–82.

17. Lighthill M. J., Whitham G. B. On kinematic waves. II. Theory of

traﬃc ﬂow on long crowded roads // Proc. R. Soc. London, Se. A.

1955. V. 229. P. 281–345.

18. Malyshev V., Yakovlev A. Condensation in large closed Jackson

networks // Ann. Appl. Probab. 1996. V. 6. N. 1. P. 92–115.

19. Botvich D. D., Zamyatin A. A. On ﬂuid approximations for

conservative networks // Markov Processes and Related Fields. 1995.

V. 1. N. 1. P. 113–141.

20. Fayolle G., Malys hev V., Menshikov M. Topics in the constructive

theory of countable Markov chains. Cambridge University Press,

1995.

21. Fayolle G., Lasgouttes J.-M. Asymptotics and Scalings for Large

Product-Form Networks via the Central Limit Theorem // Markov

Processes and Related Fields. 1996. V. 2. N. 2. P. 317–349.

22. Revised Traﬃc Flow Theory. A state-of-art report. Editors Gartner

J.-M., Messer C. J., Rathi A. K. Washington DC: Transportation

Research Board, 2001.

23. Рюэль Д. Статистическая механика. Строгие результаты.

М.: Мир, 1971.

24. Малышев В. А., Минлос Р. А. Гиббсовские случайные поля.

М.: Наука, 1985.

25. Малышев В. А. Случайные грамматики // Успехи мат. наук.

1998. Т. 53. № 2. С. 107–134.

26. Serfozo R. Introduction to stochastic networks. Springer, 1999.

27. Федорюк М. В. Метод перевала. М.: Наука, 1977.

286

28. Буслаев А. П., Новиков А. В., Приходько В. М., Таташев А. Г.,

Яшина М. В. Вероятностные и имитационные подходы к опти-

мизации автодорожного движения. М.: Мир, 2003.

29. Афанасьева Л. Г. Очерк Исследования Операций. М.: Изд-во

ЦПИ при механико-математическом факультете МГУ, 2007.

30. Кингман Дж. Пуассоновские процессы. М.: МЦНМО, 2007.

31. Blythe R. A., Evans M. R. Nonequilibrium steady states of matrix-

product form: a solver’s guide // Journal of Physics A: Mathematical

and Theoretical. 2007. V. 40. N. 46.

32. Derrida B. Non-equilibrium steady states: ﬂuctuations and large

deviations of the density and of the current // Journal of Statistical

Mechanics: Theory and Experiment. July 2007.

33. Малышев В. А. Кратчайшее ведение в современные вероятност-

ные модели. М.: Изд-во ЦПИ при механико-математическом

факультете МГУ, 2009.

http://mech.math.msu.su/

malyshev/Malyshev/Lectures/course.pdf

287