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