Для долгосрочного прогнозирования трафика — от дней до десятилетий — инженеры используют математические модели равновесного распределения потоков. Классический метод Франк—Вульфа требует поиска кратчайших путей от всех районов-источников на каждом шаге. В больших сетях, например в Чикаго (1790 зон, 39 тысяч дорог), одна итерация занимает часы.
Ученые Московского физико-технического института (МФТИ) из лаборатории продвинутой комбинаторики и сетевых приложений предложили стохастический вариант метода (SOFW). Об этом Науке Mail сообщили в пресс-службе вуза. На каждой итерации они случайно выбирают небольшую долю данных — например, 10% всех пунктов отправления. Время расчетов сокращается в 10 раз, а итоговое распределение потоков почти не отличается от классического.
На мой взгляд, эту работу важно воспринимать не только как алгоритм для оптимизации транспортных потоков, но и как пример более общей идеи: алгоритмы в задачах оптимизации можно существенно ускорить, особенно в задачах большой размерности.
Платой за ускорение становится рост нагрузки на оперативную память — теперь алгоритм хранит раздельные потоки по каждой паре «отправление—назначение». Однако на современных вычислительных системах этот компромисс оправдан. Исследователи также создали взвешенную версию SOFW-w, где районы с большим числом машин выбираются чаще — это ускоряет начальную сходимость.
Тесты на реальных дорожных сетях Филадельфии и Чикаго подтвердили эффективность. Десятикратное ускорение на большой сети превращает 100 миллионов операций в 10 миллионов — а это принципиальный выигрыш. В будущем авторы планируют применить ту же идею — случайный выбор фрагментов данных — к другим классическим методам оптимизации.
Ранее Наука Mail писала о том, что уральские ученые создали первое в России приложение, позволяющее проезжать перекрестки без остановок.
