Специалисты из лаборатории продвинутой комбинаторики и сетевых приложений МФТИ создали стохастический вариант знаменитого метода Франк–Вульфа (алгоритм SOFW). Их секрет прост до гениальности: чтобы понять, как поведет себя весь город, не обязательно просчитывать путь каждой машины. Достаточно заглянуть лишь в небольшую, случайную часть данных.
Почему старые методы буксуют?
Для долгосрочного планирования инженеры используют модели равновесного распределения потоков. Логика проста: водитель всегда ищет кратчайший путь, но чем больше машин на дороге, тем медленнее едет поток. Чтобы найти идеальный баланс для всего города, алгоритму приходится постоянно запускать поиск кратчайших маршрутов между всеми районами.
Главным инструментом здесь долгое время был алгоритм Дейкстры. На графе дорог он действует как турист с картой: шаг за шагом проверяет все возможные повороты, пока не найдет самый быстрый выезд.
В маленькой дорожной сети это работает мгновенно.
В гигантах же вроде Филадельфии (1525 зон) или Чикаго (1790 зон), где около 40 тысяч дорог, одна итерация расчетов могла занимать час. А таких итераций нужны тысячи.
Математика хаоса: принцип работы SOFW
Ученые МФТИ предложили радикально сменить подход. Вместо того, чтобы заставлять компьютер строить маршруты отовсюду сразу, они ввели элемент случайности. На каждом шаге алгоритм берет только 10% случайно выбранных точек отправления, но в итоге выдает решение с качеством, сопоставимым с традиционными методами.
«На мой взгляд, эту работу важно воспринимать не только как алгоритм для оптимизации транспортных потоков, но и как пример более общей идеи: алгоритмы в задачах оптимизации, использующие линейный минимизационный оракул (то есть подпрограмму, которая на каждом шаге находит кратчайшие пути для всех пар откуда–куда), можно существенно ускорить, особенно в задачах большой размерности, где такой оракул является узким местом», – резюмирует Игорь Игнашин, сотрудник лаборатории продвинутой комбинаторики и сетевых приложений МФТИ.
