Ученые МФТИ ускорили алгоритм прогноза трафика на годы вперед в десятки раз

Для краткосрочных прогнозов трафика — от секунд до нескольких часов — сегодня широко применяются методы машинного обучения. Однако для долгосрочного планирования, на срок от дней до десятилетий, инженеры используют математические модели, основанные на концепции равновесного распределения потоков: предполагается, что каждый водитель выбирает самый быстрый маршрут, а время поездки зависит от загруженности дорог.

Как работает классический метод и в чем его узкое место

Классические алгоритмы, в частности метод Франк—Вульфа, на каждом шаге требуют поиска кратчайших путей от всех районов-источников. Для этого используется алгоритм Дейкстры — стандартный способ поиска кратчайших маршрутов на графе дорог. Он пошагово находит минимальное время в пути от одного источника до всех перекрестков, на каждой итерации выбирая ближайший к источнику еще не обработанный узел и проверяя, можно ли через него сократить текущее известное время до соседних узлов. В больших сетях запуск Дейкстры от одного источника занимает секунды, но при тысяче источников одна итерация метода может длиться часами. На крупных дорожных сетях — например, реальные данные по Чикаго, Филадельфии, Бирмингему — это приводит к огромным вычислительным затратам.

Стохастическое решение: брать не все данные, а случайную выборку

Авторы предложили использовать подход, распространенный в машинном обучении: для расчета брать не весь объем данных, а только случайный фрагмент. На каждой итерации алгоритма они случайным образом выбирали небольшую долю (например, 10%) из всех пунктов отправления, формировали пары «пункт отправления — пункт назначения» и вычисляли кратчайшие пути только для них. Время расчетов при этом сокращалось значительно — в 10 раз для выборки 10%, — а разница в итоговом распределении потоков была небольшой.

Новый метод получил название Stochastic Origin Frank—Wolfe (SOFW). Платой за ускорение становится увеличение нагрузки на оперативную память: теперь алгоритм хранит не только суммарный поток транспорта на каждой дороге, но и раздельное хранение потоков по парам «отправление — назначение». Это позволяет при следующем шаге изменить потоки машин, учитывая новые кратчайшие пути, только для выбранных пар. Если обсчитывается 10% пар, объем оперативной памяти должен быть увеличен в 10 раз, но при этом достигается десятикратный выигрыш во времени. На современных вычислительных системах этот компромисс оказывается оправданным.

Исследователи также разработали взвешенную версию алгоритма — SOFW‑w. В ней районы, из которых выезжает больше машин, выбираются чаще. Это ускоряет начальную сходимость: за первые итерации ошибка падает быстрее, чем у обычного SOFW.

Эксперименты на реальных дорожных сетях

Соревнование классического и стохастического алгоритмов проводилось на открытых данных из репозитория Transportation Networks. Новый метод достигает заданной точности в несколько раз быстрее. На маленьких графах (например, Сиу-Фолс с 24 зонами или Анахайм с 38 зонами) ускорение не так критично: десятикратная экономия превращает одну тысячу операций в 100 — разница малозаметна. Однако на крупных сетях — Филадельфия (1525 зон, 40 тысяч дорог) и Чикаго с окрестностями (1790 зон, 39 тысяч дорог) — те же 10 раз превращают 100 миллионов операций в 10 миллионов, что уже принципиально меняет вычислительные возможности.

«На мой взгляд, эту работу важно воспринимать не только как алгоритм для оптимизации транспортных потоков, но и как пример более общей идеи: алгоритмы в задачах оптимизации, использующие линейный минимизационный оракул, можно существенно ускорить, особенно в задачах большой размерности, где такой оракул является узким местом», — отметил Игорь Игнашин, сотрудник лаборатории продвинутой комбинаторики и сетевых приложений МФТИ.

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