Новый алгоритм ИИ от петербургского ИТМО ускорил поиск оптимального маршрута для автотранспорта
Новый российский алгоритм RIDE в 30 раз ускорил логистические расчеты для автотранспорта. Разработка масштабируема и будет полезна как для организации курьерской доставки, так и для перевозки нефтепродуктов.
Специалисты исследовательского центра "Сильный ИИ в промышленности" ИТМО совместно с Лабораторией искусственного интеллекта Сбербанка создали открытую Python-библиотеку RIDE для ускорения логистических расчетов любого масштаба: от районного до международного.
"Ключевое преимущество RIDE в том, что он сразу сокращает область поиска оптимального маршрута. Инструмент анализирует топологические свойства транспортных сетей, представленных в виде графов. Большие и сложные графы разбиваются на иерархии (подграфы), чтобы упростить задачу. Сначала идет поиск кратчайшего пути именно между иерархиями, а уже затем на основе выделенного подграфа находится точное решение. Ограничивая количество перебираемых вариантов маршрутов, мы значительно ускоряем процесс вычислений. Это особенно важно для задач логистики, требующих оперативных расчетов, таких, например, как организация курьерской доставки продуктов", — рассказал аспирант ИТМО и сотрудник исследовательского центра "Сильный ИИ в промышленности" Георгий Концевик.
RIDE был успешно протестирован на графах уличных дорожных сетей более 500 городов. Согласно результатам испытаний, применение иерархического подхода ускоряет маршрутизацию до 30 раз. При этом погрешность вычислений без использования значительных объемов памяти составит до 10%, а если задействовать память системы максимально, погрешность будет нулевая. Также испытания показали, что RIDE позволяет многократно формировать маршруты в сжатые сроки и подходит для сложных типов доставок со множеством ограничений, например, для перевозки нефтепродуктов автомобильным транспортом.
