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

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

1.1. Задача транспортного равновесия

Моделирование и исследование транспортных потоков часто прово-

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

сия, описывающего достаточно адекватный механизм функциониро-

вания автомобильных улично-дорожных сетей (УДС). Рассматрива-

емые модели позволяют получить прогнозные оценки по загрузке

элементов транспортной сети. Подобные задачи интересны в част-

ности тем, что являются одним из инструментов для объективной

оценки эффективности проектов по модификации УДС с точки зре-

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

общих затрат на передвижение пользователей сети.

1.1.1. Моделирование транспортных потоков как

задача принятия решений

Для определения объемов загрузки УДС в первую очередь необ-

ходимо выявить правила, по которым водители выбирают тот или

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

транспортной сети окончательно были сформулированы в работе

[48], где постулировались следующие две возможные ситуации.

1. Пользователи сети независимо друг от друга выбирают марш-

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

портным расходам.

2. Пользователи сети выбирают маршруты следования исходя из

минимизации общих транспортных расходов в сети.

С тех пор в транспортной науке приведенные поведенческие принци-

пы получили названия соответственно первого и второго принципов

Вардропа.

Распределение транспортных потоков согласно первому принци-

пу Вардропа соответствует конкурентному бескоалиционному рав-

новесию, предполагающему совершенный эгоизм участников дорож-

ного движения — каждый стремится достигнуть конечного пункта

своей поездки как можно быстрее и из имеющихся возможных вари-

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

минимальные затраты (временные, финансовые, моральные и т.п.)

на проезд. Поэтому данный принцип также называют оптимизаци-

ей пользователей (user optimization).

Стоит отдельно отметить, что первый поведенческий принцип

предполагает определенные допущения. Во-первых, это совершенная

информированность участников движения о ситуации на дорогах —

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

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

изрядной идеализацией, но развитие автоматизированных автонави-

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

к такой ситуации. Во-вторых, предполагается ничтожно мало е влия-

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

Хотя такое предположение и заведомо неверно для крупногабарит-

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

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

или неопытных водителей за рулем.

Второй принцип Вардропа предполагает централизованное

управление движением в сети. Соответствующее ему распределение

транспортных потоков называют системным оптимумом

(system optimization). Примером пользователей, передвигающихся

согласно второму принципу, служат водители маршрутизированного

транспорта.

Несмотря на то, что принципы потокового равновесия широко

цитируются как принципы Вардропа, на самом деле чуть ранее их

сформулировали Ф. Найт [36] и А. Пигу [45], утверждая, что все

участники движения, направляющиеся из некоторого узла сети в

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

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

была одна и та же для всех.

В ситуации массовой автомобилизации, имеющей место практи-

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

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

и миниавтобусы, совершающие преимущественно маятниковые по-

ездки: место проживания – место работы и обратно. Именно такие

поездки создают пиковые нагрузки на УДС, вызывают основные по-

тери времени и други х ресурсов, повышают аварийность и услож-

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

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

именно легковым частным транспортом. Как правило, водители та-

кого транспорта преследуют исключительно личные цели и стремят-

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

дение явно соответствует первому принципу Вардропа.

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

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

со скалярным произведением xy и нормой

kxk =

√

xx, x, y ∈ R

. Элементами пространства являются векторы-

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

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

запись формул.

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

Исходя из приведенных соображений, построим экономико-

математическую модель транспортных потоков в УДС, соответству-

ющую первому поведенческому принципу Вардропа.

Транспортную сеть опишем в виде ориентированного графа

Γ(V, E) , где V — множество вершин, E — множество дуг сети. Каж-

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

ков. Каждая вершина представляет узел, разделяющий участки до-

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

Магистрали с двусторонним движением соответственно имеют пар-

ные противоположно ориентированные дуги.

При исследовании потокообразующих факторов в множестве вер-

шин V выделим два подмножества: первое S ⊆ V содержит пункты,

