Поиск равновесия в многостадийных транспортных моделях тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Котлярова Екатерина Владимировна

• Котлярова Екатерина Владимировна
• кандидат наук
• 2022

Оглавление диссертации кандидат наук Котлярова Екатерина Владимировна

Введение

Глава 1. Калибровка энтропийной модели расчёта матрицы

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

1.1 Введение

1.2 Энтропийная модель расчёта матрицы корреспонденций

1.3 Методы решения задачи энтропийно-линейного программирования 12 1.3.1 Задача подсчёта невязки для восстановленной матрицы

затрат

1.4 Восстановление матрицы корреспонденций для г. Москвы . . . . 20 1.4.1 Сравнение функций затрат

Глава 2. Многостадийные транспортные модели

2.1 Основные определения и обозначения

2.2 Введение

2.3 Модели равновесного распределения транспортных потоков по

путям

2.3.1 Связь модели Бэкмана с моделью стабильной динамики

2.4 Двухстадийная модель

2.4.1 Переход к двойственной задаче

2.4.2 Вычислительные эксперименты

Глава 3. Ускорение работы двухстадийной модели

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

3.1 Введение

3.2 Ускорение вычислений энтропийной модели расчёта матрицы корреспонденций

3.3 Ускорение модели равновесного распределения потоков по путям

3.4 Добавление платных дорог в модель

Заключение

Список литературы

Стр.

Список рисунков

Список таблиц

Введение диссертации (часть автореферата) на тему «Поиск равновесия в многостадийных транспортных моделях»

Введение

Задачам транспортного моделирования в последние годы уделяется большое внимание, поскольку строительство новых дорог без должного планирования может приводить к пробкам (см. парадокс Браесса [1]), а число автомобилей на душу населения растёт. Для решения этой проблемы предлагается в рамках компьютерного моделирования воспроизвести структуру передвижений в городе, для всех или некоторых видов транспорта в течение дня. Это является комплексной задачей, включающей в себя несколько этапов моделирования [2]. В настоящее время в различных пакетах транспортного моделирования (например, [3], разработанный В.И. Швецовым) превалирует многостадийный подход [2], в простейшем случае состоящий из следующих блоков (моделей):

0. Предобработка данных, а именно расчёт объёмов прибытия/отправления из всех районов города и изначальной матрицы транспортных затрат (затраты на перемещение из района г в район ], могут быть временными, расстояния и т.д., в зависимости от задачи). Данные величины являются входными параметрами, т.е. они не моделируются. Как правило, объёмы прибытия и отправления обозначаются как векторы Ьг и Wj, где £ ¿у = Ьг, ^ ¿у = Wj, а матрица затрат

3 (у )еОП Ц^СОБ

как {Ту}(г3)еО£.

1. Расчёт корреспонденций {¿у}(гу)2ов между каждой парой районов г,] из объёмов прибытия/отправления и матрицы затрат {Ту}(г,j)2оD. Таким образом будут смоделированы объёмы передвижения между каждой парой расчётных районов города.

2. Распределение потоков в транспортной сети. Входным параметром в этот блок является матрица корреспонденций {¿у }(гу)2Ов, а в качестве выходных данных будут получены матрица затрат {Ту}(г,3-)2об, кратчайшие пути и количество участников движения на каждом пути.

Как видно из этой схемы, набором входных параметров для последующего блока модели является результаты предыдущего (исключая нулевой шаг предобработки данных). То есть, на практике обычно задаётся изначальная матрица затрат и подсчитываются объёмы прибытия/отправления, на основе которых рассчитывается первая матрица корреспонденций. На основе первой матрицы

корреспонденций моделируется равновесное распределение потоков по путям, новая матрица затрат и кратчайшие пути. На основе новой матрицы затрат пересчитывается матрица корреспонденций и т.д. Как правило, описанная процедура итеративно повторяется до тех пор, пока не будет найдена неподвижная точка1. Этот алгоритм широко используется [3], однако имеет определенные недостатки, указанные, например, в работах [4; 5]. Главными из них является то, что для него не существует известных гарантий сходимости и оценок скорости сходимости. Поэтому был предложен другой подход [4], в котором поиск равновесия в многостадийной модели сводится к задаче выпуклой оптимизации. Теоретические выкладки были получены давно [6; 7], но автору неизвестно о каких-либо экспериментальных результатах (на момент написания диссертации). Сильной стороной этого подхода является гарантия сходимости алгоритма вкупе со значительно меньшим расчётным временем.

Кроме описанных выше проблем классического подхода к многостадийному моделированию транспортных потоков, стоит отметить, что в блоке распределения потоков по путям часто используется модель Бэкмана [8; 9]. Одним из ключевых понятий в этой модели являются функции затрат на рёбрах графа транспортной сети, которые связывают время в пути по ребру с величиной потока по этому же ребру. Как правило, предполагается, что это (строго) возрастающие, гладкие функции от потока по ребру (иногда и выпуклые). Например, общепринятым видом такой функциональной зависимости является так называемая БРЯ-функция (2.2). К сожалению, реальные данные показывают, что модель Бэкмана хорошо описывает только ситуацию относительно свободного движения2. В пробке, когда характеристики потока определяются не плотностью машин, а некоторым «бутылочным горлышком», модель вводит лишь дополнительную задержку, никак не ограничивая пропускную способность дороги и допуская сколь угодно большие интенсивности движения. В более новой модели стабильной динамики [11] случай автомобильных пробок моделируется совершенно иначе: если количество машин достигает или стано-

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

2Например, авторы работы [10] приводят оценку, что модель Бекмана не способна корректно описать характеристики транспортного потока, если его скорость меньше половины скорости движения свободного потока

вится выше пропускной способности дороги, то временные затраты могут быть сколь угодно большими. Тем не менее, была доказана связь между этими двумя подходами для нескольких функций затрат конкретного вида [12], а именно, что стохастический вариант модели стабильной динамики можно получить предельным переходом из модели Бэкмана [13].

Другим вызывающим затруднения местом в многостадийных моделях является подбор структурных параметров. В случае блока восстановления матрицы корреспонденций - это коэффициент у (в некоторых работах в) в энтропийной (или гравитационной) модели при энтропийном слагаемом3. Этот параметр можно интерпретировать как множитель Лагранжа к ограничению на «среднее время в пути» [6]; т.е. в качестве физического смысла величину у можно понимать как обратную к среднему времени в пути. В действительности же от подбора этого коэффициента существенно зависит качество модели.

