Учёные из Лаборатории искусственного интеллекта Сбербанка совместно с коллегами из Университета ИТМО разработали инновационный метод, способный значительно улучшить транспортную логистику в мегаполисах. Этот прорыв поможет оптимизировать грузовые перевозки, сервисы доставки, работу такси и общественного транспорта, обеспечив быстрый и точный поиск кратчайших маршрутов в условиях сложных городских сетей. По результатам исследования статья, посвящённая оценке сложности оптимизационного метода поиска пути на основе кластеризации транспортного графа, была опубликована в престижном научном журнале EPJ Data Science, входящем в Q1.
Проблема поиска кратчайшего пути между двумя точками в городской среде является одной из ключевых задач теории графов и широко иллюстрируется на примере навигаторов. Прокладывая маршрут, навигатор перебирает множество вариантов, чтобы выбрать оптимальный путь. Однако в крупных городах, где множество дорог и перекрестков, традиционные алгоритмы требуют значительных вычислительных ресурсов и времени. Новый метод учёных позволяет предварительно выделять области, содержащие наиболее вероятные оптимальные маршруты, что многократно ускоряет расчёты без ущерба для точности. Такой подход существенно снижает нагрузку на процессоры и уменьшает время построения маршрута.
Кроме транспортной логистики, данный метод имеет универсальное применение. Его можно использовать для анализа абстрактных графов в различных сферах, например, в социальных сетях для поиска связей между пользователями через общих знакомых или для быстрого доступа к информации. Более того, перспективы применения этой технологии существуют и в биомедицине — она способна помочь при изучении сложных графовых структур белков, что открывает новые горизонты для научных исследований.
Глеб Гусев, руководитель Лаборатории искусственного интеллекта Сбербанка, отметил, что логистика является одной из главных отраслей экономики, и оптимизация маршрутов способна сэкономить стране миллиарды рублей. По его словам, предложенный метод снижает потребности в вычислительных мощностях, особенно для масштабных городских сетей, и публикация в международном журнале подтверждает высокую оценку разработок российских учёных мировым научным сообществом. Он также подчеркнул, что это лишь начало, и впереди ещё более амбициозные задачи, направленные на укрепление научного имиджа страны.
Сергей Митягин, директор Института дизайна и урбанистики ИТМО, рассказал, что идея возникла во время экспериментов, когда они столкнулись с ростом сложности расчетов при увеличении зоны доставки и числа транспортных средств. Учёные заметили, что несмотря на масштаб, топология городских дорог имеет всего несколько типовых схем. Это подтолкнуло их к использованию препроцессинга графов с учётом этих закономерностей. Разделение города на вернакулярные районы и оптимизация маршрутов сначала внутри районов, а затем связей между ними, позволили создать двухуровневую систему. Этот подход кардинально ускорил построение маршрутов по сравнению с классическими алгоритмами, которые работают с транспортной сетью целиком.
Данный метод открывает перспективы для улучшения городской инфраструктуры и может стать ключевым инструментом в цифровизации транспортных систем крупных мегаполисов, снижая затраты времени и ресурсов, а также повышая качество обслуживания горожан.