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

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

откуда немедленно следует, что y

†

= 0, y

†

= 1, при этом системные

затраты c(y

†

, y

†

) = 1 · y

†

+ y

†

· y

†

= 1.

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

дропа (системный оптимум) определяется как решение оптимизаци-

онной задачи:

min y

+ y

, y

+ y

= 1, y

, y

≥ 0, (20)

минимум которой достигается в точке y

⋆

= y

⋆

= 0.5, м инимальные

затраты c(y

⋆

, y

⋆

) = 0.75, что на 25% уменьшает системные издержки

в сети.

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

в конкурентном равновесии могут составлять 4/3 от суммарных за-

трат системного оптимума. Оказывается, это соотношение представ-

ляет собой неулучшаемую оценку сверху для конкурентного пото-

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

топологии сети. Для подробного изложения этого результата устано-

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

ные и оптимальные потоки.

Условие равновесия (2) для вектора x

†

∈ X можно переписать

следующим образом: для каждой пары источник–сток w ∈ W в сети

Γ выполнены условия:

если x

†

> 0, то G

†

) = u

†

≤ G

†

) для всех q ∈ P

Отсюда, очевидно, следует, что если x

†

> 0 и x

†

> 0 для путей

p, q ∈ P

, то G

†

) = G

†

) = u

†

, что, собственно говоря, и

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

го принципа Вардропа.

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

c(x

†

)) при равновесном распределении x

†

вносят только ненулевые

потоки x

†

> 0, а для них все удельные затраты в пределах одной

пары w одинаковы и равны u

†

, то значение c(x

†

) можно рассчитать

следующим образом:

c(x

†

) =

p∈P

†

w∈W

p∈P

†

w∈W

†

p∈P

†

w∈W

†

(21)

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

⋆

и си-

стемный оптимум c (x

⋆

) соответствуют решению оптимизационной

задачи:

c(x) =

p∈P

(x)x

→ min, x ∈ X. (22)

Положим c

(x) = G

(x)x

и будем предполагать, что для всех p ∈ P

функции c

(x) являются выпуклыми и непрерывно дифференциру-

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

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

⋆

— решения задачи (22), то есть оптималь-

ное распределение потоков в сети. Тогда для всякой пары w ∈ W ,

если x

⋆

> 0, p ∈ P

, то

∂c(x

⋆

)

∂x

≤

∂c(x

⋆

)

∂x

для всех q ∈ P

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

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

, такой, что x

⋆

¯p

> 0 и

∂c(x

⋆

)

∂x

∂c(x

⋆

)

∂x

для некоторого ¯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, при этом в силу выпуклости

функции c(x) имеем оценку

c(x

) − c(x

⋆

) ≤ ∇c(x

)(x

− x

⋆

) = ε



∂c(x

)

∂x

−

∂c(x

)

∂x



< 0,

что противоречит оптимальности x

⋆



В частном случае, когда G

(x) ≡ G

), из теоремы 5 непосред-

ственно следует, что в оптимальном распределении потоков x

⋆

для

всякой пары w ∈ W , если x

⋆

> 0, p ∈ P

, то

∂c

⋆

)

∂x

≤

∂c

⋆

)

∂x

для

всех q ∈ P

. При этом, как и в случае равновесных потоков, для оп-

тимальных потоков справедливы равенства

∂c

⋆

)

∂x

∂c

⋆

)

∂x

для

тех p, q ∈ P

, для которых x

⋆

> 0, x

⋆

> 0. Эти условия известны

также как условия Гиббса (см., например, [7]).

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

ние каждого пути p ∈ P складываются только из затрат на проезд

по дугам, составляющим этот путь, то есть G

(x) определяются по

формуле (15), при этом затраты по дугам τ

(y) описываются аффин-

ными функциями τ

(y) = a

+ b

, где a

и b

— неотрицательные

коэффициенты для всех e ∈ E. При этом функция системных затрат

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

c(x) =

p∈P

e∈E

(y)x

e∈E

(y)y

e∈E