Поскольку большее количество расчётного времени в многостадийной модели занимает блок равновесного распределения потоков по путям, а в нём в свою очередь алгоритм поиска кратчайший путей, логично было бы попытаться ускорить именно эту часть многостадийной модели. Действительно, после каждой итерации модели Бэкмана или стабильной динамики матрица затрат изменяется совсем немного, а для некоторых рёбер вовсе не меняется, но алгоритм Дейкстры работает каждый раз так, будто предыдущих запусков не было. Алгоритмы, которые обновляют дерево кратчайших путей без полной рекаль-куляции, называются динамическими алгоритмами поиска кратчайшего пути (dynamic shortest-path algorithms) [14].

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

3Стоит отметить, что в разных вариантах модели этот коэффициент может стоять как при линейном слагаемом, так и при энтропийном. Эти варианты равнозначны и сводятся в итоге к одной задаче энтропийно-линейного программирования.

Научная новизна:

1. Был предложен и научно обоснован алгоритм калибровки моделей расчета матрицы корреспонденций. Особенно большое внимание было уделено вычислительным аспектам в этой области.

2. Впервые были проведены численные эксперименты с одномоментной двухстадийной моделью на реальных данных. И хотя ранее теория уже была описана, о практической реализации и численных экспериментах с данным подходом автору неизвестно. Также была проведена работа в области приведения теории к общим обозначениям.

3. Была исчерпывающе обоснована связь между моделью стабильной динамики (или Нестерова-Де Пальмы) и моделью Бэкмана для вырождающихся функций затрат с помощью предельного перехода. Ранее это уже было проделано для некоторых функций конкретного вида, но о полном доказательстве автору неизвестно.

Апробация работы. Основные результаты работы докладывались на конференциях:

1. Международный форум «Kazan Digital Week», 21 - 24 сентября 2021 г., сайт конференции: https://kazandigitalweek.com/ru/site

2. The International Conference «Quasilinear Equations, Inverse Problems and Their Applications», 30 ноября - 2 декабря 2020 г., сайт конференции: https://qipa2020.mipt.ru/home

3. Школа «Современные методы теории информации, оптимизации и управления» в научно-техническом университете «Сириус», 2-23 августа 2020 г., сайт прошедшей школы: https://sochisirius.ru/obuchenie/graduate

4. Международная научно-техническая конференция «Актуальные проблемы прикладной математики, информатики и механики», 11-13 ноября 2019 г., сайт конференции: http://www.amm.vsu.ru/conf/index.php

5. The International Conference «Quasilinear Equations, Inverse Problems and Their Applications», 2-4 декабря 2019 г., сайт конференции: https://qipa2019.mipt.ru/

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

Публикации. Основные результаты по теме диссертации изложены в 4 печатных изданиях, 4 из которых изданы в журналах, рекомендованных ВАК, 4 — в периодических научных журналах, индексируемых Web of Science и Scopus.

Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения и 0 приложен. Полный объём диссертации составляет 76 страниц, включая 14 рисунков и 3 таблицы. Список литературы содержит 62 наименования.

Глава 1. Калибровка энтропийной модели расчёта матрицы

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

1.1 Введение

В первой главе диссертации рассматривается задача расчёта матрицы корреспонденций. Следуя общепринятому подходу [8], транспортная сеть рассматривается как ориентированный граф, дуги которого соответствуют участкам дороги, а вершины графа - районам, в которые въезжают/выезжают участники движения. Число жителей города считается постоянным. Задача восстановления матрицы корреспонденций состоит в расчёте всех корреспонденций из района г в район ].

Для восстановления матрицы предлагается использовать один из наиболее популярных в урбанистике способов расчёта матрицы корреспонценций -энтропийную модель. Наиболее широко в отечественной литературе такие модели разивал Попков Ю. С. Собственно, в диссертации, базируясь на его работе и книге Вильсона А. Дж. [15; 16] описывается основная идея перехода к решению задачи энтропийно-линейного программирования (ЭЛП) при расчёте матрицы корреспонденций, в то время как описание эволюционного обоснования энтропийной модели изложено соответственно статье [17]. Для решения полученной задачи ЭЛП предлагается перейти к двойственной задаче и решать задачу относительно двойственных переменных. В главе описывается два численных метода оптимизации для решения данной задачи: стандартный алгоритм Синхорна и ускоренный. Далее приводятся численные эксперименты для следующих вариантов функций затрат: линейная функция затрат и сумма степенной и логарифмической функции затрат. В данных функциях затраты представляют из себя комбинацию среднего времени в пути и расстояния между районами, которая зависит от параметров. Для каждого набора параметров функции затрат рассчитывается матрица корреспонденций и далее оценивается качество восстановленной матрицы относительно известной матрицы корреспонденций. Предполагая, что шум в восстановленной матрице корреспонденций является гауссовским, в качестве метрики качества выступает среднеквадратичное отклонение. Данная задача представляет из себя задачу

невыпуклой оптимизации, поэтому использовать можно только безградиеные методы. Так как число параметров функции затрат небольшое, для определение оптимальных параметров функции затрат было выбрано использовать метод перебора по сетке значений. Таким образом, для каждого набора параметров рассчитывается матрица корреспонденций и далее оценивается качество восстановленной (рассчитанной) матрицы корреспонденций относительно известной. Далее по минимальному значению невязки для каждой функции затрат определяется для какой функции затрат и при каких значениях параметров восстановленная матрица наилучшим образом описывает реальные корреспонденций.

1.2 Энтропийная модель расчёта матрицы корреспонденций

В данном разделе приведем эволюционное обоснование энтропийной модели согласно статье [17].

Пусть в некотором городе имеется п районов. Общее число жителей города постоянно и равно N, при этом выполняется N ^ п2. Пусть Ьг > 0 это число жителей, выезжающих в типичный день за рассматриваемый промежуток времени из района г, а Wj > 0 число жителей, приезжающих на работу в район ] в типичный день за рассматриваемый промежуток времени. В рамках рассматриваемого подхода данные величины являются входными параметрами для модели, т.е. они не моделируются. При этом будут выполняться следую-

п п

щие соотношения: Ь2 = ^ Wj = N.

2=1 j = 1

