Российские исследователи разработали метод, позволяющий значительно ускорить моделирование дорожного движения на долгосрочную перспективу без значительного ущерба для точности прогнозов. Аналогично можно ускорить и другие оптимизационные вычисления.
«Нашу работу важно воспринимать не только как алгоритм для оптимизации транспортных потоков, но и как пример более общей идеи. Алгоритмы, использующие для решения задач оптимизации линейный минимизационный оракул – подпрограмму, которая на каждом шаге находит кратчайшие пути для всех пар, можно существенно ускорить, особенно в задачах большой размерности, где такой оракул является узким местом», – пояснил сотрудник МФТИ Игорь Игнашин.
Игнашин и другие исследователи утверждают, что оптимизация и прогнозирование дорожного трафика играют ключевую роль в математике и городском планировании. Для краткосрочных прогнозов движения транспорта на несколько минут или часов используются различные методы машинного обучения. Однако для долгосрочных прогнозов применяются математические модели, основанные на равновесном распределении транспортных потоков.
Эти модели предполагают, что каждый водитель выбирает наиболее быстрый маршрут, а время поездки зависит от загруженности дорог. Для составления прогнозов программа должна определить кратчайшие маршруты между всеми возможными комбинациями точек отправления и назначения в дорожной сети. В настоящее время эти маршруты рассчитываются с помощью графовых алгоритмов, выполнение которых значительно увеличивается с ростом сложности дорожной сети.
Российские ученые предложили ускорить эти вычисления, используя случайный выбор данных вместо анализа всего объема информации, как это часто делается в алгоритмах искусственного интеллекта. На основе этой идеи они разработали новую версию метода Франка-Вульфа для прогнозирования дорожного трафика, которая случайным образом отбирает только 10% пунктов отправления на каждом этапе подготовки прогноза.
Эффективность этого подхода была проверена на нескольких простых и сложных дорожных сетях реальных городов. Результаты показали, что новый метод ускоряет составление прогнозов для крупных американских мегаполисов в 10 раз по сравнению с существующими алгоритмами, сохраняя при этом высокую точность расчетов. Ученые считают, что это существенно ускорит процесс составления долгосрочных прогнозов трафика для больших городов.
Источник: ТАСС
распечатать статью