+ b

∂c(x)

∂x

e∈E

(2a

+ b

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

†

= (y

†

: e ∈ E) и y

⋆

= (y

⋆

: e ∈ E) — загрузку

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

†

и x

⋆

соответственно. Опираясь

на приведенные выше результаты для равновесных x

†

и оптималь-

ных x

⋆

потоков, выполнены следующие условия:

равновесие: если x

†

> 0, p ∈ P

, то для любого q ∈ P

выполнено

e∈E

†

+ b

) ≤

e∈E

†

+ b

); (23)

оптимальность: если x

⋆

> 0, p ∈ P

, то для любого q ∈ P

выпол-

нено

e∈E

(2a

⋆

+ b

) ≤

e∈E

(2a

⋆

+ b

). (24)

Любопытно, что при линейных функциях задержек τ

(y) = a

из неравенств (23) и (24) следует совпадение равновесных и опти-

мальных потоков.

Следуя работе [46], через тройку [Γ, ρ, G(x)] обозначим транс-

портную модель, определенную на сети Γ, с матрицей корреспон-

денций ρ = (ρ

: w ∈ W ) и затратами G(x) = (G

(x) : p ∈ P ). Везде

далее будем полагать

(x) =

e∈E

(y) =

e∈E

+ b

). (25)

Имеет место следующий результат.

Лемма 1. Пусть x

†

— решение задачи транспортного равновесия

для модели [Γ, ρ, G(x)]. Тогда вектор

†

является решением опти-

мизационной задачи для модели [Γ,

ρ, G(x)].

Дока зат ельство. Если x

†

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

новесной модели [Γ, ρ, G(x)], то, очевидно,

†

— допустимое решение

оптимизационной модели [Γ,

ρ, G(x)], при этом неравенства (24) для

†

переходят в (23). 

Более того, для каждого маршрута p ∈ P

, такого, что x

†

> 0,

выполнено

∂c(

†

)

∂x

e∈E

†

+ b

} = u

†

Лемма 2. Пусть x

⋆

— оптимальное распределение потоков, отве-

чающее транспортной модели [(Γ, ρ, G(x)]. Тогда для любого допу-

стимого потока x

в модели [Γ, (1 + δ)ρ, G(x)] справедлива оценка

c(x

) ≥ c(x

⋆

) + δ

w∈W

⋆

)ρ

, (26)

где δ ≥ 0, v

⋆

) = min

p∈P

∂c(x

⋆

)

∂x

Дока зат ельство. Рассмотрим допустимые относительно модели

[Γ, (1+δ)ρ, G(x)] потоки x

. При затратах G

(x), определенных в (25),

где все коэффициенты a

≥ 0, функция c(x) выпукла, отсюда

c(x

) ≥ c(x

⋆

) +

∂c(x

⋆

)

∂x

− x

⋆

) = c(x

⋆

) +

p∈P

∂c(x

⋆

)

∂x

− x

⋆

) =

= c(x

⋆

) +

w∈W

p∈P

∂c(x

⋆

)

∂x

− x

⋆

) =

= c(x

⋆

) +

w∈W



p∈P

∂c(x

⋆

)

∂x

−

p∈P

∂c(x

⋆

)

∂x

⋆



Поскольку для p, таких, что x

⋆

> 0, производная

∂c(x

⋆

)

∂x

принимает

минимальное значение:

∂c(x

⋆

)

∂x

= min

q∈P

∂c(x

⋆

)

∂x

= v

⋆

то

p∈P

∂c(x

⋆

)

∂x

⋆

p∈P

⋆

Следовательно, продолжая оценку снизу для c(x

), получаем

c(x

) ≥ c(x

⋆

) +

w∈W

(

p∈P

⋆

−

p∈P

⋆

) =

= c(x

⋆

) +

w∈W

⋆

)(

p∈P

−

p∈P

⋆

) =

= c(x

⋆

) +

w∈W

⋆

)((1 + δ)ρ

− ρ

) = c(x

⋆

) + δ