порождающие потоки, элементы множества S назовем источника-

ми; второе D ⊆ V содержит пункты, поглощающие потоки, элемен-

ты множества D назовем стоками. Применительно к задаче моде-

лирования потоков, порождаемых ежедневной трудовой ми грацией

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

и пригороды, стоками — деловые районы города. Множество всех

потокообразующих пар представим в виде декартова произведения:

W = {w = (i, j) : i ∈ S, j ∈ D}.

Каждой паре и сточник–сток w = (i, j) ∈ W соответствует свой

спрос на перевозку ρ

— общий объем пользователей, которые из

пункта i должны прибыть в пункт j. Набор {ρ

: w ∈ W } называет-

ся матрицей корреспонденций. Объемы корреспонденций ρ

могут

иметь фиксированные значения или являться функциями от зат рат

на передвижения в сети, то есть ρ

= ρ(u

), где u

— минимальные

транспортные затраты на проезд для пары w, зависящие в свою оче-

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

ного равновесия с фиксированным спросом, во втором — о задаче с

эластичным спросом.

Путем (маршрутом) в сети Γ, соединяющим вершины i и j, на-

зовем последовательность дуг e

= (i → k

), e

= (k

→ k

), . . . ,

= (k

l−1

→ k

), e

l+1

= (k

→ j), где e

∈ E при всех t = 1, . . . , l+1.

Предполагается отсутствие петель и циклов в маршрутах. Обозна-

чим через P

множество альтернативных маршрутов, следуя кото-

рым для каждой пары w = (i, j) ∈ W исходящий из источника i

поток достигает стока j. Совокупность всех путей в сети Γ обозна-

чим через P =

w∈W

Пусть x

— это величина потока, идущего по пути p ∈ P . Тра-

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

быть неотрицательными и удовлетворять балансовым ограничениям.

Поэтому для каждой пары w потоки x

, p ∈ P

, должны принадле-

жать множеству

= {x

≥ 0 : p ∈ P

p∈P

= ρ

Объединим велич ины x

в вектор x = (x

: p ∈ P ). Тогда допусти-

мой областью для вектора x является множество, образованное как

декартово произведение всех X

X =

w∈W

= {x ≥ 0 :

p∈P

= ρ

, w ∈ W }. (1)

Преодоление каждого из путей p ∈ P сопровождается некото-

рыми затратами (время, топливо, деньги, амортизация автомобиля,

износ дороги и т.п.). Количественная характеристика таких затрат

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

ло, в моделях рассматриваются временные или финансовые затр аты.

Обозначим через G

удельные затраты пользователей на проезд по

пути p. Поскольку на затраты по одному маршруту может влиять

загрузка других путей УДС, то в общем случае G

представляют

собой функции от загрузки всей сети, то есть G

= G

(x).

Во введенных обозначениях первый принцип Вардропа можно

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

меньшими транспортными расходами, поэтому если по пути p ∈ P

для пары w идет ненулевой поток, то затраты по этому пути мини-

мальны, то есть

если x

†

> 0, то G

†

) = min

q∈P

†

) = u

†

), (2)

где u

†

) — минимальные транспортные затраты по маршрутам,

соединяющим пару w ∈ W , при загрузке сети, определяемой векто-

ром x

†

. Потоки x

†

∈ X, удовлетворяющие условию (2), называются

равновесными. Проблема поиска равновесных потоков x

†

∈ X назы-

вается задачей транспортного (потокового) равновесия.

1.1.3. Сведение к вариационному неравенству

Основной подход к решению задачи транспортного равновесия состо-

ит в сведении условия (2) к вариационному неравенству или задаче

дополнительности [17, 30, 38, 40], а в частном случае — к оптимиза-

ционной задаче [3, 16, 20, 26], и дальнейшем применении существу-

ющих численных методов.

Для компактности последующего изложения объединим компо-

ненты G