Обозначим через (у (£) > 0 - число жителей, живущих в г-м районе и работающих в з-м в момент времени £. Мы предполагаем, что со временем жители могут меняться только квартирами, поэтому во все моменты времени £ > 0 выполнено

п,п п п

(у(£) > 0, X (у(£) = N, X(у(£) = X(у (£) = Wj, = 1,...,п.

¡у=1 у=1 2=1

Определим следующее множество:

( п,п п п \

Я = < > 0 : X ¿3 = N X ¿3 = X ¿3 = ^, = (1-1)

I ¿,3=1 3=1 ¿=1 )

Отметим, что основным стимулом к обмену места жительства для жителя города будут являться транспортные издержки, то есть для каждого жителя работать далеко от дома плохо из-за больших транспортных издержек. Будем считать, что эффективной функцией затрат [8] является функция Я(Т) = ^г, где Т > 0 - затраты на путь от дома до работы, которые определяются как временем так и расстоянием, а у > 0 - настраиваемый параметр модели, который можно интерпретировать как цену единицы затрат на путь от работы до дома. Далее в работе будем подразумевать под функцией затрат только Т(а, в,у), где а, в,У - настраиваемые параметры модели.

Динамику процесса можно описать следующим образом: пусть в момент времени £ > 0 г-й житель живет в к-м районе и работает в т-м, а в-й житель живет в р-м районе и работает в д-м. Тогда Лк,т;р,д(£)Д£ + о(Д£)- есть вероятность того, что жители с номерами г и в (1 6 г < в 6 N "поменяют-ся"квартирами в промежутке времени (£,£ + Д£). Вероятность обмена местами жительства зависит только от мест проживания и работы обменивающихся:

Лк,т;р,ц(£) = Лк,ш;р,^ = ЛN 1 вХЩ Л(Т£ТО) + Я(Трд)

4 4-V-'

суммарные затраты до обмена

(Я(Трт) + Я(Ткч)) ) > 0,

4-V-' у

суммарные затраты после обмена

где коэффициент 0 < Л = 0(1) характеризует интенсивность обменов. Отметим, что совершенно аналогичным образом можно было рассматривать случай, когда жители могут обмениваться местами работы. То есть мы предполагаем некое равноправие агентов (жителей) внутри фиксированной корреспонденций и их независимость [6].

Согласно эргодической теореме для марковских цепей (в независимости от начальной конфигурации {¿¿3 (0)}"*= 1) [8] предельное распределение совпадает со стационарным (инвариантным), которое можно посчитать (получается

проекция прямого произведение распределений Пуассона на Q):

lim P(t) = dij, = 1,...,n) = t!1

n,n

= Z-1 П exp(-2R(Tj)dj) • (dj!)-1 = p({dj JjnjLi.x),

=1,1

где {djj1 2 Q, а «статсумма» Z. Отметим, что начальная конфигурация {dj (0)}П;П=11 влияет на время выхода на стационарное состояние. При этом стационарное распределение p({dj}nj=11) удовлетворяет условию детального равновесия [6]. При N ^ 1 распределение p({dj}П^=1 1) экспоненциально сконцентрировано на множестве Q в O(\/N) окрестности наиболее вероятного значения d* = {d*j}nj'=1 1, которое определяется, как решение задачи энтропийно-линейного программирования (ЭЛП) [8; 18]:

n , n n , n

lnP({dj}njn=1,1 )= mi„ax —Y X dijTij - X dijln dij•

{dij }ij=M2Q i,j=1,1 i,j=1,1

Это следует из теоремы Санова о больших уклонениях для мультиномиального распределения [19].

1.3 Методы решения задачи энтропийно-линейного

программирования

В данном разделе приведем описание способов решения задачи ЭЛП, возникающей при расчёте матрицы корреспонденций.

Как было показано в предыдущем разделе, задачу восстановления матрицы корреспонденций можно записать как следующую задачу оптимизации:

n,n n,n

min f (dij) := у X djTj + X dj ln dj, (1.2)

dij 2Q •■11 -11

где Q определяется как (1.1) и Tj := Tj (ц) - функция затрат на перемещёние из района i в район j, которая зависит от вектора параметров ц.

n,n

Введем следующую нормировку: ^ dj = 1, тогда ограничения можно

=1,1

n n W

переписать в следующем виде ^ dij = 1i и ^ dij = Wj, где 1i = N W = -N .

j=i i=i

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

п,п п п

Я = < ¿¿3 > 0 : X ¿¿3 = 1, X ¿¿3 = X ¿¿3 = ^3, ¿, .7 = 1,-..,п > .

I ¿,3=1 3=1 ¿=1 )

После введения нормировки, получаем, что для задачи (1.2):

п,п п,п

у X N • ¿¿3 Тг3 + X N • ¿¿31п N • ¿¿3 = ¿,3=1,1 ¿,3=1,1

п,п п,п п,п

= Ч

У ^^ ¿¿3 + ^^ ¿¿3 1п ¿¿3

+ X ¿¿31п

¿,3=1,1 ¿,3=1,1 ¿,3=1,1

=1

Тогда задача (1.2) перепишется в следующем эквивалентном виде:

т у ^^ ¿¿3 + ^^ ¿¿3 1п ¿¿3. (1.3)

¿,3=1,1 ¿,3=1,1

Далее введем два блока двойственных переменных Л1 € Кп и Л3 € Кп, где Л1

\1 2 Кп и Л3 € Кп, — л1

пп

множитель к ограничению ^ ¿¿3 = ^ и Л3 множитель к ограничению ^ ¿¿3 =

3=1 ¿=1

и>3. Применим для решения задачи (1.3) метод множителей Лагранжа. Для

этого запишем двойственную задачу:

п,п п,п п,п

т*П У X

¿¿3 Т3 + X ¿¿3 1п ¿¿3 = тах т*п X

¿¿3

+

^265 ¿,3=1,1 ¿,3=1,1 ^ Л" £ а-ц=1,^.5>0 ¿,3=1,1

¿,¿=1,1

п п п п

3 л Л 7 А I \ лЛ3/

+ X ¿¿3 1п ¿¿3 + X ¿¿3 - У + X Л3(X ¿¿3 - ^3)} =

¿,3=1,1 ¿=1 3=1 3=1 ¿=1

п,п

тах{-(Л1,/) - (Л3+ тт{ X ¿¿3 (УТу + 1п¿¿3 + Л¿ + Л3) +

Л1, Л™ ^ >0 ^ . .

¿,3=1,1

п,п

+у X ¿¿3 -1)}} = тах!-(л1 ,/> - (л3,™>+

VI ' -¿3

^ Л1, л™ ^

¿,3=1,1

п,п

+ { X ¿¿3 (Л1, Л3) (УТ,- + 1п ¿¿3 (Л1, Л3) + Л¿ + Л3 + V) - у} },

¿,3=1,1

где

п,п п,п

¿¿3(Л1,Л3) = а^тт{ X ¿¿3 (УТ; + 1п¿¿3 + Л¿ + Л3) + X ¿¿3 - 1)}}-

а >0 ¿,3=1,1 ¿,3=1,1

Используя условия оптимальности, получаем

YTj + ln dij + Ai + AJ + 1 + v = 0, X dij = 1.

Решая данную систему уравнений и переопределяя А1 := —А1 — 2 и Aw := —Aw — 2 получаем, что

d (А1 AW) = exp(—YTij +Ai+AW) = Bj (A',Aw)

(A ,A )= , ™ Л, ЛИЛ = 1TB(A1,Aw)1'

E exp(—YTij +Aj+AJW) V ;

i,j=1,1 j

где Bj(A1, Aw) = exp(—yTj + A- + Aw). Подставляя это в двойственную задачу, получаем, что двойственная задача имеет вид

max '(A1, Aw) := (A1, l) + (Aw,w) — ln (1TB(A1, Aw)1,)

A1, Aw

где под обозначением ln l подразумевается поэлементный логарифм вектора, под 1 2 Rn - единичный вектор, под Tj - затраты на поездку из района i в район j. Перепишем задачу, как задачу минимизации с точностью до знака

min '(A1, Aw) := ln (1TB(A1, Aw)1) — (A1, l) — (Aw,w). (1.4)

Л1, Л'

Для решения двойственной задачи рассмотрим Метод Альтернированной Минимизации (Алгоритм 1). Для удобства описания алгоритма введем следующее обозначение. Множество {1,...,n} векторов 6^=1 ортонормированного базиса разделено на p непересекающихся блоков , k 2 {1 ,..., p}. Пусть (x) = x + span{ei : i 2 }, подпространство, содержащее x построенное на базисных векторах k-го блока.

Алгоритм 1 Метод Альтернированной Минимизации 1: Input: x0 - starting point. 2: for k > 0 do 3: Choose ik 2 1,...,p. 4: Compute xk+1 = argmin f (x).

5: end for 6: Output: xk.

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

задачи (1.4) мы будет рассматривать минимизацию по двум блокам: Л1 и Aw. Согласно Лемме 5 из [20] шаг минимизации по блоку Л1 можно представить в следующем виде

[Л1 ]k+1 = [Л1 ]k + ln(l) - ln (B([Л1 ]k, [Л3]k)1) ,

аналогичным образом можно представить шаг минимизации по блоку Л3:

[Л3]k+1 = [Л3]k + ln(w) - ln (BT([Л1 ]k, [Л3]k)1) .

Учитывая это, для решения (1.4) получаем Алгоритм 2.

Алгоритм 2 Алгоритм Синхорна 1: Input: x0 = [[Л1 ]0, [Л3]0] = (0,..., 0) 2 R2n - starting point. 2: for k > 0 do 3: if k mod 2 = 0 then 4: Compute

[Л1 ]k+1 = [Л1 ]k + ln(l) - ln (B([Л1 ]k, [Л3]k)1) , [Л3 ]k+1 = [Л3 ]k.

5: else

6: Compute

[Л1 ]k+1 = [Л1 ]k,

[Л3]k+1 = [Л3]k + ln(w) - ln (BT([Л1 ]k, [Л3]k)1) .

7: end if 8: end for

9: Output: xk = [[Л1]^, [Л3]к] 2 R2n.

Отметим, что алгоритмом альтернированной минимизации для задачи (1.4) является хорошо известный алгоритм Синхорна [21].

Также для оптимального решения задачи ЭЛП будем рассматривать ускоренный вариант метода Альтернативной Минимизации. Согласно [20], в качестве основы ускоренного метода Альтернативной Минимизации используется традиционный адаптивный ускоренный градиентный метод. Для этой задачи этот вариант метода оказался быстрее на практике, чем другие способы ускорения. Здесь мы не используем одномерную минимизацию, чтобы найти размер

шага, а вместо этого мы адаптируемся к константе Липшица Ь. Анализ скорости сходимости этого алгоритма можно найти в [20]. В нашем случае Ускоренный Метод Альтернативной Минимизации представлен в виде Алгоритма 3.

При этом вектор градиента функции (1.4) представляет из себя вектор Уф(А/, Л«) = [У1ФТ, У2'т]Т, где

^ /л/ л «А , В (А1, л-)1 ^ /л/ Л«А Вт (Л1, Л« )1

У1ф(л1,Л«) = -1 + ^ ' « , У2ф(Л/,Л«) = -ад + ^ ' ;

1ТВ(Л/, Л«)1' ' у 1ТВ(Л/, Л«)1'

1.3.1 Задача подсчёта невязки для восстановленной матрицы

затрат

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

Для постановки задачи подсчёта невязки между бу - исходной матрицей корреспонденций и бу (а) - восстановленной матрицей корреспонденций, предположим, что в восстановленной матрице корреспонденций бу (а) шум является гауссовским (мы восстанавливаем матрицу неточно, с шумом). Тогда восстановленную матрицу можно рассматривать как нормально распределенную выборку N(6, а2), и плотность вероятности нормального распределения можно рассчитать следующим образом:

1 -(х-6)2

р(х) = . -б 2а2 ,

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

Алгоритм 3 Ускоренный алгоритм Синхорна

1: Input: x0 := [[x1 ]0, [xw]0] = (0,..., 0) e R2n - starting point, L0 = 1, «0 = 0.

2: repeat

3: Set y0 := [[y1 ]0, [yw]0] = x0.

4: Set v0 := [[v1 ]0, [vw]0] = x0.

5: Lk+1 = /2

6: while True do

7: Set =2L+1+q+

4L

k+i

Set Tk =

1

afc+iLfc+i

9: Set = Tk+ (1 - Tk)xk

10: Choose ik = argmax ||Vj'(yk)||2

i2{1,2}

11: if ik = 1 then

12: Compute

[x1 ]k+1 = [y1 ]k + ln(l) - ln (B([y1 ]k, [yw]k)1) , [xw ]k+1 = [yw ]k.

13: else

14: Compute

[x1 ]k+1 = [y1 ]k,

[xw]k+1 = [yw]k + ln(w) - ln (BT([y1 ]k, [yw]k)1)

16: Set vk+1 = - ak+1V'(yk)

15: end if

Г1 , V7 /'Г* i n

tM\|2 2Lfc+i

1g: Set ¿k+1 = afc+idk)+Lfca1dk

17: if '(xk+1) 6 '(yk) - "Vff* then

+

Lk+iak+i

19: break

20: end if

21: Set Lk+1 = 2Lk+1.

22: end while

23: until |f(dk+1) + '(xk+1)| 6 "f, ||dk+11 - 11|2 6 "eq, ||(^+У 1 - w||2 6

24: Выход: dk+1, xk+1.

'eq

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

n,n n,n

(«)} = П («))} = П • (*))2/2"2 ! max

