Российские исследователи представили передовой алгоритм для ускорения транспортной маршрутизации

Специалисты Лаборатории искусственного интеллекта Сбербанка в партнерстве с коллегами из ИТМО создали Python-библиотеку RIDE, которая сокращает время на поиск кратчайшего пути на графе. Решение позволяет повысить производительность логистических расчетов произвольного масштаба от городского до регионального или масштаба целой страны. О новой разработке учёных стало известно в ходе трека «Наука» международной конференции AI Journey («Путешествие в мир искусственного интеллекта»).

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

Библиотека RIDE предоставляет методы, которые значительно ускоряют процесс построения субоптимальных маршрутов, особенно на больших (транспортные графы крупных городов, регионов и стран) и абстрактных графах (графы цитирования). Библиотека наиболее актуальна, когда нужно многократно формировать маршруты в сжатые сроки. RIDE позволяет разработчикам сделать высокопроизводительный продукт от мобильного приложения до AI-инструмента, быстро проверить научные гипотезы и сэкономить массу времени.

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