Моделирование транспортных потоков: принцип Вардропа и алгоритм Франка-Вульфа

Первый принцип Вардропа (Пользовательское равновесие, User Equilibrium) гласит: время в пути по всем используемым маршрутам между любой парой районов абсолютно одинаково, и оно строго меньше или равно времени в пути по любому неиспользуемому маршруту. Если бы это было не так, часть водителей обязательно свернула бы на более быстрый маршрут. Проблема заключается в том, что время проезда по улице не является константой: оно нелинейно возрастает с увеличением числа машин (функции задержки Бюро общественных дорог США, BPR). Таким образом, перестроение даже одного водителя меняет время в пути для всех остальных, создавая сложнейшую систему взаимосвязанных нелинейных дифференциальных уравнений.

Гениальное аналитическое решение предложил Мартин Бекманн. Он доказал, что эгоистичное пользовательское равновесие Вардропа можно найти, решив одну гигантскую задачу выпуклого нелинейного программирования. Целевая функция в интеграле Бекманна не имеет прямого физического смысла (это не суммарное время и не деньги), но она сконструирована так, что ее абсолютный минимум математически в точности совпадает с состоянием равновесия трафика. Это превратило задачу из области теории игр (поиск равновесия Нэша для сотен тысяч игроков) в классическую задачу математической оптимизации, для решения которой можно применить всю мощь вычислительных машин.

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

Аппарат Вардропа и алгоритм Франка-Вульфа позволили исследователям операций строго математически доказать и объяснить знаменитый Парадокс Браеса. Парадокс заключается в том, что строительство новой, быстрой дороги в перегруженной транспортной сети может парадоксальным образом увеличить время в пути абсолютно для всех водителей города. Причина кроется в эгоизме пользовательского равновесия: водители устремляются на новую дорогу, перегружая критические узкие места на съездах, уводя систему от глобального социального оптимума. Сегодня градиентные алгоритмы распределения потоков встроены в ядро навигационных систем, позволяя правительствам принимать взвешенные решения о том, какие именно улицы нужно расширять, а какие, наоборот, закрывать для движения, чтобы улучшить кровообращение мегаполиса.