Все выпуски

В работе описывается двухстадийная модель равновесного распределения транспортных потоков. Модель состоит из двух блоков, где первый блок — модель расчета матрицы корреспонденций, а второй блок — модель равновесного распределения транспортных потоков по путям. Первая модель, используя матрицу транспортных затрат (затраты на перемещение из одного района в другой, в данном случае — время), рассчитывает матрицу корреспонденций, описывающую потребности в объемах передвижения из одного района в другой район. Для решения этой задачи предлагается использовать один из наиболее популярных в урбанистике способов расчета матрицы корреспонценций — энтропийную модель. Вторая модель на базе равновесного принципа Нэша–Вардропа (каждый водитель выбирает кратчайший для себя путь) описывает, как именно потребности в перемещениях, задаваемые матрицей корреспонденций, распределяются по возможным путям. Таким образом, зная способы распределения потоков по путям, можно рассчитать матрицу затрат. Равновесием в двухстадийной модели транспортных потоков называют неподвижную точку цепочки из этих двух моделей. Практически ранее отмеченную задачу поиска неподвижной точки решали методом простых итераций. К сожалению, на данный момент вопрос сходимости и оценки скорости сходимости для этого метода не изучен. Кроме того, при численной реализации алгоритма возникает множество проблем. В частности, при неудачном выборе точки старта возникают ситуации, в которых алгоритм требует вычисления экстремально больших чисел и превышает размер доступной памяти даже в самых современных вычислительных машинах. Поэтому в статье предложены способ сведения задачи поиска описанного равновесия к задаче выпуклой негладкой оптимизации и численный способ решения полученной задачи оптимизации. Для обоих методов решения задачи были проведены численные эксперименты. Авторами использовались данные для Владивостока (для этого была обработана информация из различных источников и собрана в новый пакет) и двух небольших городов США. Методом простой прогонки двух блоков сходимости добиться не удалось, тогда как вторая модель для того же набора данных продемонстрировала скорость сходимости $k^{−1.67}$.

С ростом населения городов сильнее ощущается необходимость планирования развития транспортной инфраструктуры. Для этой цели создаются пакеты транспортного моделирования, которые обычно содержат набор задач выпуклой оптимизации, итеративное решение которых приводит к искомому равновесному распределению потоков по путям. Одно из направлений развития транспортного моделирования — это построение более точных обобщенных моделей, которые учитывают различные типы пассажиров, их цели поездок, а также специфику личных и общественных средств передвижения, которыми могут воспользоваться агенты. Другим не менее важным направлением является улучшение эффективности производимых вычислений, так как в связи с большой размерностью современных транспортных сетей поиск численного решения задачи равновесного распределения потоков по путям является довольно затратным. Итеративность всего процесса решения лишь усугубляет это. Одним из подходов, ведущим к уменьшению числа производимых вычислений, и является построение согласованных моделей, которые позволяют объединить блоки 4-стадийной модели в единую задачу оптимизации. Это позволяет исключить итеративную прогонку блоков, перейдя от решения отдельной задачи оптимизации на каждом этапе к некоторой общей задаче. В ранних работах было доказано, что такие подходы дают эквивалентные решения. Тем не менее стоит рассмотреть обоснованность и интерпретируемость этих методов. Целью данной статьи является обоснование единой задачи, объединяющей в себе как расчет матрицы корреспонденций, так и модальный выбор, для обобщенного случая, когда в транспортной сети присутствуют различные слои спроса, типы агентов и классы транспортных средств. В статье приводятся возможные интерпретации для калибровочных параметров, применяемых в задаче, а также для двойственных множителей, ассоциированных с балансовыми ограничениями. Авторы статьи также показывают возможность объединения рассматриваемой задачи с блоком определения загрузки сети в единую задачу оптимизации.

