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