w∈W

⋆

)ρ



Итоговый результат текущего разде ла устанавливает следующая

теорема.

Теорема 6. Для транспортной модели [Γ, ρ, G(x)] с аффинными

функциями задержек (25) для оптимального x

⋆

и равновесного x

†

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

c(x

†

)/c(x

⋆

) ≤ 4/3.

Дока зат ельство. Cогласно (21) системные затраты для равно-

весного распределения x

†

рассчитываются как

c(x

†

) =

w∈W

†

)ρ

по лемме 1 поток

†

оптимален для транспортной модели [Γ,

ρ, G(x)],

при этом v

(

†

) = u

†

Положим δ = 1 в оценке (26). Тогда для произвольного потока x,

допустимого в модели [Γ, 2

ρ, G(x)] = [Γ, ρ, G(x)], имеем

c(x) ≥ c



†



w∈W



†



= c



†



w∈W

†

)ρ

= c



†



c(x

†

(27)

Осталось получить оценку снизу c(

†

) в терминах c(x

†

), что легко

сделать, учитывая вид функций задержки:



†



e∈E

†



†

+ b



≥

e∈E

†

+ b

) =

c(x

†

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

гам (y

†

, e ∈ E), индуцированные равновесными потоками по марш-

рутам x

†

. Очевидно, что при этом потоки

†

будут индуцировать

загрузку дуг (

†

, e ∈ E).

В результате, продолжая оценку (27), получим

c(x) ≥

c(x

†

) +

c(x

†

) =

c(x

†

Вычисляя в последнем неравенстве минимум левой части по всем x,

допустимым в модели [Γ, ρ, G(x)], получаем

c(x

†

)/c(x

⋆

) ≤ 4/3.



1.2. Построение матрицы корреспонденций

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

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

, w = (i, j) рассматривается как средний поток

пользователей, который из источника i ∈ S должен прибыть в сток

j ∈ D. В данном разделе вместо ρ

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

, чтобы выделять характеристики источников i и стоков j.

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

цы ρ = (ρ

: i ∈ S, j ∈ D), в том числе с применением математиче-

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

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

спонденций. Описание указанных моделей для транспортных сетей

можно найти, например, в работах [3–5; 13, 14, 20, 31].

1.2.1. Гравитационная модель

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

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

с силой, прямо пропорциональной произведению масс этих тел и об-

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

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

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

суммарный объем выезжающего/въезжающего потока, физическое

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

с передвижением. В самом простой форме гравитационная модель

имеет вид

= κ

, i ∈ S, j ∈ D. (28)

где s

— общий объем выезжающих из пункта i ∈ S, d

— общий

объем въезжающих в пункт j ∈ D, c

— удельные затраты на пере-

движение из i в j, κ > 0 — калибровочный коэффициент.

Система (28) обладает существенным недостатком. Нетрудно ви-

деть, что при увеличении объемов s

и d

, например, в два раза, мо-

дель (28) приведет к увеличени ю корреспонденции ρ

в четыре раза,

что совершенно нелогично. Поэтому вместо классической гравита-

ционной модели (28) на практике используют ее модификацию, в

которой к условию (28) добавляют дополнительные условия, напри-

мер, балансовые ограничения на выезд и въезд. Кроме того, квадрат

расстояния (затрат) c

заменяют на так называемую функцию тя-

готения f (c

), характеризующую предпочтения индивидуумов при

выборе пары источник–сток (i, j) для передвижения. В результате

модифицированная гравитационная модель имеет вид

f(c

)

j=1

= s

i=1

= d

, ρ

≥ 0, i ∈ S, j ∈ D,

или, что то же:

= α

f(c

), i ∈ S, j ∈ D, (29)

где калибровочные коэффициенты α

и β

определяются из системы





j∈D

f(c

)





−1

, β

i∈S

f(c

)

−1

. (30)

Очевидно, что система будет совместной только тогда, когда сум-

марные объемы по выезду и въезду равны

i∈S

j∈D

Выбор функции тяготения f осуществляется либо в процессе ка-

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

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

ражений о предпочтениях при выборе пары источник–сток. Одна из

аппроксимаций функции имеет следующий вид: f(c

) = exp(−γc

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

γ ≈ 0.065, θ ≈ 1 (см., например, [20] и ссылки там).

Важно отметить, что величины α

и β

зависят от всего набора

и d

, а следовательно, и объемы корреспонденций ρ

зависят от

загрузки всей системы.

Численные значения α

и β

определяют по специальной итера-

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

вестна как метод балансировки Шацкого—Шелейховского [19, 22].

В зарубежной литературе метод балансировки имеет свою независи-

мую историю развития. Например, в работе [24] описана следующая

процедура: начиная с матрицы

= s

f(c

)

l∈D

f(c

)

−1

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







i∈S

−1

, если

i∈S

> d

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

= s

−

j∈D

, r

= d

−

i∈S

;

k+1

= ̺

+ q

f(c

)

l∈D

f(c

)

−1

(31)

Вычислительные эксперименты по расчету трудовых корреспон-

денций на примере УД С г. Владивостока [12] (строилась матрица

размерности 638 ×638) показали высокую скорость сходимости про-

цесса (31) к искомой матрице корреспонденций — сбалансированная

матрица была получена всего за 4 итерации.

1.2.2. Энтропийная модель

Как и в случае гравитационного подхода, идею построения энтро-

пийной модели подсказала физика, а именно второй закон термо-

динамики, утверждающий, что любая замкнутая физическая систе-

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

характеризуется максимумом энтропии этой системы. Впервые кон-

цепция энтропии для определения матрицы корреспонденций была

использована в работе [47].

Транспортную систему как систему передвижения индивидуумов

по УДС города объединяет с физической наличие очень большо-

го числа неуправляемых элементов. При определенных допуще ни ях,

например, таких как неизменность затрат на проезд по маршр утам,

неизменность топологии УДС (исключаются реконструкция, введе-

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

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

корреспонденций ρ

можно ставить как задачу максимизации эн-

тропии в транспортной системе.

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

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

зоны источниками и объединим их в множество S, и по зонам, по-

глощающим потоки, назовем их стоками и объединим в множество

D. Источниками, например, м огут служить районы жилых масси-

вов, стоками — мес та приложения труда. Индивидуумы в транспорт-

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

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

номер паспорта. Состояние транспортной системы определяется рас-

пределением «помеченных» индивидуумов между парами источник–

сток.

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

только общее количество индивидуумов без детализации по составу

их идентификаторов. Поэтому каждой паре источник–сток соо твет-

ствует величина корреспонденции ρ

— колич ество индивидуумов,

выезжающих из источника i ∈ S и прибывающих в сток j ∈ D. Оче-

видно, что существует множество состояний, приводящих к одной

и той же матрице корреспонденций ρ = {ρ

: i ∈ S, j ∈ D}. Сле-

дуя принципу максимизации энтропии, будем искать значения ρ

доставляющие максимум функции P (ρ), определяющей вероятность

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

спонденций ρ.

Обозначим через ν(ρ) — вероятность каждой реализации матри-

цы ρ, через Q(ρ) — количество состояний системы, соответствующих

ρ. Тогда

P (ρ) = ν(ρ)Q(ρ). (32)

Пусть в си стеме имеется n источников и m стоков. Обозначим

через R =

i=1

j=1

— общее количество индивидуумов в системе,

через ν

> 0 — вероятность выбора индивидуумом коммуникации

По аналогии со схемой Бернулли значение ν(ρ) определяется фор-

мулой

ν(ρ) = ν

· ν

· . . . · ν

i=1

j=1

Вычислим количество состояний Q(ρ). Если объем корреспонден-

ции из источника 1 в сток 1 равен ρ

, то количество способов дости-

жения этого объема равно C

. Далее, из оставшейся части инди-

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

равно C

R−ρ

, корреспонденции ρ

равно C

R−ρ

−ρ

и так далее.