(x) в вектор-функцию G(x) = (G

(x) : p ∈ P ). Отдельно

рассмотрим случаи эластичного и неэластичного спроса.

1.1.3.1. Транспортная задача с фиксированным спросом

Пусть для каждой пары w ∈ W объемы корреспонденций ρ

за-

даны и имеют фиксированные значения. Справедлив следующий ре-

зультат.

Теорема 1. Вектор x

†

∈ X удовлетворяет условию равновесия

(2) тогда и только тогда, когда является решением вариационного

неравенства

G(x

†

)(x − x

†

) ≥ 0, ∀x ∈ X. (3)

Дока зат ельство. Пусть вектор x

†

= (x

†

: p ∈ P ) ∈ X является

решением вариационного неравенства (3). Покажем, что в x

†

выпол-

нено условие (2). Предположим противное, а именно, что для пары

w существует путь ¯p ∈ P

, такой, что x

†

¯p

> 0 и G

¯p

†

) > G

¯q

†

) для

некоторого ¯q ∈ P

, ¯q 6= ¯p. Рассмотрим вектор x

= (x

: p ∈ P ),

такой, что







†

, p 6= ¯p, p 6= ¯q,

†

¯p

− ε, p = ¯p,

†

¯q

+ ε, p = ¯q,

где ε > 0 достаточно мало и не нарушает условия неотрицательности

≥ 0. Нетрудно видеть, что x

∈ X, при этом

G(x

†

)(x

− x

†

) = G

¯p

†

)(x

¯p

− x

†

¯p

) + G

¯q

†

)(x

¯q

− x

†

¯q

) =

= ε(G

¯q

†

) − G

¯p

†

)) < 0,

что противоречит тому, что x

†

— решение вариационного неравен-

ства (3). Следовательно, в точке x

†

условие (2) всегда выполнено.

Пусть вектор x

†

∈ X удовлетворяет условию (2). При этом для

всех p ∈ P

и w ∈ W выполнено

†

) − u

†

) ≥ 0, (G

†

) − u

†

))x

†

= 0,

†

) − u

†

))x

≥ 0, ∀x ∈ X,

следовательно, имеет место оценка

0 ≤

w∈W

p∈P

†

) − u

†

))(x

− x

†

) =

w∈W

p∈P

†

)(x

− x

†

) −

w∈W

p∈P

†

)(x

− x

†

) =

= G(x

†

)(x − x

†

) −

w∈W

†

)



p∈P

−

p∈P

†



