Поиск неэффективных ребер в транспортных сетях

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

Водителей можно считать игроками, множество доступных маршрутов - множеством стратегий, а издержки в пути (временные, финансовые и прочие), взятые со знаком «минус», - выигрышем игрока. При этом издержки, сопряженные с проездом по маршруту, являются суммой издержек на. ребрах, входящих в маршрут. В свою очередь издержки на. ребре зависят от того, сколько игроков его используют в своих стратегиях. Тем самым мы определили игру [13].

Равновесием Нэша-Вардропа [17] в данной игре называется такое распределение водителей по маршрутам, что ни один из водителей не сможет увеличить свой выигрыш, единолично изменив свою стратегию.

Равновесные модели распределения потоков - статические модели, в которых предполагается, что в исследуемой системе реализуется равновесие Нэша-Вардропа. Наиболее популярной на. практике стала, модель BMW [1]. Оказалось, что введенная выше игра, в предположениях модели BMW является потенциальной игрой [16], вследствие чего равновесие является глобально устойчивым, т.е. под действием любой «разумной» динамики система «скатывается» в положение равновесия. Это подтвердилось и экспериментами [12]. Стоит отметить, что предположения BMW-модели достаточно плохо описывают реальный транспортный поток в предзаторном и заторном состояниях. В последние годы было предложено достаточно много альтернативных моделей, одной из которых является модель стабильной динамики [7].

В 1969 году Дитрих Браесс привел пример [2] транспортной системы, в которой строительство новой дороги приводило к увеличению издержек для всех пользователей сети в точке равновесия. С тех пор данный феномен, названный парадоксом Браесса, стал объектом пристального исследования [3-4, 10-11]. Оказалось, что подобные парадоксы наблюдаются в жизни [5], в экспериментальных условиях [12] и являются следствием неэффективности по Парето равновесия Нэша. [8]. При этом было показано, что подобные феномены с большой вероятностью встречаются в больших случайных графах [15]. Все это приводит к задаче поиска неэффективных ребер в транспортном графе или же, в другой постановке, к задаче поиска оптимального подграфа в заданном графе, где критерием качества (обычно) принимаются суммарные издержки пользователей в точке равновесия Нэша-Вардропа. Как было показано в работе [14], данная задача, при весьма, общих предположениях является NP-трудной. Это привело исследователей к необходимости сузить исходную задачу. До сих пор, насколько нам известно, единственный положительный результат был описан в работе [6], где авторы представили субполиномиальный алгоритм поиска для транспортного графа со строго возрастающими линейными функциями зависимости издержек от потока на ребрах. Исследование парадокса Браесса в модели стабильной динамики проводилось только в работе [9], предложенный алгоритм имеет переборный характер.

В нашей работе мы исследуем парадокс Браесса в модели стабильной динамики для графа с одним источником и одним стоком в случае, когда существует и единственно равновесное распределение потоков при некоторых дополнительных предположениях.

Модель стабильной динамики

Пусть в ориентированном графе Г (V, Е, т, /) V - множество вершин графа, а Е = V xV - множество ребер графа, вектор пропускных способностей / и вектор времени свободного движения Т, / = {/1,..., / | е|} , Т = {Т₁,..., Т | е | } . В модели стабильной динамики предполагается, что каждому ребру е соответствует заданная пропускная способность /_е и время свободного движения Т_ё. При этом, если /_ё< /_ё, то Т_ё = Т_е. Если же /_ё = /_е, то Т_ё >  Т_ё. Здесь /_ё - поток по ребру е, / = {/і,..., / | е | }^Т - вектор загрузки сети, Т_е - издержки при проезде по ребру е, Т = { т і , ...,Т | е | } ^Т - вектор издержек в сети. Поясним это, следуя [18].

Допустим, на некоторое ребро е стало поступать больше автомобилей, чем оно способно обслужить. Это приводит к образованию пробки. Временные издержки на прохождение ребра Т_е складываются из минимальных временных издержек Т_е и времени, которое водитель вынужден отстоять в заторе. При этом, пока входящий поток автомобилей на ребро е не снизится до максимально допустимого уровня (/_ё), очередь будет продолжать расти и система не будет находиться в стационарном состоянии. Если же в какой-то момент входящий на е поток снизится до уровня пропускной способности ребра, то в системе наступит равновесие. При этом пробка на ребре е (если входящий поток /_ё будет равен /_ё) не будет рассасываться, т.е. временные издержки так и останутся на уровне Т_е Де. > Т_ё).