С 50-х годов XX века транспортное моделирование крупных мегаполисов стало усиленно развиваться. Появились первые модели равновесного распределения потоков по путям. Наиболее популярной (и использующейся до сих пор) моделью была модель Бэкмана и др. 1955 г. В основу этой модели положены два принципа Вардропа. На современном теоретико-игровом языке можно кратко описать суть модели как поиск равновесия Нэша в популяционной игре загрузки, в которой потери игроков (водителей) рассчитываются исходя из выбранного пути и загрузках на этом пути, при фиксированных корреспонденциях. Загрузки (затраты) на пути рассчитываются как сумма затрат на различных участках дороги (ребрах графа транспортной сети). Затраты на ребре (время проезда по ребру) определяется величиной потока автомобилей на этом ребре. Поток на ребре, в свою очередь, определяется суммой потоков по всем путям, проходящим через заданное ребро. Таким образом, затраты на проезд по пути определяются не только выбором пути, но и тем, какие пути выбрали остальные водители. Таким образом, мы находимся в стандартной теоретико-игровой постановке. Специфика формирования функций затрат позволяет сводить поиск равновесия к решению задачи оптимизации (игра потенциальная). Эта задача оптимизации будет выпуклой, если функции затрат монотонно неубывающие. Собственно, различные предположения о функциях затрат формируют различные модели. Наиболее популярной моделью является модель с функцией затрат BPR. Такие функции используются при расчетах реальных городов повсеместно. Однако в начале XXI века Ю. Е. Нестеровым и А. де Пальмой было показано, что модели типа Бэкмана имеют серьезные недостатки. Эти недостатки можно исправить, используя модель, которую авторы назвали моделью стабильной динамики. Поиск равновесия в такой модели также сводится к задаче оптимизации. Точнее, даже задаче линейного программирования. В 2013 г. А. В. Гасниковым было обнаружено, что модель стабильной ди- намики может быть получена предельным переходом, связанным с поведением функции затрат, из модели Бэкмана. Однако обоснование упомянутого предельного перехода было сделано в нескольких важных (для практики), но все- таки частных случаях. В общем случае вопрос о возможности такого предельного перехода, насколько нам известно, остается открытым. Данная работа закрывает данный зазор. В статье в общем случае приводится обоснование возможности отмеченного предельного перехода (когда функция затрат на проезд по ребру как функция потока по ребру вырождается в функцию, равную постоянным затратам до достижения пропускной способности, и равна плюс бесконечности, при превышении пропускной способности).

В работе приведены возможные улучшения двухстадийной модели равновесного распределения транспортных потоков, повышающие качество детализации моделирования и скорость вычисления алгоритмов. Модель состоит из двух блоков, первый блок — модель расчета матрицы корреспонденций, второй блок — модель равновесного распределения транспортных потоков по путям. Равновесием в двухстадийной модели транспортных потоков называют неподвижную точку цепочки из этих двух моделей. Более подробно теория и эксперименты по данной модели были описаны в предыдущих работах авторов. В этой статье в первую очередь рассмотрена возможность сокращения вычислительного времени алгоритма расчета кратчайших путей (в модели стабильной динамики, равновесно распределяющей потоки). В исходном варианте эта задача была выполнена с помощью алгоритма Дийкстры, но, так как после каждой итерации блока распределения транспортных потоков, время, требующееся для прохода по ребру, изменяется не на всех ребрах (и если изменяется, то очень незначительно), во многом этот алгоритм был избыточен. Поэтому были проведены эксперименты с более новым методом, учитывающим подобные особенности, и приведен краткий обзор других ускоряющих подходов для будущих исследований. Эксперименты показали, что в некоторых случаях использование выбранного T-SWSF-алгоритма действительно сокращает вычислительное время. Во вторую очередь в блоке восстановления матрицы корреспонденций алгоритм Синхорна был заменен на алгоритм ускоренного Синхорна (или AAM-алгоритм), что, к сожалению, не показало ожидаемых результатов, расчетное время не изменилось. Инак онец, в третьем и финальном разделе приведена визуализация результатов экспериментов по добавлению платных дорог в двухстадийную модель, что помогло сократить количество перегруженных ребер в сети. Также во введении кратко описана мотивация данных исследований, приведено описание работы двухстадийной модели, а также на маленьком примере с двумя городами разобрано, как с ее помощью выполняется поиск равновесия.