= G(x

†

)(x − x

†

то есть x

†

— решение вариационного неравенства (3). 

К настоящему времени теория и методы решения вариационных

неравенств уже достаточно хорошо разработаны (см., например, мо-

нографии [32, 37, 38, 40]). Одним из наиболее известных является

проективный метод и его модификации, по мнению авторов, особен-

но подходящие для решения транспортных задач. В связи с этим

далее понадобятся следующие результаты.

Определение 1. Проекцией точки y ∈ R

на множество

X ⊂ R

называется точка π

(y) = argmin{ky − xk : x ∈ X}.

Критерием проверки, является ли вектор p проекцией точки

y ∈ R

на множество X, служит выполнение условия

(p − y)(x − p) ≥ 0, ∀x ∈ X. (4)

Решение вариационного неравенства (3) тесно связано с поис-

ком неподвижных точек проективного отображения H(x) = π

(x −

−λG(x)), где λ > 0 — некоторое фиксированное число.

Утверждение 1. Множество решений X

†

⊆ X вариационного

неравенства (3) совпадает с множеством неподвижных точек отоб-

ражения H(x), то есть X

†

= {x

†

∈ X : x

†

= H(x

†

)}.

Дока зат ельство. Пусть x

†

∈ X

†

и λ > 0, тогда выполнено нера-

венство

†

− (x

†

− λG(x

†

))(x − x

†

) ≥ 0, ∀x ∈ X,

следовательно, в силу свойства (4) имеем x

†

= π

†

− λG(x

†

) =

= H(x

†

Пусть x

†

= H(x

†

), тогда по свойству (4) для любого x ∈ X вы-

полнено условие

0 ≤ ( x − x

†

)(x

†

− (x

†

− λG(x

†

)) = G(x

†

)(x − x

†

то есть x

†

∈ X

†

. 

Теорема 2. Пусть вектор-функция G непрерывна по каждой ком-

поненте, множество X непусто, выпукло и замкну то. Если X

ограничено, то вариационное неравенство (3) разрешимо.

Дока зат ельство. Для выпуклого множества X отображение

H( x) : X → X является непрерывным и однозначным. Множество

X по условию теоремы компактно, следовательно, по теореме Брау-

эра (см., например, [1, 8, 18]) у H(x) существует неподвижная точка

†

= H(x

†

), которая в силу утверждения 1 одновременно является

решением вариационного неравенства (3). 

Нетрудно видеть, что при фиксированных н еотрицательных кор-

респонденциях ρ

допустимая область X, определенная в (1), явля-

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

Следовательно, если затраты на передвижение G

(x) являются непре-

рывными функциями от потоков x ∈ X, то задача транспортного

равновесия с фи ксированным спросом всегда разрешима. Единствен-

ность решения гарантирует свойство строгой монотонности вектора-

функции G(x).

Определение 2. Вектор-функция G : X → R

называется строго

монотонной на X, если для любых x, y ∈ X, таких, что x 6= y,

выполнено (G(x) − G(y))(x − y) > 0.

Теорема 3. Если вектор-функция G(x) строго монотонна, то ва-

риационное неравенство (3) может иметь не более одного решения.

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

ществуют два различных решения x

, x

∈ X, x

6= x

, задачи (3).

Очевидно, при этом выполнены неравенства

G(x

)(x

− x

) ≥ 0, G(x

)(x

− x

) ≥ 0,

складывая которые, получаем

(G(x

) − G(x

)(x

− x

) ≥ 0,

что противоречит свойству строгой монотонности G(x). 

С точки зрения задачи транспортного равновесия утверждение

теоремы 3 означает, что если транспортные затраты возрастают с

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

ние, то существует единственное равновесное распределение транс-

портных потоков.

1.1.3.2. Транспортное равновесие с эластичным спросом

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

портных затрат, то есть ρ

= ρ

). Предположим, что для каж-

дого маршрута p ∈ P транспортные затраты G

(x) строго положи-

тельны, а для всех пар w ∈ W функция спроса ρ

) принимает

только неотрицательные значения.

Объединим величины u

в вектор u = (u

: w ∈ W ), функции

) — в вектор ρ(u) = (ρ

) : w ∈ W ). Построим векторы

z =

, F (z) =

G(x) − Ξu

x − ρ(u)

где Ξ = (ξ

: p ∈ P, w ∈ W ) — матрица инцидентности путей и пар

источник–сток:



1, если путь p соединяет пару w,

0 — в противном случае.

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

тант Z = {z : z ≥ 0}.

Утверждение 2. Вектор z

†

= (x

†

, u

†

) ≥ 0 является решением

вариационного неравенства

F (z

†

)(z − z

†

) ≥ 0, ∀z ∈ Z, (5)

тогда и только тогда, когда x

†

— решение вариационного неравен-

ства (3) с допустимой областью X = X(u

†

) = {x ≥ 0 : Ξ

x =

= ρ(u

†

)}.

Дока зат ельство. Пусть x

†

∈ X — решение вариационного нера-

венства (3) и u

†

= (u

†

) : w ∈ W ), где u

†

) = min

q∈P

†

) > 0.

Тогда для любых x ≥ 0 и u ≥ 0 выполнены условия