Пусть также s Д Е V) - источник корреспонденции, t (t Е V) - сток корреспонденции. Паре источник-сток (s, t) соответствует поток d. Пусть P(_s,_t) ~ множество доступных маршрутов для пары (s,t). Под маршрутом р (р Е P(_s,_t^, ведущим из s в t, мы будем подразумевать упорядоченную связанную последовательность вершин и ребер {s, е_а1, нщ, е_а2,..., t} (vg, Е V. е_а, Е Е). При выборе маршрута, р при загрузке сети / и водителя ожидают издержки:

Ср (Т) = ^ 5ерТе.

еЕЕ

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

Здесь

_ ( 1, если ребро с принадлежит маршруту р, ер [ 0 иначе.

Пусть С_р (г|Т) - издержки на. проезд по маршруту р до тонки г (г Е V. г Е р). Определим также

^{Т (Т}) = min ^{С (Т}).

4EP(s,t)

В статье [7] было показано, что равновесие в модели стабильной динамики может быть найдено как решение следующей оптимизационной задачи:

max т >т

[d • Т (Т) -,Т>]

—*       —

Г = / - s *.

Здесь Т* - вектор множителей Лагранжа в точке оптимума.

( г- ^

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

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

данном уровне загрузке d такая точка единственна.

Некоторые свойства равновесия

В дальнейшем мы будем интересоваться в большей степени состоянием системы именно в состоянии равновесия. Из условия равновесия следует, что издержки на всех используемых в равновесии маршрутах (для одной и той же корреспонденции) совпадают. Если мы обозначим множество используемых в равновесии маршрутов через P^p ^то можно записать это свойство формально:

Vq, р G P^) :   С- (т^6- ) = Ср    ) = min Сі (т^6- ) .

lEP(=,t)

Более того, хорошо известно, что верно и более сильное свойство:

Vq,p G P₍^ ,t) , V j G p,q,j G V :

C- (j Ir^6-)=Ср (j ■ )= min Ci (j Ir^6- ) . ^lEP(s,t)

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

С * ^=С- (ІІТ ^6-) ,q EP^y

Очевидно, что Vq G P(_st) выполняется С_- (т⁶ ) = С * (t).

Пусть задан некоторый ориентированный граф Г (V, Е, Т, /). Любая связная последовательность вершин и ребер ({«д ,e_ai,...,e_ak,up_n }, «д, G V, e_a, G Е) образует на этом графе некоторую ориентированную ломаную. Ее ориентация не обязана совпадать с ориентацией ребер в исходном графе. Мы будем говорить, что связанная последовательность ребер и вершин {«,31 ,e_ai,...,e_ak ,«g_n} задает простую ломаную, если ни одна вершина и ни одно ребро не встречаются в определяющей последовательности более одного раза.

Пусть задан некоторый ориентированный граф Г (V, Е,Т,/) и некоторая простая ломаная G на нем. Тогда можно определить следующую функцию:

dirG (e) = <

1 , -1 , 0 ,

если e G G іі направления на. e в графе Г и ломаной G совпадают, если e G G іі направления на. e в грacjx? Г и ломаной G не совпадают, если e G G.

Определим через Г* (V *,Е *, т, /) граф, содержащий только те ребра и вершины исходного графа Г (V, Е, Т,/), которые принадлежат маршрутам, используемым в равновесии. Другими словами, i G V* (e G Е*) равносильно тому, что i G V, Зр G P(*_sty i G р (e Е Е, e G р). Очевидно, что s ii t всегда, принадлежат V*.

Лемма 1. Пусть задан ориентированный граф Г (V, Е, Т,/), ноток d для пары (s,t) такой, что задача (1) имеет единственное решение (ф⁶,т ^е-У Тогда для любой простой ломаной G из Г* (V*,Е*,Т,/) с началом в s и концом в t, ориентированной из s в t выполняется следующее равенство:

С * № = £т_е^6- dirG ( e ) . eGE

Доказательство. Возьмем произвольную простую ломаную G из Г* (V *,Е*,Т,/у Она определяется некоторой последовательностью вершин и ребер {s,e_Q1 , ...,e_ak,t} up, G V, e_a, G Е. Пронумеруем все вершины на ломаной G согласно порядку, по которому они встречаются в {s,e_ai,...,e_ak , t}.

Далее (в доказательстве), говоря «вершина г», мы будем иметь в виду вершину под номером г в последовательности {s, е_а1, ...,е_ак , t}, определяющей G.

Покажем, что для любой вершины г выполнено:

С * (г + 1) = С * (г) + т^йгтс (ег,г+1).

Здесь через е_г,г+₁ обозначено ребро, соединяющее вершины гиг + 1 в G.

Возможны два случая: а) йгтс (егу+1) = 1 и б) йгтс (ег,г+1) = —1.

Рассмотрим случай «а». Так как вершины г, г + 1 G G С Г * (У *,Е*,т,.рф то они используются некоторыми маршрутами в равновесии. Следовательно, значения С * (г) и С * (г + 1) определены. Из е_г,г+₁ G G С Г* (V *,Е*,T,f} следует, что существует некоторый маршрут р, используемый при равновесном распределении потоков (р G P(*_t)), такой, что ег,г+1 G р, причем, т.к. йгтс (егу+1) = 1, в данном маршруте ребро используется по направлению из г в г + 1. Но отсюда сразу следует, что С * (г) + тД_і+1 = С * (г + 1). Из С * (г) + ДТ+Дгтс (е^,г+1) = С * (г) + тД^ следует требуемое утверждение.

Рассмотрим случай «б». Так как вершины г, г + 1 G G С Г* (У*,Е*,т,/), то они используются некоторыми маршрутами в равновесии. Значит, значения С * (г) и С * (г + 1) определены. Из ег,г+₁ G G С Г* (У*, Е*,т,/) следует, что существует некоторый маршрут р, используемый при равновесном распределении потоков (р G Р(Д)Г такой, что егу+1 G р, причем, т.к. йгтс (ег,г+1) = —1, в данном маршруте ребро используется по направлению из г + 1 в г. Но отсюда сразу следует, что С * (г + 1) + т^е_і+1 = С * (г). Следовательно, С * (г + 1) = С * (г) — т_е^е^₊1. Используя С * (г) — тД^ = С * (г) + те^+Дгтс (ег,г+1). получаем требуемое равенство.

Доказательство (2) получается индукцией (3) по вершинам G вплоть до стока t.

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

Лемма 1 (расширенная). Пусть задан ориентированный граф Г (У, Е), ноток й для нары (s, t) такой, что реализовалось некоторое равновесное распределение потоков по маршрутам (согласно определению Нэша-Вардропа). Тогда для любой простой ломаной G из Г* (У *,Е *) с началом в s и концом в t, ориентированной из s в t, выполняется следующее равенство:

С * (t) = ^т^ йгт_с (е) .

eGE

Поиск неэффективных ребер в транспортной сети

Заметим, что, задавая вектор т, мы тем самым определяем естественный порядок для всех маршрутов из Р(_s,_t). Упорядочим маршруты из Р(_s,t) (|Р(_s,t) | = к) так, чтобы выполнялось следующее условие: Уг, j G 1, к из г <  j следует С_г (т) 6 С (т). Обозначим данный порядок Е.

Назовем ребро графа е «локально» неэффективным, если увеличение стоимости свободного проезда т_е ^ т_е + о(т_е ) по ребру при сохранении порядка маршрутов Е ведет к уменьшению суммарных издержек всех пользователей С * (t).

Заметим, что если ребро е является неэффективным, т.е. если издержки в равновесии в графе Г (У, Е, т,/) выше, чем в графе Г (У, Е/ {е} , т,/), то ребро е должно быть и локально неэффективным.

Воспользуемся следующей леммой.

Лемма 2. Пусть задан ориентированный граф Г ( У, Е, т,/), поток й для пары (s,t) такой, что задача (1) имеет единственное решение (f^eq , т^. Тогда в остаточной сети для графа Г* (У*,Е*,т,/) существует хотя бы один дополняющий путь.

Доказательство. Утверждение леммы непосредственно следует из двойственности задачи (1) задаче MAX-FLOW [7].

Лемма 3. Пусть задан ориентированный граф Г ( V, Е , Т,р), ноток d для пары (s,t) такой, что задача (1) имеет единственное решение (/^еу ,Т^⁹^. Пусть таксисе в графе Г* (V*,Е*,Т,/) есть только один дополняюш,ий путь G. Если граф Г' (V, Е, Т',/) получен из Г(^Е, т, /) путем изменения издержек на некоторых ребрах, причем порядок маршрутов н не менялся, тогда G будет дополняют,им путем и для Г' (V, Е, Т',/).

Доказательство. Заметим, что вхождение ребра е в дополняющий путь G зависит от 'загрузки /_е. но I io от Т_е.

Равновесие в модели стабильной динамики может быть получено с помощью инкрементального наполнения сети. Другими словами, решение (1) может быть получено, если мы будем постепенно заполнять сеть, постепенно увеличивая поток из s в t вплоть до d. При бесконечно маленьком потоке из s в t будет использоваться только маршрут pi. При этом С * (t) = СР1 (т). Когда поток превысит тіп/е, пропускной способности маршрута pi станет еері не хватать для обслуживания всего потока и начнется использование маршрута р2- При этом издержки будут определяться издержками на втором маршруте. Если продолжать этот процесс до того момента, как поток из s в t не станет равным d, будет использовано ровно столько маршрутов из Н, чтобы их суммарная пропускная способность превысила d.

Действительно, если мы определим через Г/(V, Е, т, /) граф, содержащий в себе только те ребра и вершины, которые принадлежат маршрутам под номерами влоть до Z-ro включительно. Определим через U (Г/) максимальную пропускную способность графа Г/ (v,e,т, /). Тогда в равновесии будут использоваться маршруты вплоть до i-ro, который получается из решения следующей задачи оптимизации:

min i, U (И) >  d.

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

Верна следующая

Теорема 1. Пусть задан ориентированный граф Г (V, Е, Т,/), поток d для пары (s,t) такой, что задача (1) имеет единственное решение (/^eq ,т ^е9^. Пусть таксисе в графе Г* (V*,Е*,Т,/) есть только один дополняющей путь G. Тогда ребро е является локально неэффективным, если и только если dirG (е) = — 1.

Доказательство. Из определения дополняющего пути следует, что для любого ребра е Е G выполняется /е < /е. Отсюда следует, что для любого ребра е Е Те = Те-

G выполняется

G. Тогда верно

Так как в нашем случае вектор загрузки / = Д9, то выполнена лемма

Возвмем в качестве простой ломаной в лемме 1 дополняющий путв

С * (t) = ЕееЕ те dir_G (е).

Следователвно,

С * (t) = 52 ТedІrG (е) . ееЕ

Но Е _е^Е Т_edirG (е) - константа. Ее значение зависит только от того, какие ребра принадлежат или не принадлежат дополняющему пути G. Следовательно, ребра, не принадлежащие G, не могут быть локально неэффективными, так как локальное изменение издержек на них не влияет на значение (4). Если допускать только локальные изменения, то влияние на значение (4) могут оказывать только изменения на ребрах, лежащих на дополняющем пути G.

В определении локально неэффективных ребер требуется, чтобы повышение времени свободного движения по ребру приводило к снижению издержек для всех пользователей сети. Из (4) легко видеть, что ребра, для которых dirG (е) = —1, такому требованию удовлетворяют. Ребра же, для которых dirG (е) = 1, напротив, не могут быть неэффективными.

Это приводит нас к алгоритму поиска неэффективных ребер.

Алгоритм:

• 1)    Решение задачи (1).

• 2)    Формирование Г* (И *, Е*,т,/).

• 3)    Нахождение дополняющего пути G в Г* (V*,Е*,т,/).

• 4)    Проверка единственности дополняющего пути.

• 5)    Поиск среди ребер, формирующих G, таких, что dir^ (е) = —1.

Работа выполнена при поддержке грантов РФФИ 11-01-00494-а, 12-01-33007 мол-а- вед, 13-01-12007-офи_м, Лаборатории структурных методов анализа данных в предсказательном моделировании, грант Правительства РФ дог. 11 .G34.31.0073; гранта Президента РФ No МК-5285.2013.9