Точное прогнозирование дорожного движения остается одной из ключевых задач для современных мегаполисов. От качества таких расчетов зависит эффективность транспортного планирования, развитие городской инфраструктуры и снижение нагрузки на дороги. Российские ученые предложили новый математический подход, который позволяет ускорить моделирование дорожного трафика в десятки раз, практически не теряя в точности результатов. По мнению исследователей, разработка может найти применение не только в транспортной сфере, но и в решении широкого круга сложных оптимизационных задач, передает inbusiness.kz со ссылкой на ТАСС.
О создании нового метода сообщил Центр научной коммуникации МФТИ. Разработка позволяет значительно сократить время, необходимое для построения долгосрочных прогнозов дорожного движения, сохраняя при этом высокую точность вычислений.
"Нашу работу важно воспринимать не только как алгоритм для оптимизации транспортных потоков, но и как пример более общей идеи. Алгоритмы, использующие для решения задач оптимизации линейный минимизационный оракул, — подпрограмму, которая на каждом шаге находит кратчайшие пути для всех пар, можно существенно ускорить, особенно в задачах большой размерности, где такой оракул является узким местом", — пояснил сотрудник МФТИ Игорь Игнашин.
Как отмечают Игнашин и его коллеги, прогнозирование и оптимизация дорожного трафика являются одними из наиболее важных направлений современной математики и городского планирования. Если для краткосрочных прогнозов, охватывающих несколько минут или часов, сегодня широко применяются различные методы машинного обучения, то для долгосрочных расчетов специалисты по-прежнему используют математические модели, основанные на равновесном распределении транспортных потоков.
Такие модели исходят из предположения, что каждый водитель выбирает наиболее быстрый маршрут, а время поездки напрямую зависит от загруженности дорог. Чтобы построить прогноз, программе необходимо определить кратчайшие пути между всеми возможными пунктами отправления и назначения в исследуемой дорожной сети. Для этого используются графовые алгоритмы, однако с ростом размеров транспортной системы время вычислений увеличивается очень быстро, что делает моделирование чрезвычайно ресурсоемким.
Российские исследователи предположили, что этот процесс можно существенно ускорить, если отказаться от обработки всего массива данных и использовать лишь случайно выбранную часть информации. Подобный принцип уже давно применяется в разработке алгоритмов искусственного интеллекта, где выборочная обработка данных позволяет заметно повысить скорость вычислений без значительной потери качества результата.
Опираясь на эту идею, ученые создали новую модификацию метода Франка—Вульфа, широко используемого при прогнозировании дорожного трафика. Новый алгоритм на каждой стадии расчетов случайным образом отбирает лишь 10% пунктов отправления вместо полного набора данных, что значительно снижает вычислительную нагрузку.
Эффективность разработки была проверена на нескольких простых и сложных дорожных сетях, существующих в реальных городах США, включая Анахайм, Филадельфию и Чикаго. Испытания показали, что новый метод позволяет примерно в 10 раз быстрее строить прогнозы для крупных городских транспортных систем, по сравнению с существующими алгоритмами. При этом точность расчетов практически не уступает традиционным подходам.
По словам исследователей, предложенный алгоритм способен заметно ускорить подготовку долгосрочных прогнозов дорожного движения для крупных городов. Кроме того, сам принцип выборочной обработки данных может оказаться полезным и в других задачах оптимизации, где основные вычислительные затраты приходятся на поиск большого количества кратчайших маршрутов. Это открывает возможности для создания более быстрых математических моделей, востребованных как в транспортной отрасли, так и в других сферах, где требуется анализ сложных систем и больших объемов данных.
Читайте по теме:
Шоссе Коргалжын частично закроют в Астане
