URSS.ru Магазин научной книги
Обложка Гасников А.В., Гасникова Е.В. Модели равновесного распределения транспортных потоков в больших сетях Обложка Гасников А.В., Гасникова Е.В. Модели равновесного распределения транспортных потоков в больших сетях
Id: 296500
869 р.

Модели равновесного распределения транспортных потоков в больших сетях № 5. Изд. 2

URSS. 2023. 240 с. ISBN 978-5-9710-4380-5.
Белая офсетная бумага
Редакционный совет серии «Учебник школы прикладной математики и информатики МФТИ»: проф. А.М. Райгородский (председатель совета); проф. РАН К.В. Воронцов; проф. А.В. Гасников; проф. Г.Е. Иванов; чл-корр. РАН И.Б. Петров; проф. В.В. Стрижов; академик РАН А.А. Шананин

Предисловие к серии А.М. Райгородского

Аннотация

Учебное пособие основано на семестровом курсе лекций, читаемых студентам шестого курса физтех-школы прикладной математики и информатики для ФУПМ МФТИ и пятого курса физтех-школы аэрокосмических технологий для ФАКИ МФТИ с 2008 года. Пособие посвящено моделям равновесного распределения транспортных потоков по путям и их многостадийным вариантам.

В первой главе описываются элементы теории популяционных игр загрузки (потенциальных игр) на... (Подробнее)


Оглавление
top
Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ» (А. М. Райгородский)6
Введение8
Актуальность8
Цели и задачи10
Методы исследования11
Общие замечания12
Глава 1. Эволюционный вывод равновесных моделей распределения транспортных потоков в больших сетях13
1.1. Трехстадийная модель равновесного распределения транспортных потоков13
1.1.1. Введение13
1.1.2. Структура раздела и предварительные сведения16
1.1.3. Энтропийная модель расчета матрицы корреспонденций19
1.1.4. Модель равновесного распределения потоков Бэкмана28
1.1.5. Краткий обзор подходов к построению многостадийных моделей транспортных потоков с моделью типа Бэкмана в качестве модели равновесного распределения потоков40
1.1.6. Модель стабильной динамики49
1.1.7. Связь модели стабильной динамики с моделью Бэкмана55
1.1.8. Учет расщепления потоков по способам передвижений61
1.1.9. Трехстадийная модель стабильной динамики64
1.1.10. Стохастический вариант трехстадийной модели стабильной динамики65
1.1.11. Калибровка модели стабильной динамики67
1.2. Эволюционные выводы энтропийной модели расчета матрицы корреспонденций69
1.2.1. Введение69
1.2.2. Вывод на основе обменов71
1.2.3. Вывод на основе модели равновесного распределения потоков81
1.3. Об эффективной вычислимости конкурентных равновесий в транспортно-экономических моделях86
1.3.1. Введение86
1.3.2. Равновесное распределение потоков по путям89
1.3.3. Равновесный расчет матрицы корреспонденций93
1.3.4. Сетевая модель алгоритмического рыночного поведения98
1.3.5. Общее конкурентное равновесие102
1.4. О связи моделей дискретного выбора с разномасштабными по времени популяционными играми загрузок106
1.4.1. Введение106
1.4.2. Постановка задачи107
1.4.3. Двойственная задача115
Глава 2. Численные методы поиска равновесий в моделях распределения транспортных потоков в больших сетях123
2.1. Неускоренные численные методы поиска равновесного распределения транспортных потоков в модели Бэкмана и модели стабильной динамики123
2.1.1. Введение123
2.1.2. Метод Франка—Вульфа поиска равновесия в модели Бэкмана125
2.1.3. Поиск равновесия в модели стабильной динамики (Нестерова—де Пальма) и смешанной модели с помощью двойственного субградиентного метода133
2.2. Универсальный ускоренный метод поиска равновесий и стохастических равновесий в транспортных сетях145
2.2.1. Введение145
2.2.2. Экстремальные (вариационные) принципы для поиска равновесий в транспортных сетях146
2.2.3. Переход к двойственной задаче149
2.2.4. Универсальный метод подобных треугольников152
2.2.5. Приложение УМПТ к поиску равновесий в транспортных сетях154
2.2.6. Вычисление (суб-)градиентов в задаче поиска равновесий в транспортных сетях159
2.2.7. Сопоставление оценок, численные эксперименты164
2.3. Поиск равновесий в многостадийных транспортных моделях168
2.3.1. Введение168
2.3.2. Универсальный градиентный метод с неточным оракулом170
2.3.3. Заключительные замечания184
Приложение 1. Теория макросистем с точки зрения стохастической химической кинетики186
1.1. Введение186
1.2. Примеры макросистем187
1.3. Изучение динамики макросистемы с точки зрения стохастической химической кинетики191
Приложение 2. Эволюционный вывод простейшей модели бимодального расщепления спроса на городские передвижения196
2.1. Введение196
2.2. Простейшая эволюционная модель расщепления197
2.3. Численные эксперименты201
2.4. Закон Ципфа—Парето и процесс Юла202
Приложение 3. Универсальный метод подобных треугольников для задач стохастической композитной оптимизации204
3.1. Введение204
3.2. Метод подобных треугольников для задач композитной оптимизации204
3.3. Метод подобных треугольников для сильно выпуклых задач композитной оптимизации210
3.4. Универсальный метод подобных треугольников217
Литература225

