Геоданные и уникальные алгоритмы: как Veeroute добивается топ-результата в маршрутизации

Чтобы понять принцип работы автоматической маршрутизации, существенно повышающей эффективность бизнес-процессов, необходимо разобраться в теме геоданных. Предлагаем сделать это вместе со специалистом, который занимается инженерной разработкой именно таких программных моделей. Задаём вопросы о геоданных и маршрутизации ведущему алгоритмисту компании Veeroute Вячеславу Соколову.

Вячеслав, нам необходимо «нырнуть» в сложную инженерную тему и понять, как геоданные используются при разработке продукта Veeroute и зачем они нужны клиентам компании?

То, что интересует всех наших клиентов в том или ином виде – от чего непосредственно зависит качество наших результатов и их применимость – это математические модели, которые мы разрабатываем. Если мы говорим о проектах по внедрению маршрутизации, то в модель попадают не только различные параметры задачи клиента (те же окна доставки, доступный автопарк, массогабаритные характеристики), но и времена переезда между точками доставки. Вот здесь мы и подходим к понятию геоданных, которые крайне важны для нашей работы.

«Мы должны иметь возможность «отрисовать» результаты работы нашего маршрутизатора на карте для заказчика»

Во-первых, при планировании нам необходимо знать значения всех параметров модели, в частности, время в пути между точками. Во-вторых, мы должны иметь возможность «отрисовать» результаты работы нашего маршрутизатора на карте для заказчика. И третье, эти же результаты отображаются в мобильном приложении. И если курьер может и не использовать наше приложение, то логисту компании эти данные просто необходимы.

А откуда берутся геоданные?

Начнём с того, что описание реального мира (цифровая карта) с помощью различных инструментов должно попасть к нам. Данные берутся из различных геоинформационных систем (ГИС), сторонних сервисов, специализирующихся на сборе и актуализации информации. Такие источники предоставляют данные о существующих дорогах, о качестве их покрытия, действующих дорожных знаках и о целом ряде других параметров вплоть до 3d-моделей зданий. Соответствие реального мира цифровой картографической модели (вместе с возникающими в этой сфере проблемами и способами их устранения) хорошо описано в специализированных открытых источниках. Открытыми источниками геоданных, например, являются Open Street Map и Overture Maps.

Если геоданные получены, то каков следующий шаг?

Указанные геоданные носят статический характер, и перед нами стоит ещё одна задача – прогноз пробочной ситуации на дорогах. Откуда такая задача берётся? Дело в том, что любое планирование делается на будущее. Возможно, на самое ближайшее – на час или два. А зачастую — на более отдалённое, до вечера следующего дня.

«…невозможно со стопроцентной уверенностью знать о загруженности дорог <…> поэтому мы разрабатываем модели, которые будут предсказывать ожидаемую нагрузку»

Но абсолютно достоверной информации о времени, которое потребуется на переезд между точками, пусть и в самом ближайшем будущем, не существует. Даже если мы предполагаем, что водители двигаются в строгом соответствии с правилами дорожного движения, не происходит ДТП и учтены все особенности работы светофоров, невозможно со стопроцентной уверенностью знать о загруженности дорог – сколько будет транспортных средств, между какими точками поедут люди и какие маршруты следования они будут выбирать. Поэтому мы разрабатываем модели, которые будут предсказывать ожидаемую нагрузку.

Какие ещё задачи решаются на начальных этапах разработки проекта маршрутизации?

Когда компания, которая занимается логистикой, ставит нам задачу планирования, то возникает задача прямого или обратного геокодирования. Объясню, что это такое. Допустим, что нам известно название организации или адрес её нахождения, а необходимо выяснить координаты её расположения. Это нужно потому, что маршрутизация осуществляется в терминах географических координат. Мы строим так называемый «роутинг по графу дорог», узлы которого привязаны к точкам на карте с помощью системы координат. Если информации о таких точках нет, то и возникает задача геокодирования. Состоит она в том, чтобы понять соответствие адреса широте и долготе. Обратное геокодирование, соответственно, это обратный процесс – мы ищем адрес по известным координатам.

Какие вопросы о геоданных обычно задают клиенты?

У каждого клиента свои вопросы, на них всегда влияет специфика деятельности организации. Но есть, конечно, и общие темы. Первая такая тема – кто наши поставщики геоданных. Помимо источника, клиентов интересует гарантия актуальности этих данных. Второй вопрос, для нас отдельно значимый, связан ещё и с пробками. Откуда мы берём прогноз пробок и почему мы можем на него полагаться? То есть вопрос вызывает возможность контролировать точность прогноза и выполнимость тех маршрутов, которые запланировали. Второй вопрос отличается тем, что информация здесь «добывается» полностью автоматизированным способом, в то время как первая тема – это результат деятельности человека в той или иной степени. Таким образом, информация о пробках следует за «графом дорог» и является, по сути, определением скорости движения на конкретном участке маршрута в заданное время.

«Что касается точности прогноза — мы сами заинтересованы в устранении расхождений, поэтому должным образом принимаем обратную связь от клиентов и с радостью берёмся анализировать фактические времена исполнения»

