Все выпуски

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

В статье рассматривается одна из задач транспортного моделирования — поиск равновесного распределения транспортных потоков в сети. Для описания временных издержек и распределения потоков в сети, представляемой с помощью графа, используется классическая модель Бэкмана. При этом поведение агентов не является полностью рациональным, что описывается посредством введения марковской логит-динамики: в каждый момент времени водительвыбирает маршрут случайно согласно распределению Гиббса с учетом текущих временных затрат на ребрах графа. Таким образом, задача сводится к поиску стационарного распределения для данной динамики, которое является стохастическим равновесием Нэша – Вардропа в соответствующей популяционной игре загрузки транспортной сети. Так как данная игра является потенциальной, эта задача эквивалентна минимизации некоторого функционала от распределения потоков, причем стохастичностьпро является в появлении энтропийной регуляризации. Для полученной задачи оптимизации построена двойственная задача. Для ее решения применен универсальный прямо-двойственный градиентный метод. Его особенность заключается в адаптивной настройке на локальную гладкость задачи, что особенно важно при сложной структуре целевой функции и невозможности априорно оценитьг ладкость с приемлемой точностью. Такая ситуация имеет место в рассматриваемой задаче, так как свойства функции сильно зависят от транспортного графа, на который мы не накладываем сильных ограничений. В статье приводится описание алгоритма, в том числе подробно рассмотрено применение численного дифференцирования для вычисления значения и градиента целевой функции. В работе представлены теоретическая оценка времени работы алгоритма и результаты численных экспериментов на примере небольшого американского города.

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