= 1 ¿J^1

^ n,n f 1 ^ ^ log L(dj(a)) = X ] - log ^2яа2 - ^ ' (dj - dj(a))2 > ! max

л /> — IV. s

=1

1

2a2

log L(dj(a)) = - lo^ V2^a2 - 2^ • X (dj - d^ij(a))2 ! max

k=i

Изменив знак перед выражением, получаем следующую задачу для подсчёта невязки:

min Y^ (dj - dj(a))

2

in (dj - dj(a))2 или, при нормировке, -——:-2-• (1-5)

^ . n «j=M

Отметим что данная задача является задачей минимизации, которая зависит от параметра а (это может быть вектор параметров, в зависимости от количества параметров в рассматриваемой функции затрат).

Целевая функция полученной задачи является невыпуклой функцией. Для решения данной задачи предлагается использовать безградиентные методы. В частности в рассматриваемой задаче для поиска оптимального параметра (параметров) а в возникающей при подсчёте невязки задаче минимизации, используется метод перебора так как число параметров в зависимости от функции затрат 1 — 3. Однако, в качестве обзора, приведём описание ещё нескольких безградиентных методов для задач невыпуклой оптимизации. Рассмотрим метод имитации отжига, для работы которого не требуется гладкость функции [22]. Он является вариантом метода случайного поиска и известен как алгоритм Метрополиса. Для задач оптимизации имитация процесса может быть произведена следующим образом. Вводится параметр Т, который имеет смысл температуры, и в начальный момент ему устанавливается значение Т0. Набор переменных, по которым происходит оптимизация, будет обозначаться как х. В качестве начального состояния системы выбирается произвольная точка. Далее запускается итерационный процесс — на каждом шаге из множества соседних состояний случайно выбирается новое X. Если значение функции в этой точке