Предисловие к серии «Учебник Школы прикладной математики и информатики МФТИ»
top

Физтех-школа прикладной математики и информатики (ФПМИ) — это активно развивающееся подразделение МФТИ, возникшее в результате успешного объединения двух факультетов — факультета управления и прикладной математики и факультета инноваций и высоких технологий.

Сейчас ФПМИ занимает лидерские позиции в России и в мире, давая своим студентам как традиционно мощное физтеховское фундаментальное образование, так и столь же традиционные для МФТИ выходы на самые современные прикладные задачи, возникающие в высокотехнологичной индустрии.

Разумеется, ФПМИ старается быть открытой всем. Например, в интернет-проекте «Лекторий ФПМИ» выложены записи многих лекций, читаемых в нашей Школе. В 2017 году был создан региональный научно-образовательный «Кавказский математический центр» в Майкопе, который получает постоянную поддержку от ФПМИ. А в 2021 году аналогичный проект стартовал в Пскове.

И это только начало! Мы мотивируем наших лучших студентов хотя бы на время возвращаться в регионы, в олимпиадное, кружковое и проектное движение для поддержки высокого уровня этого движения во всей нашей стране. Мы с удовольствием делимся с региональными вузами нашими программами в рамках сетевых образовательных проектов, инициируемых Физтехом и призванных помогать регионам удерживать у себя достаточно сильных абитуриентов.

И, конечно, мы очень рады представить наше новое начинание — «Учебник Школы прикладной математики и информатики МФТИ». В серии книг наши ведущие специалисты поделятся своими знаниями и методическими наработками со студентами, аспирантами, учеными, педагогами и просто со всеми, кто любит математику и ее приложения, хочет оказаться на гребне знаний и увидеть далекую перспективу. Как я часто говорю в своих выступлениях: «Присоединяйтесь к нам!»

А. М. Райгородский,

директор Школы прикладной математики и информатики МФТИ,

заведующий кафедрой дискретной математики,

профессор, доктор физико-математических наук


Введение
top
Актуальность

Настоящее пособие посвящено разработке новых подходов к построению многостадийных моделей транспортных потоков и эффективных численных методов поиска равновесий в таких моделях. Начиная с 50-х годов XX века вопросам поиска равновесий в транспортных сетях стали уделять большое внимание в связи с ростом городов и необходимостью соответствующего транспортного планирования. В 1955 г. появилась первая модель равновесного распределения потоков по путям: BMW-модель, также называемая моделью Бэкмана [75]. В этой модели при заданных корреспонденциях (потоках из источников в стоки) решалась задача поиска равновесного распределения этих корреспонденций по путям, исходя из принципа Вардропа, т. е. исходя из предположения о том, что каждый пользователь транспортной сети рационален и выбирает кратчайший маршрут следования. Таким образом, поиск равновесия в такой модели сводился к поиску равновесия Нэша в популяционной игре [145] (популяций столько, сколько корреспонденций). Поскольку в модели предполагалось, что время прохождения ребра есть функция от величины потока только по этому ребру, то получившаяся игра была игрой загрузки, следовательно, потенциальной. Последнее означает, что поиск равновесия сводится к решению задачи оптимизации. Получившуюся задачу выпуклой оптимизации решали с помощью метода условного градиента [99]. Описанная модель и численный метод и по настоящее время используются в подавляющем большинстве продуктов транспортного моделирования для описания блока равновесного распределения потоков по путям [61, 140, 142, 148]. Однако в работе [133] было указано на ряд существенных недостатков модели Бэкмана и предложена альтернативная модель, которую авторы назвали моделью стабильной динамики.

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

К сожалению, при этом в энтропийную модель явным образом входит информация о матрице затрат на кратчайших путях по всевозможным парам районов. Возникает «порочный круг»: чтобы посчитать эту матрицу затрат, нужно сначала найти равновесное распределение потоков по путям, а чтобы найти последнее, необходимо знать матрицу корреспонденций, которая рассчитывается по матрице затрат. На практике отмеченную проблему решали методом простых итераций. Как-то «разумно» задавали начальную матрицу корреспонденций, по ней считали распределение потоков по путям, по этому распределению считали матрицу затрат, на основе которой пересчитывали матрицу корреспонденций, и процесс повторялся. Повторялся он до тех пор, пока не выполнялся критерий останова. К сожалению, до сих пор для описанной процедуры неизвестно никаких гарантий ее сходимости и тем более оценок скорости сходимости [140].