Простой пример: на Невском проспекте в Петербурге в час дня фактическая средняя скорость движения, вне зависимости от официального ограничения, вряд ли превысит 20 км/ч. Но если это не дневное, а ночное время – час ночи, то дорога обычно свободна и движение осуществляется с максимально разрешённой скоростью. Из-за того, что время проезда зависит от времени отправления, выбор времени старта маршрута существенно влияет на его продолжительность и попадание во временные окна. Ошибки в прогнозах приводят к трудностям на этапе выполнения маршрута, влекут за собой издержки, в том числе репутационные. Также клиентов интересует, соответствуют ли действительности данные, которое отображаются на нашей карте, соотносятся ли они с реальным миром и другими ГИС. Мы стремимся к тому, чтобы не возникало расхождений между теми геоданными, которые мы используем при планировании, и тем, что видит заказчик. Что касается точности прогноза — мы сами заинтересованы в устранении расхождений, поэтому должным образом принимаем обратную связь от клиентов и с радостью берёмся анализировать фактические времена исполнения, если заказчик готов ими делиться.

Хорошо, перейдём от ответов к вопросам: как вы отвечаете на вопрос заказчиков об источниках геоданных?

Самый простой ответ таков: мы можем использовать данные стороннего провайдера и тогда все задачи по актуальности ложатся на этого поставщика. У этой схемы, конечно, есть свои недостатки. Первый недостаток – за данные нужно платить. И стоят они довольно дорого. Гарантия актуальности такой информации предполагает оплату такой услуги. Здесь нужно уточнить, что если у вас установлено любое приложение с цифровыми картами и вы можете проверить нужную вам локацию, то это не значит, что данный источник можно бесплатно использовать в коммерческих целях и в нужных масштабах.

«Негативные факторы мы в своей работе сводим к нулю»

Вторая проблема — далеко не все провайдеры могут передавать данные в режиме реального времени. Третья, связанная со второй, такова: при планировании с учётом пробок требуется существенно больше данных и, в принципе, должен быть способ такую информацию получить. Плюсом скажу, что не все провайдеры работают по всему миру. Да и в целом компаний, способных предоставлять геоданные, не так и много. К недостаткам можно отнести риск ухода провайдера с российского рынка или, напротив, неготовность расширяться за пределы РФ. Ещё один фактор риска – зависимость бизнеса нашего клиента не только от нас, но и от качества услуг стороннего провайдера, если его данные используются в проекте маршрутизации. Компания может не только уйти, но и, например, повысить цены без предупреждения или обанкротиться. Негативные факторы мы в своей работе сводим к нулю. Так выглядит первый способ получения геоданных, который может быть удобным, но не для всех.

А какие есть альтернативы?

Есть открытые карты, которые составляются пользователями по всему миру. Их заполняют как из альтруистических соображений, так и за деньги – если какая-то компания такую карту использует, то она может платить сотрудникам за работу по её актуализации и наполнению. Звучит неплохо, но и в этом варианте есть свои проблемы и ограничения. Основная проблема состоит в том, что если мы берем конкретную версию такой карты, то мы не получаем никаких гарантий. Мы можем обнаружить в ней проблемы, затем обойти их или исправить. Тогда через некоторое время карта будет точнее, чем была раньше. Но на это нужно время, а планирование для заказчика может требоваться прямо сейчас. И вот здесь данный источник не сработает.

«Вряд ли хоть кто-нибудь сможет гарантировать, что имеет абсолютно точную и актуальную карту всех дорог России»

Какие же геоданные в итоге используют разработчики Veeroute?

Мы используем комбинацию этих вариантов. Разные источники для разных целей. Например, данные проекта Open Street Map для карт и графа дорог и 2GIS как основного официального провайдера данных для прогноза пробок, Навител (ГК МТС) и Яндекс-карты – как дополнительные при использовании различных источников геоданных нужно учитывать ещё один важный аспект. Если какая-либо дорога популярна, то и качество её отражения на картах повышается. Соответственно, малоиспользуемые участки дорог будут в зоне риска – в таких случаях мы исправляем проблему самостоятельно. Если говорить об открытых картах, то там случаются акты вандализма – сознательной порчи карты «специфическими» пользователями. Есть компании, которые системно вносят доработки в такие карты. Этих обновлений приходиться ждать (тоже минус), но вносимые такими командами данные отличаются качеством (это проверка и надежность). Отметим ещё один важный положительный момент работы с открытыми картами: благодаря открытому формату данных существуют и в течение долгого времени развиваются библиотеки с открытым исходным кодом, которые можно использовать для решения задачи построения матриц времён и расстояний между точками.

«…мы комбинируем разные виды источников геоданных»

Приведу упрощённый пример. В запросе нужно запланировать 5000 заказов. Для планирования может возникнуть потребность переезда от точки до любой другой точки. Итого нужно посчитать таблицу со статистиками переездов размером 5 000 на 5 000, и всё это требуется выполнить за считанные секунды. Здесь мы имеем дело с вычислительной задачей высокой сложности. Кроме точек из запроса, есть много других промежуточных точек в графе дорог и фактически нужно агрегировать информацию с миллиардов переездов. На подобные запросы далеко не все провайдеры могут отвечать быстро. Возможность кастомизации, максимально быстрого получения результата при планировании и необходимость точности прогноза — причины, по которым мы комбинируем разные виды источников геоданных.

Мы обязательно продолжим диалог с Вячеславом Соколовым и узнаем, как алгоритмисты Veeroute разрабатывают наиболее эффективные маршруты, добиваются высоких вычислительных скоростей и постоянно улучшают свой продукт.

Если вас заинтересовала тема автоматической оптимизации, то вы сможете больше узнать о возможностях платформы оптимизации и компаниях, которые успешно используют продукт.