(G(x

†

) − Ξu

†

= 0, (G(x

†

) − Ξu

†

)x ≥ 0,

(Ξ

†

− ρ(u

†

))u

†

= 0, (Ξ

†

− ρ(u

†

))u = 0.

Откуда следует, что

0 ≤ ( G(x

†

) − Ξu

†

)(x − x

†

) + (Ξ

†

− ρ(u

†

))(u − u

†

) = F (z

†

)(z − z

†

Покажем обратное. Пусть z

†

= (x

†

, u

†

) ≥ 0 — решение вариаци-

онного неравенства (5), то есть для любых z ≥ 0 выполнено

F (z

†

≤ F (z

†

)z.

Рассмотрим точки z

= σz

†

≥ 0 для всех σ ≥ 0. Им еем

F (z

†







≤ 0 при σ = 0,

≥

F (z

†

→ 0 при σ → +∞.

Следовательно, F (z

†

= 0 и F (z

†

)z ≥ 0.

Если предположить существование индекса l, такого, что соот-

ветствующий ему элемент вектора F (z

†

) отрицательный, F

†

) < 0,

то, выбирая z

→ +∞, получаем нарушение неравенства F (z

†

)z ≥ 0.

Отсюда F (z

†

) ≥ 0. Таким образом, точка z

†

= (x

†

, u

†

) ≥ 0 удовле-

творяет системе

F (z

†

) ≥ 0, z

†

≥ 0, F(z

†

= 0, (6)

известной в литературе как нелинейная задача дополнительности

(см., например, [17, 32]).

Перепишем условия (6) в виде

G(x

†

) − Ξu

†

≥ 0, x

†

≥ 0, (G(x

†

) − Ξu

†

= 0, (7)

†

− ρ(u

†

) ≥ 0, u

†

≥ 0, (Ξ

†

− ρ(u

†

))u

†

= 0. (8)

Система (7) показывает, что вектор u

†

соответствует минимальным

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

†

. При условии положительности транспортных затрат из (8) сле-

дует, что Ξ

†

− ρ(u

†

) = 0, тогда неравенство (5) можно переписать

в виде

G(x

†

)(x − x

†

) ≥ u

†

(Ξ

x − ρ(u

†

)) = 0, ∀x ∈ X(u

†



Из утверждения 2 следует, что решение задачи транспортного

равновесия с эластичным спросом сводится к решению вариационно-

го неравенства (5), которое в свою очередь эквивалентно нелинейной

задаче дополнительности (6). Допустимая область Z вариационного

неравенства (5) неограничена, поэтому для существования решения

†

помимо непрерывности необходимы дополнительные предположе-

ния о свойствах вектора-функции F (z).

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

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

ниченность потенциального множества решений, коэрцитивность, мо-

нотонность и прочие. Общая идея выявления таких свойств состоит

в следующем. Выберем радиус R > 0, такой, что пересечение замкну-

того шара B = {z : kzk ≤ R} с выпуклым замкнутым множеством Z

непусто, положим Z

= Z ∩ B 6= ∅. По теореме 2 с уществует точка

†

∈ Z

, такая, что

F (z

†

)(z − z

†

) ≥ 0, ∀z ∈ Z

. (9)

Теорема 4. Пусть вектор-функция F непрерывна по каждой ком-

поненте, множество Z непусто, выпукло и замкнуто. Если суще-

ствует радиус R > 0, такой, что Z

6= ∅, и решение z

†

∈ Z

вариационного неравенства (9) удовлетворяет условию kz

†

k < R,

то вариационное неравенство (3) разрешимо.

Дока зат ельство. Для произвольного z ∈ Z выберем λ ∈ (0, 1],

такое, что точка ¯z = z

†

+ λ(z − z

†

) ∈ Z

. Имеем

0 ≤ F (z

†

)(¯z − z

†

) = F (z

†

)(z

†

+ λ(z − z

†

) − z

†

) = λF (z

†

)(z − z

†