Описанный выше подход можно назвать двухстадийной моделью транспортных потоков, потому что модель состоит из прогонки двух разных блоков. В действительности, в реальных приложениях, число блоков обычно равно трем-четырем [140]. В частности, как правило, всегда включают блок расщепления потоков по типу передвижения (например, личный и общественный транспорт) — этот блок описывается моделью, аналогичной модели Бэкмана. В математическом плане это уточнение несущественно. Все основные имеющиеся тут сложности хорошо демонстрирует уже двухстадийная модель. Отметим также, что часто в приложениях вместо модели Бэкмана используется её «энтропийно-регуляризованный» вариант, который отражает ограниченную рациональность пользователей транспортной сети [70, 145, 148]. Равновесие в такой модели часто называют стохастическим равновесием.

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

Цели и задачи

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

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

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

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

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

Методы исследования

В основе предложенного в пособии эволюционного формализма обоснования многостадийной транспортной модели лежит часто используемая в популяционной теории игр марковская logit-динамика, отражающая ограниченную рациональность агентов (водителей) [145]. Новым элементом является понимание этой динамики как модели стохастической химической кинетики с унарными реакциями и рассмотрение сразу нескольких разных типов таких унарных реакций, происходящих с разной (по порядку величины) интенсивностью и отвечающих разномасштабным процессам, протекающим в транспортной системе. Например, для двухстадийной модели динамика, отвечающая формированию корреспонденций, идет, по терминологии А. Н. Тихонова, в медленном времени (годы), а динамика, отвечающая распределению потоков по путям, — в быстром времени (дни). Тогда с некоторыми оговорками функционал в вариационном принципе с точностью до множителя и аддитивной константы можно, с одной стороны, понимать как функционал Санова (действие), отвечающий за концентрацию стационарной (инвариантной) меры введенной марковской динамики, а с другой — как функционал Ляпунова—Больцмана для кинетической динамики, полученной при (каноническом) скейлинге (по числу агентов) введённой марковской динамики.

Общие замечания

Наш интерес к данной проблематике был инициирован общением с А. А. Шананиным, Ю. С. Попковым, Е. А. Нурминским и Ю. Е. Нестеровым. Данное пособие было написано в промежутке 2010–2016 гг. Однако мы не спешили с его публикацией, поскольку хотели убедиться, что полученные результаты пройдут некоторую апробацию. Результаты, собранные в разделе 2.2 гл. 2, отражают то новое, что было сделано с 2016 года. Отметим также, что в данном пособии, написанном в основном по статьям авторов, были исправлены различные опечатки, которые удавалось обнаруживать в опубликованных статьях.

Для лучшего понимания второй главы пособия рекомендуется предварительно ознакомиться с пособием [21].


Об авторах
top
photoГасников Александр Владимирович
Доктор физико-математических наук. С 2005 г. работает на кафедре математических основ управления Московского физико-технического института (МФТИ). С 2022 г. — заведующий кафедрой. Также с 2022 года возглавил лабораторию Математических методов оптимизации школы ПМИ МФТИ. В 2007 г. под руководством академика РАН А. А. Шананина защитил кандидатскую диссертацию, в которой было получено решение задачи И. М. Гельфанда о распаде разрыва для уравнения типа Бюргерса. С 2008 г. ведет курс в МФТИ «Математическое моделирование транспортных потоков». В 2013 г. выпустил книгу «Введение в математическое моделирование транспортных потоков», предисловие к которой написал руководитель департамента транспорта г. Москвы М. С. Ликсутов. В 2016 г. защитил докторскую диссертацию, в которой (на основе совместных работ с Ю. Е. Нестеровым) был предложен новый способ формализации задач поиска равновесий в многостадийных моделях транспортных потоков и эффективные численные методы решения таких задач. В 2019 г. получил награду от компании «Yahoo!». В 2020 г. получил премию им. Ильи Сегаловича и премию правительства Москвы по направлению «математика». Автор более 200 статей, в том числе более 90 статей за последние 5 лет, индексируемых в Scopus.
photoГасникова Евгения Владимировна
Кандидат физико-математических наук, старший научный сотрудник в Московском физико-техническом институте (МФТИ), кафедра Математических основ управления. Окончила факультет управления прикладной математикой МФТИ. В 2012 г. защитила кандидатскую диссертацию по теме «Моделирование динамики макросистем на основе концепции равновесия» под руководством И. С. Меньшикова. Автор более 30 научных работ.