меньше, чем значение в текущей точке, то эта точка выбирается в качестве нового состояния системы. В ином случае (т.е. если f (ж ) > f (ж)) такой переход происходит с вероятностью P, зависящей от температуры T, текущего состояния и кандидата на новое состояние x следующим образом:

„ f (й)-/(x)

P = e T .

Также стоит упомянуть метод ломаных, который применим к классу функций одной переменной, удовлетворяющих условию Липшица [23]. Говорят, что функция f (ж) удовлетворяет условию Липшица, если найдётся такая константа L > 0, что:

I f (ж) - f (У) I6 L| ж - У I 8x,y G [a,b]

Пусть функция f (ж) удовлетворяет условию Липшица на отрезке [a,b]. Зафиксируем какую-либо точку y G [a,b] и определим функцию g(x,y) = f (y) — L^ | ж — y | переменной а 6 ж 6 b. Функция g(x,y) кусочно-линейна на [a, b], и график её представляет ломаную линию, составленную из отрезков двух прямых, имеющих угловые коэффициенты L и —L и пересекающихся в точке (y,f (y)). Также в силу липшицевого условия:

g^y) = f(y) — L| ж — y |6 f(ж,У) 8ж 2 [a,b]

причём g(y,y) = f (y). Из этого следует, что график функции f (ж) лежит выше ломаной д(ж^) при всех ж G [a,b] и имеет с ней общую точку (y,f(y)). Данное свойство ломаной д(ж^) можно использовать для построения метода. Этот метод начинается с выбора произвольной точки жо G [a, b] и составления функции д(ж,ж0) = f (ж0) — L^| ж — ж0 |= р0(ж). Следующая точка ж1 определяется из условий р0(ж1) = minxG[a,b] (р0(ж))(ж1 G [a,b]), причём ж1 = а или ж1 = b. Далее берётся новая функция p1 (ж) = max (д(ж, ж1),р0(ж)), и очередная точка ж2 находится из условий р1(ж2) = minxG[a,b]р1(ж)(ж2 G [a,b]) и т.д. Пусть точки ж 1, ..., (n > 1) уже известны. Тогда составляется функция:

