Улучшить логистику в мегаполисах поможет открытие российских учёных

Учёные Лаборатории искусственного интеллекта Сбербанка и ИТМО нашли способ улучшить транспортную логистику в мегаполисах. Открытие поможет повысить эффективность грузовых перевозок, сервисов доставки, такси и общественного транспорта. По итогам исследования статья «Оценка сложности метода оптимизации поиска пути на основе кластеризации для транспортного графа» (Assessing the complexity of a path search optimization method based on clustering for a transport graph) опубликована в научном журнале EPJ Data Science уровня Q1.

Поиск кратчайшего пути между двумя вершинами — одна из фундаментальных задач теории графов. Можно проиллюстрировать это на примере навигатора. Прокладывая маршрут из точки «А» в точку «В», программа перебирает множество вариантов, чтобы найти оптимальный путь. В крупных городах с огромным количеством дорог и перекрёстков поиск на основе традиционных способов требует больших вычислений. Метод позволяет эффективно предсказывать области, содержащие кратчайший маршрут, благодаря чему многократно повышается скорость расчётов без потери точности Разработанный метод позволит не только упростить городскую навигацию и оптимизировать логистику грузоперевозок, но и эффективно работать с абстрактными графовыми структурами в различных сферах. Его можно использовать, например, в социальных сетях для быстрого поиска связей между пользователями через общих знакомых или для мгновенного доступа к нужной информации. Кроме того, метод имеет большой потенциал в биомедицине — в частности, при анализе графовой структуры белков.

Глеб Гусев, директор Лаборатории искусственного интеллекта Сбербанка:

«Логистика — одна из ключевых отраслей современной экономики, и оптимизация маршрутов сможет сэкономить многие миллиарды рублей для нашей страны. Предложенный нашими учёными метод оптимизации поиска пути на основе кластеризации графа существенно снижает потребность в вычислительных ресурсах, необходимых для построения эффективных маршрутов, особенно в условиях огромных городских сетей, характерных для мегаполисов. При этом публикация наших исследований в международном научном издании свидетельствует: мировое профессиональное сообщество высоко оценивает разработки российских учёных. Мы ставим перед собой новые амбициозные цели, которые ещё больше укрепят научный имидж нашей страны».

Сергей Митягин, директор Института дизайна и урбанистики Университета ИТМО:

«Идея исследования родилась в результате экспериментов. Мы тестировали стандартные алгоритмы для транспортной маршрутизации и заметили, что при росте зоны доставки продукции и количества транспорта расчёты значительно усложнялись и требовали больших ресурсов. Но при этом мы обнаружили важную закономерность — топологически города имеют всего несколько типов организации дорожной сети, что и натолкнуло нас на мысль использовать препроцессинг графов, учитывающий типовые топологии дорожных сетей. Наш метод основан на разделении города на вернакулярные районы, а дорожной сети — на отдельные компоненты: сначала мы оптимизируем маршруты внутри каждого района, а затем выстраиваем связи между ними. Такая двухуровневая оптимизация существенно ускоряет процесс планирования маршрутов по сравнению с традиционными методами, требующими одновременного расчёта для всего города».