Searching stochastic equilibria in transport networks by universal primal-dual gradient method
Alexander Vladimirovich Gasnikov, Meruza Kubentayeva · Computer Research and Modeling · 2018
В статье рассматривается одна из задач транспортного моделирования -поиск равновесного распределения транспортных потоков в сети.Для описания временн ых издержек и распределения потоков в сети, представляемой с помощью графа, используется классическая модель Бэкмана.При этом поведение агентов не является полностью рациональным, что описывается посредством введения марковской логит-динамики: в каждый момент времени водитель выбирает маршрут случайно согласно распределению Гиббса с учетом текущих временных затрат на ребрах графа.Таким образом, задача сводится к поиску стационарного распределения для данной динамики, которое является стохастическим равновесием Нэша -Вардропа в соответствующей популяционной игре загрузки транспортной сети.Так как данная игра является потенциальной, эта задача эквивалентна минимизации некоторого функционала от распределения потоков, причем стохастичность проявляется в появлении энтропийной регуляризации.Для полученной задачи оптимизации построена двойственная задача.Для ее решения применен универсальный прямо-двойственный градиентный метод.Его особенность заключается в адаптивной настройке на локальную гладкость задачи, что особенно важно при сложной структуре целевой функции и невозможности априорно оценить гладкость с приемлемой точностью.Такая ситуация имеет место в рассматриваемой задаче, так как свойства функции сильно зависят от транспортного графа, на который мы не накладываем сильных ограничений.В статье приводится описание алгоритма, в том числе подробно рассмотрено применение численного дифференцирования для вычисления значения и градиента целевой функции.В работе представлены теоретическая оценка времени работы алгоритма и результаты численных экспериментов на примере небольшого американского города.