Рп(ж) = max (g(ж,жп),рп_ 1 (ж)) = max д(ж,ж^,

06i6n

и следующая точка жп+1 определяется условиями:

Рп(жп+1) = min рп(ж), жп+1 G [a, b]

ж€[а,6]

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

Также следует упомянуть алгоритм случайного мультистарта [22]. Случайный мультистарт - это метод глобальной оптимизации, состоящий в многократном отыскании локальных минимумов из различных начальных точек. В своем первоначальном виде он неэффективен, однако некоторые из его модификаций могут быть полезны. Основная сложность при практической реализации метода состоит в следующем: для того, чтобы с высокой надёжностью отыскать точку глобального минимума, необходимо взять количество начальных точек для локальных алгоритмов существенно больше, чем число локальных минимумов функции, которое обычно неизвестно.

Список литературы диссертационного исследования кандидат наук Котлярова Екатерина Владимировна, 2022 год

Список литературы

1. Braess, D. Über ein Paradoxon aus der Verkehrsplanung

[Текст] / D. Braess // Unternehmensforschung Operations Research. — 1968. — Т. 12. — С. 258—268.

2. Швецов, В. И. Проблемы моделирования передвижений в транспортных сетях

[Текст] / В. И. Швецов // Труды Московского физико-технического института. — 2010. — Т. 2, 4(8). — С. 169—179.

3. Швецов, В. И. TransNet

[Электронный ресурс] / В. И. Швецов, А. С. Алиев. — ÜRL: http://www. isa.ru/transnet/ (дата обр. 09.07.2022).

4. Гасников, А. В. Эффективные численные методы поиска равновесий в больших транспортных сетях

[Текст] : дис. ... канд. / Гасников А. В. — 141700, Московская обл., г. Долгопрудный, Институтский пер., д. 9 : Московский физико-технический институт (государственный университет), 12.2016. — Диссертация на соискание степени д.ф.-м.н. по специальности 05.13.18-Математическое моделирование, численные методы, комплексы программ.

5. Ortuzar, J. D. Modelling transport

[Текст] / J. D. Ortuzar, L. G. Willumsen. — West Sussex, England : John Wiley & Sons Ltd, 2002. — 608 p.

6. О трехстадийной версии модели стационарной динамики транспортных потоков

[Текст] / А. В. Гасников [и др.] // Математическое моделирование. — 2014. — Т. 26, № 6. — С. 34—70.

7. Двухстадийная модель равновесного распределения транспортных потоков

[Текст] / Т. С. Бабичева [и др.] // Труды Московского физико-технического института. — 2015. — Т. 7, 3(27). — С. 31—34.

8. Введение в математическое моделирование транспортных потоков. Под ред. А.В. Гасникова с приложениями М.Л. Бланка, К.В. Воронцова и Ю.В. Чеховича, Е.В. Гасниковой, А.А. Замятина и В.А. Малышева, А.В. Колесникова, Ю.Е. Нестерова и С.В. Шпирко, А.М. Райгородского, с

предисловием руководителя департамента транспорта г. Москвы М.С. Лик-сутова

[Текст] / А. В. Гасников [и др.]. - М. : МЦНМО, 2013. - 427 с. - 2-е изд.

9. Beckmann, M. Studies in the economics of transportation

[Текст] / M. Beckmann, C. B. McGuire, C. B. Winsten. — Santa Monica : RAND Corporation, 1955. — 249 p.

10. Manzo, S. Effects of Uncertainty in Speed-Flow Curve Parameters on a Large-Scale Model Case Study of the Danish National Model

[Текст] / S. Manzo, A. O. Nielsen, C. G. Prato // Transportation Research Record. — 2014. — Vol. 2429, no. 1. — P. 30—37.

11. Nesterov, Y. Stationary dynamic solutions in congested transportation Networks: Summary and Perspectives

[Текст] / Y. Nesterov, A. Nemirovski // Networks Spatial Econ. — 2003. — Vol. 3, no. 3. — P. 371—395.

12. Гасников, А. В. Модели равновесного распределения потоков в больших сетях

[Текст] / А. В. Гасников, Е. В. Гасникова. - М. : МФТИ, 2013. - 204 с.

13. Обоснование связи модели Бэкмана с вырождающимися функциями затрат с моделью стабильной динамики

[Текст] / Е. В. Котлярова [и др.] // Компьютерные исследования и моделирование. - 2022. - Т. 14, № 2. - С. 335-342.

14. Bauer, R. Batch dynamic single-source shortest-path algorithms: an experimental study

[Текст] / R. Bauer, D. Wagner // 8th Int. Symp. on Experimental Algorithms (SEA '09). — 2009. — Vol. 5526. — P. 51—62.

15. Вильсон, А. Д. Энтропийные методы моделирования сложных систем [Текст] / А. Д. Вильсон. - М. : Наука, 1978. - 248 с.

16. Попков, Ю. С. Теория макросистем: Равновесные модели

[Текст] / Ю. С. Попков. - М. : Книжный дом «ЛИБРОКОМ», 2013. -320 с.

17. Эволюционные выводы энтропийной модели расчета матрицы корреспон-денций

[Текст] / А. В. Гасников [и др.] // Математическое моделирование. -2016. - Т. 28, № 4. - С. 111-124.

18. Малышев, В. А. Обратимость и необратимость в стохастической химической кинетике

[Текст] / В. А. Малышев, С. А. Пирогов // Успехи математических наук. — 2008. — Т. 63, 1(379). — С. 3—36.

19. Санов, И. Н. О вероятности больших отклонений случайных величин [Текст] / И. Н. Санов // Математический сборник. — 1957. — Т. 42, № 1. — С. 11—44.

20. Accelerated alternating minimization, accelerated Sinkhorn's algorithm and accelerated iterative Bregman projections

[Электронный ресурс] / S. Guminov [et al.]. — URL: https://arxiv.org/abs/ 1906.03622 (visited on 07/09/2022).

21. Cuturi, M. Sinkhorn distances: Lightspeed computation of optimal transport [Текст] / M. Cuturi // Advances in neural information processing systems. — 2013. — Vol. 26. — P. 2292—2300.

22. Zhigljavsky, A. Stochastic global optimization

[Текст] / A. Zhigljavsky, A. Zilinskas. — New York : Springer, 2007. — 272 p.

23. Васильев, Ф. П. Методы оптимизации

[Текст] / Ф. П. Васильев. — М. : Факториал Пресс, 2002. — 820 с.

24. Patriksson, M. The traffic assignment problem: models and methods [Текст] / M. Patriksson. — Utrecht, The Netherlands : VSP Publishers, 1994. — 240 p.

25. Research Core Team, T. N. for. Transportation Networks for Research. [Электронный ресурс] / T. N. for Research Core Team. — URL: https: //github.com/bstabler/TransportationNetworks (visited on 07/09/2022).

26. Гасников, А. В. Численные методы поиска равновесного распределения потоков в модели Бэкмана и в модели стабильной динамики

[Текст] / А. В. Гасников, Ю. В. Максимов, Ю. В. Дорн // Математическое моделирование. — 2016. — Т. 28, № 10. — С. 40—64.

27. Gasnikov, A. V. Dual methods for finding equilibriums in mixed models of flow distribution in large transportation networks

[Текст] / A. V. Gasnikov, E. V. Gasnikova, Y. Nesterov // Computational Mathematics and Mathematical Physics. — 2018. — Vol. 58. — P. 1395—1403.

28. Kubentayeva, M. Kubentayeva M. TransportNet.

[Электронный ресурс] / M. Kubentayeva. — URL: https://github.com/ MeruzaKub/TransportNe (visited on 02/16/2021).

29. Гасников, А. В. Поиск стохастических равновесий в транспортных сетях с помощью универсального прямо-двойственного градиентного метода [Текст] / А. В. Гасников, М. Б. Кубентаева // Компьютерные исследования и моделирование. - 2018. - Т. 10, № 3. - С. 335-345.

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

[Текст] / Д. Р. Баймурзина [и др.] // Журнал вычислительной математики и математической физики. — 2019. — Т. 59, № 1. — С. 21-36.

31. Kubentayeva, M. Finding equilibria in the traffic assignment problem with primal-dual gradient methods for Stable Dynamics model and Beckmann model [Электронный ресурс] / M. Kubentayeva, A. Gasnikov. — URL: https: //arxiv.org/abs/2008.02418 (visited on 08/21/2022).

32. Васин, А. А. Эволюционные и повторяющиеся игры [Текст] / А. А. Васин. - М. : РЭШ, 2005. - 74 с.

33. Поиск стохастических равновесий в транспортных моделях равновесного распределения потоков

[Текст] / А. В. Гасников [и др.] // Труды Московского физико-технического института. - 2015. - Т. 7, 4(28). - С. 114-128.

34. О связи моделей дискретного выбора с разномасштабными по времени популяционными играми загрузок

[Текст] / А. В. Гасников [и др.] // Труды Московского физико-технического института. - 2015. - Т. 7, 4(28). - С. 129-142.

35. Bertsekas, D. P. Convex optimization theory

[Текст] / D. P. Bertsekas. — Belmont : Athena Scientific, 2009. — 257 p.

36. Гасников, А. В. Современные численные методы оптимизации. Метод универсального градиентного спуска

[Текст] / А. В. Гасников. - М. : МЦНМО, 2021. - 272 с.

37. Sandholm, W. Population games and evolutionary dynamics [Текст] / W. Sandholm. — Cambridge : MIT press, 2010. — 616 p.

38. Primal-dual method for searching equilibrium in hierarchical congestion population games

[Электронный ресурс] / P. Dvurechensky [et al.]. — URL: https://arxiv. org/abs/1606.08988 (visited on 07/09/2022).

39. Ускоренный метаалгоритм для задач выпуклой оптимизации

[Текст] / А. В. Гасников [и др.] // Журнал вычислительной математики и математической физики. — 2021. — Т. 61, № 1. — С. 20—31.

40. Поиск равновесий в многостадийных транспортных моделях

[Текст] / А. В. Гасников [и др.] // Труды Московского физико-технического института. — 2015. — Т. 7, 4(28). — С. 143—155.

41. Об эффективных численных методах решения задач энтропийно-линейного программирования

[Текст] / А. В. Гасников [и др.] // Журнал вычислительной математики и математической физики. — 2016. — Т. 56, № 4. — С. 523—534.

42. A stable alternative to Sinkhorn's algorithm for regularized optimal transport [Текст] / P. Dvurechensky [et al.] //. — International Conference on Mathematical Optimization Theory, Operations Research. Cham : Springer, 2020. — P. 406—423.

43. Гасников, А. В. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях //Математическое моделирование [Текст] / А. В. Гасников // Математическое моделирование. — 2015. — Т. 27, № 12. — С. 121—136.

44. Dvurechensky, P. Computational optimal transport: Complexity by accelerated gradient descent is better than by Sinkhorn's algorithm [Электронный ресурс] / P. Dvurechensky, A. Gasnikov, A. Kroshnin. — URL: https://arxiv.org/abs/1802.04367 (visited on 08/21/2022).

45. Peyre, G. Computational Optimal Transport: With Applications to Data Science

[Текст] / G. Peyre, M. Cuturi // Foundations and Trends® in Machine Learning. — 2019. — Т. 11, № 5/6. — С. 355—607.

46. Gradient methods for problems with inexact model of the objective

[Текст] / F. Stonyakin [et al.] //. — International Conference on Mathematical Optimization Theory, Operations Research. Cham : Springer, 2019. — P. 97—114.

47. Strongly convex optimization for the dual formulation of optimal transport [Текст] / N. Tupitsa [et al.] //. — International Conference on Mathematical Optimization Theory, Operations Research. Cham : Springer, 2020. — P. 192—204.

48. Nesterov, Y. Universal gradient methods for convex optimization problems [Текст] / Y. Nesterov // Mathematical Programming. — 2015. — Т. 152, № 1/ 2. — С. 381—404.

49. Kamzolov, D. Universal intermediate gradient method for convex problems with inexact oracle

[Текст] / D. Kamzolov, P. Dvurechensky, A. Gasnikov // Optimization Methods and Software. — 2020. — Т. 36, № 6. — С. 1289—1316.

50. Primal-dual accelerated gradient methods with small-dimensional relaxation oracle

[Текст] / Y. Nesterov [и др.] // Optimization Methods and Software. — 2021. — Т. 36, № 4. — С. 773—810.

51. On the Complexity of Approximating Wasserstein Barycenters

[Текст] / A. Kroshnin [и др.] // Proceedings of the 36th International Conference on Machine Learning. Т. 97. — International conference on machine learning. PMLR, 2019. — С. 3530—3540. — (Proceedings of Machine Learning Research).

52. Гасников, А. В. Универсальный метод для задач стохастической композитной оптимизации

[Текст] / А. В. Гасников, Ю. Е. Нестеров // Журнал вычислительной математики и математической физики. — 2018. — Т. 58, № 1. — С. 51—68.

53. Sioux Falls

[Электронный ресурс]. —URL: https://en.wikipedia.org/wiki/Sioux_Falls, _South_Dakota (visited on 02/16/2021).

54. Kotliarova, E. V. Kotliarova-Yarmoshik

[Электронный ресурс] / E. V. Kotliarova, D. V. Yarmoshik. — URL: https: //github.com/tamamolis/TransportNet (visited on 02/16/2021).

55. Министерство труда и социальной политики Приморского края [Электронный ресурс]. — URL: https://soctrud.primorsky.ru/employer/ (дата обр. 16.02.2021) ; Реестр работодателей // Интерактивный портал Министерства труда и социальной политики Приморского края.

56. ДаДата

[Электронный ресурс]. — URL: https://dadata.ru/api/geocode/ (дата обр. 16.02.2021).

57. On a Combination of Alternating Minimization and Nesterov's Momentum [Текст] / S. Guminov [et al.] // Proceedings of the 38th International Conference on Machine Learning. — 2021. — Vol. 139. — P. 3886—3898.

58. Nesterov, Y. A method of solving a convex programming problem with convergence rate o(1/k2)

[Текст] / Y. Nesterov // Soviet Mathematics Doklady. — 1983. — Т. 27, № 2. — С. 372—376.

59. Ускорение работы двухстадийной модели равновесного распределения потоков по сети

[Текст] / Е. В. Котлярова [и др.] // Компьютерные исследования и моделирование. — 2022. — Т. 14, № 2. — С. 343—355.

60. Dijkstra, E. W. A note on two problems in connexion with graphs

[Текст] / E. W. Dijkstra // Numerische mathematik. — 1959. — Vol. 1, no. 1. — P. 269—271.

61. Peixoto, T. P. The graph-tool python library

[Текст] / T. P. Peixoto // figshare. — 2014. — URL: http://figshare.com/ articles/graph_tool/1164194 (дата обр. 22.08.2022).

62. Чеканов М.

[Электронный ресурс]. — URL: https : / / github . com / AlonsoQuijano / TransportNet-1/tree/tax_integration (дата обр. 12.01.2022).

Список рисунков

1.1 Разбиение г.Москвы и МО по районам ................. 21

1.2 Значение невязки (1.5) при функции затрат Tj(а) = а • timej в зависимости от alpha........................... 22

1.3 Оптимальное значение невязки в зависимости от у при функции затрат Tj(а,у) = а • time-........................ 23

1.4 Изменение невязки от в при функции затрат

Tj(а, в,У) = а • timej • dist j, где а* = 26.76 и у* = 0.09....... 24

1.5 Сравнение оптимальная невязок при функциях затрат

Tj(а, в,у) = а• time - • distj и Tj(а,у) = а• timej в зависимости от у 25

1.6 Невязка в зависимости от в при функции затрат

Tj(а,у, в) = а • timej — в lntimej при оптимальных (а,у)..... 26

2.1 Иллюстрация примера элементарного графа города с двумя

районами. Стрелки обозначают ориентацию рёбер графа, тогда как разные цвета соответствуют разным транспортным потокам: потоки s12 и s21 - голубые, потоки I12 и l21 - красные, потоки по кольцевым дорогам отмечены прерывистыми чёрными линиями. . . 39

2.2 Схема, иллюстрирующая разность между «традиционной» двухстадийной моделью (слева) и предложенным подходом (справа), в котором всё сводится к единой задачи оптимизации. Отличие состоит в том, что в первом варианте двухстадийной модели блоки двигаются друг за другом итеративно, по кругу. Во втором варианте модели «вложены» одна в другую, т.е. энтропийная модель расчёта матрицы корреспонденций - это внешний цикл, а модель равновесного распределения потоков по путям - это внутренний. Таким образом, на каждую итерацию

модели равновесного распределения потоков приходится один

расчёт обновлённой матрицы корреспонденций............. 43

2.3 Результаты вычислительного эксперимента по предложенному новому подходу для города Су Фолс. По оси абсцисс указаны итерации, по оси ординат величина, оценивающая «зазор двойственности» Д(гкБк) = тах^ВкП аст а*(Г Г(гк),гк - г)...... 48

2.4 Транспортная сеть Владивостока. Серые линии — сетка разбиения на районы. Заполненные цветом круги — предприятия, где радиус соответствует логарифму числа рабочих мест, а цвет — принадлежности району.......................... 49

3.1 Сравнительный анализ разных вариантов алгоритма: «базовый» алгоритм Синхорна (8КНОКК-БЛ8Е), ускоренный градиентный метод (ЛСМ-КОКРЭ), адаптивный ускоренный алгоритм с одномерным поиском (ЛЛМ-КОКРЭ), две ускоренные вариации с добавлением тавтологического ограничения и сдвигом на единичный вектор ^КНОИ^-ТЛИТ, 8КНОКК-ТЛиТ-8Н1РТ). По оси абсцисс время в секундах, по оси ординат критерий зазора двойственности по переменной £...................... 54

