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