Участники программы «Большие вызовы» выпустили научную публикацию по итогам проекта «Усовершенствование модели транспортной сети». Над этим кейсом школьники трудились в июле 2023 года по заданию от Московского физико-технического института. Глобально работа в этом направлении ведется математиками, чтобы улучшить транспортную инфраструктуру городов. Перед ребятами стояла задача – исследовать и сравнить несколько новых алгоритмов оптимизации, которые потенциально можно применить при планировании и совершенствовании дорожных развязок, и в целом просчитать как можно больше вариантов развития транспортной инфраструктуры. Проект был реализован на стыке машинного обучения, численных методов оптимизации и математического моделирования.
Чтобы усовершенствовать транспортную инфраструктуру, например, расширить дорогу, построить новую, изменить расписание общественного транспорта или реализовать другие проекты, необходимо провести тщательные расчеты. Проектировщики должны понимать, как перемещения жителей городов распределены по транспортной сети. Благодаря этому можно рассчитать, сколько времени в пробках тратят автомобилисты. А зная потери, можно определить участки транспортной сети, где необходимы новые дороги и развязки. Для этих целей инженеры и математики применяют транспортные пакеты – специальные программы, позволяющие проводить расчеты.
В прошлые годы, как правило, применялись иностранные транспортные пакеты, но постепенно их методики устарели. Сегодня актуальна разработка собственных транспортных пакетов. Для этого исследуются новые алгоритмы.
Раньше чаще всего применялись пакеты транспортного моделирования с двумя или большим числом оптимизационных блоков. С одной стороны, анализировалась матрица корреспонденции – сколько и между какими районами преимущественно перемещаются жители города. Также анализировалось равновесное распределение потоков по путям. Эти блоки взаимосвязаны, и необходимо было найти параметры состояния равновесия транспортной модели. На практике для поиска равновесия эти блоки последовательно прогоняли друг за другом. Однако гарантий того, что такая процедура будет сходиться к неподвижной точке, нет.
В рамках задачи на программе «Большие вызовы» ребята протестировали несколько алгоритмов на модельной задаче. Для эксперимента была использована транспортная инфраструктура городов Су-Фолс и Анахайм.
«Данные о транспортной инфраструктуре этих городов есть в открытых источниках. Нам предстояло собрать их воедино: изучить особенности транспортных развязок, количество населения и рабочих мест в каждом районе, характеристики дорог, их вместимость, количество полос и многое другое. На этих данных были проведены вычислительные эксперименты и количественная оценка качества сходимости модели, что позволило сравнить наши алгоритмы с существующими. В общей сложности мы реализовали и сравнили три разных алгоритма: универсальный адаптивный градиентный метод, включающий ускорение Нестерова, USTM + Синхорн, ускоренный блочно-покомпонентный метод ACRCD. Эти алгоритмы применялись в разных задачах и раньше, но не были адаптированы к транспортным моделям. В этом состоит новизна нашего проекта. То есть это полностью исследовательская задача», – рассказывает один из участников проекта 11-классник из Новосибирска Никита Ильтяков.
На программе школьники начали работать над научной статьей, в которой представили итоги работы. Авторами публикации стали участники проекта Никита Ильтяков, Марк Обозов и Игорь Дышлевский под руководством экспертов МФТИ: доктора физико-математических наук, профессра Александра Гасникова и преподавателя Демьяна Ярмошика.
С результатами исследования и выводами можно ознакомиться в статье, опубликованной в научном журнале «Программирование».
