Найден способ в десятки раз ускорить прогнозирование дорожного трафика

МОСКВА, 1 июля. /ТАСС/. Российские ученые разработали подход, который позволяет в десятки раз ускорить моделирование дорожного трафика в долгосрочной перспективе, и при этом не приводит к существенному снижению в точности этих прогнозов. Схожим образом можно ускорить и другие оптимизационные расчеты, сообщил Центр научной коммуникации МФТИ.

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

Как объясняют Игнашин и другие ученые, оптимизация и прогнозирование дорожного трафика является одной из самых важных задач в математике и городском планировании. Сейчас для составления краткосрочных прогнозов движения транспорта длиной в несколько минут или часов применяются различные формы машинного обучения, однако для более длительных прогнозов используются математические модели, основанные на равновесном распределении потоков.

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

Российские ученые предположили, что данные вычисления можно ускорить в несколько раз, если брать для расчета не весь объем данных, а только случайный фрагмент, подобно тому, как часто делают различные алгоритмы в области разработки ИИ. Опираясь на эту идею, ученые создали новый вариант метода Франка-Вульфа, применяемого для прогнозов дорожного трафика, который случайным образом отбирает для расчета лишь 10% пунктов отправления на каждой стадии подготовки прогноза дорожного трафика.

Работа этого подхода была проверена на наборе из нескольких простых и сложных дорожных сетей, существующих в реальных городах США, таких как Анахайм, Филадельфия и Чикаго. Эти расчеты показали, что новый подход в 10 раз ускорял составление прогнозов для крупных американских мегаполисов по сравнению с уже существующими алгоритмами и при этом позволял достичь столь же высокой точности расчетов. В перспективе, это существенно ускорит составление долгосрочных прогнозов трафика для крупных городов, подытожили ученые.