3.2 Сравнительный анализ разных вариантов алгоритма: «базовый» алгоритм Синхорна (8КНОКК-БЛ8Е), ускоренный градиентный метод (ЛСМ-КОКРЭ), адаптивный ускоренный алгоритм с одномерным поиском (ЛЛМ-КОКРЭ), две ускоренные вариации с добавлением тавтологического ограничения и сдвигом на единичный вектор (8КНОИК-ТЛИТ, 8КНОКК-ТЛИТ-8Н1РТ). По оси абсцисс время в секундах, по оси ординат критерий нормы невязки ограничений по переменной £................... 55

3.3 Для проверки работоспособности алгоритма T-SWSF было решено «встроить» его в модель стабильной динамики и сравнить с работой «стандартного» алгоритма Дейкстры. В качестве солверов использовались алгоритмы UMST и UGM (универсальных подобных треугольников и универсального градиентного спуска соответственно). В качестве времени сравнивалось время, необходимое модели стабильной динамики для выхода на плато сходимости. Суффикс -dijkstra означает, что для расчёта кратчайших путей использовался алгоритм Дейкстры. Суффикс -t-swsf означает, что использовался T-SWSF алгоритм. В свою очередь суффикс -tradeoff означает, что алгоритмы Дийкстры использовался, если r > r* и T-SWSF, если r 6 r*, , где r* = 20 (т.е. если количество возмущённых рёбер невелико или велико соответственно). Численные эксперименты показали, что T-SWSF может уменьшить расчётное время в случае, если количество возмущённых рёбер на графе относительно невелико.......... 59

3.4 Транспортная сеть города Су-Фоллс до введения «налогов» (слева) и после (справа). Красный цвет показывает показывает соотношение рассчитанных потоков fe к максимальной пропускной способности ребра fe. Как видно из рисунка, после введения «налогов» загрузка потоками на некоторых рёбрах графа существенно снизились........................... 62

Список таблиц

1 Сравнение невязок для разных функций затрат............ 23

2 Сравнение невязок для разных функций затрат............. 26

3 Сравнительное время работы алгоритма Дейкстры (в секундах), реализованного с помощью языка программирования Со и с помощью библиотеки СгарЬТоо1. Сравнение проводилось для модели Бэкмана, засекалось время необходимое для 100 итераций алгоритма Франка-Вульфа......................... 60