Геопространственное моделирование с применением методов машинного обучения18.06.2021 18:31

ydtbfsqnu7380rdlwtvis7v361g.png

Всем привет! Меня зовут Константин Измайлов, я руководитель направления Data Science в Delivery Club. Мы работаем над многочисленными интересными и сложными задачами: от формирования классических аналитических отчетов до построения рекомендательных моделей в ленте приложения.

Сегодня я расскажу про одну из задач, которую мы решали: про автоматизацию построения зон доставки ресторанов. Зона доставки — это область вокруг заведения, и когда вы в ней находитесь, этот ресторан отображается в списке доступных для заказа. Несмотря на всю простоту формулировки, построение зон доставки ресторанов достаточно непростая задача, в которой встречается много подводных камней не только со стороны технической реализации, но и на этапе внедрения. Я расскажу про предпосылки появления этой задачи, подходы (от более простого к сложному) и подробно рассмотрю алгоритм построения зоны доставки.

Статья будет полезна не только техническим специалистам, которые могут вдохновиться нашими подходами по работе с геоданными, но и менеджерам, которые смогут прочитать про процесс интеграции нашей модели в бизнес, увидев «грабли», а самое главное — результаты, которых удалось добиться.

Статья написана по мотивам выступления с Евгением Макиным на конференции Highload++ Весна 2021. Для тех, кто любит видео, — ищите его в конце статьи.

Бизнес-модель работы Delivery Club


Бизнес-модель Delivery Club состоит из двух частей:
  • ДДК (доставка Деливери Клаб): мы передаем заказ в ресторан и доставляем его клиенту, то есть ресторану остается только приготовить заказ к определенному времени, когда придет курьер.
  • МП (маркетплейс): мы передаем заказ в ресторан, а он своими силами доставляет заказ в пределах своей согласованной зоны.

В ДДК-модели мы отвечаем за все, кроме приготовления блюд. Это порождает много алгоритмов автоматизации процессов, и построение зон доставки — один из них, поэтому будем рассматривать его на примере этой бизнес-модели.

При этом построить зону доставки — это полбеды. Ведь география ДДК огромна и охватывает более 170 городов России с тысячами ресторанов в каждом из них, и у каждого ресторана свои индивидуальные особенности, которые необходимо учитывать при построении эффективного сервиса доставки.

Рисуем зону доставки ресторана


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

rtudwpf4_amoq5ocllrxyaoksqk.jpeg

Как процесс выглядел раньше


Исторически сложилось, что за построение зон доставки отвечали координаторы операционной команды, которые вручную перерисовывали зоны для каждого из наших партнеров. Это было трудоемко, требовало должной сноровки и, самое главное, — терпения. Несмотря на набор правил, в процессе присутствовала субъективная оценка. Даже можно было заметить индивидуальный стиль отрисовки зон, который прослеживался у каждого из менеджеров.

В итоге мы могли получить вот такие зоны: ошибка ли это уставшего менеджера или индивидуальный стиль — остается лишь догадываться.

hb4rxskup3zijnxnbgmtcfytdqc.jpeg

Стоит упомянуть и про SLA (Service Level Agreement — соглашение о максимальной длительности отрисовки зоны доставки для одного партнера): онбординг партнера или подготовка его зоны для внедрения в нашу платформу составляли порядка 40 минут для одного заведения. Представьте, что к вам подключилась городская сеть с сотней ресторанов, а если это ещё и жаркий сезон, например, после проведения рекламной акции… Вот наглядное доказательство неэффективности ручной отрисовки:

$T = R * SLA = 100 * 40\ минут =\ \sim 67\ часов\ ручной\ работы$


где $T$ — время, которое будет затрачено на отрисовку всех зон доставки партнера,
$R$ — количество ресторанов,
$SLA$ — время на отрисовку одной зоны.

Проблемы ручной отрисовки зон:


  • непостоянство результата;
  • непрозрачная логика;
  • субъективизм в принятии решений о форме зоны и ее характеристиках;
  • однообразный подход без учета индивидуальных особенностей партнера;
  • крайне низкая скорость построения зон;
  • ручной труд менеджеров;
  • отсутствие гибкости в управлении характеристиками зон доставки (зона представляла собой единую нераздельную сущность, внутри которой нельзя было установить разную стоимость доставки в зависимости от расстояния между клиентом и рестораном).

Baseline


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

При этом оставались недостатки:

  • артефакты в зонах доставки (стандартный случай с переходом через реку);
  • единообразный подход к партнерам (не учитываются индивидуальные KPI партнеров).

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

hv83e5cemzatynnrnhrhxbuwxnc.jpeg

Пробовали алгоритмы на основе Convex Hull и Alpha Shape, с их помощью можно было бы устранить артефакты. Например, используя границы водных массивов как опорные точки для построения форм удавалось обходить реки. Однако всё равно отсутствовал индивидуальный подход к партнерам.

Преимущества технологии H3


Мы стремились прийти к универсальному решению. Каких-то простых и популярных подходов найти не удалось, поэтому мы сосредоточились на разработке собственного алгоритма. А за основу взяли технологию H3 компании Uber.

pmq9gdtpgodfe808wqedr5fx7um.png
Источник: eng.uber.com/h3

Система геопространственной индексации H3 представляет собой дискретную глобальную сеточную систему, состоящую из крайне точной гексагональной мозаичной сферы с иерархическими индексами. То есть мы можем разбить всю поверхность Земли на специфические фигуры разного размера.

Также стоит отметить, что:

  1. Существует хорошая библиотека для работы с H3, которую и выбрала наша команда в качестве основного инструмента. Библиотека поддерживает многие языки программирования (Python, Go и другие), в которых уже реализованы основные функции для работы с гексагонами.
  2. Наша реляционная аналитическая база Postgres поддерживает работу с нативными функциями H3.
  3. При использовании гексагональной сетки благодаря ряду алгоритмов, работающих с индексами, можно очень быстро получить точную информацию о признаках в соседних ячейках, например, определить вхождение точки в гексагон.
  4. Преимуществом гексагонов является возможность хранить информацию о признаках не только в конкретных точках, но и в целых областях.

Алгоритм построения зон доставки


  1. Вокруг ресторана строим лучи, вдоль которых создаем набор точек, а затем с помощью маршрутизатора рассчитываем расстояние от ресторана до каждой из точек.
    kcd0gn-5adwckaul5mygaqnvun8.png

  2. Убираем точки-выбросы. Анализируем все постройки и сразу отбрасываем те, которые нас не интересуют. Например, какие-то мелкие нежилые объекты. Далее с помощью DBSCAN формируем кластеры точек и отбрасываем те, которые для нас не являются важными: например, если кластер находится далеко от ресторана или нам экономически невыгодно доставлять туда.
    cmyo3afthwj7fz6h-mvkldts-ai.png

  3. Далее на основе очищенного набора точек применяем триангуляцию Делоне.
    -hvjkzl-ehkokgzntbku9jgtouc.png

  4. Создаем сетку гексагонов H3.
    jd2o2dcorigiontp2pqsdqy81de.png

  5. Определяем, к какому треугольнику принадлежит каждый гексагон H3, и для этого гексагона определяем расстояние от ресторана с помощью аппроксимации по трем вершинам треугольника (кто хочет чуть больше разобраться в геоматематике и понять рациональность использования тех или иных геоформ, вот ссылка на оригинал статьи Uber).
    pamnbrgidcyosz_769-qjszmufe.png

  6. Далее оптимизируем функцию ошибки, которая зависит от нашей задачи, постепенно удаляя с внешней стороны зоны по одному гексагону. При этом мы следим за формой нашей зоны, она должна оставаться цельной.
    u0r-yx3lsofhfehfuvqcf2erjaw.png

    В текущей версии алгоритма мы используем следующие функции ошибок:

    • минимизацию времени доставки при фиксированном покрытии;
    • максимизацию охвата пользователей при фиксированном времени доставки.

    Пример функции ошибки для минимизации времени доставки:

    ${L_{min}}_{time}\;=\;min(\sum_{i=1}^n\;({t_{rest}}_i)/n),$


    где $L_{min_ {time}}$ — функция ошибки минимизации времени доставки с фиксированным покрытием,
    $t_{rest_ {i}}$ — время от ресторана i до клиента,
    $n$ — количество клиентов в зоне доставки.
  7. Далее строим временной градиент в получившихся зонах (с очищенными выбросами) и с заранее определенными интервалами (например, по 10-минутным отрезкам пешего пути).
    z-wpwikvp_phi5xp2k1eky4we2i.png


Зона построена, теперь очередь оптимизации бизнес-метрики. В алгоритме используются оптимизации покрытия клиентов с фиксированием времени доставки и оптимизация времени доставки с фиксированным покрытием.

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

Внедрение


Алгоритм написан, технические и нагрузочные тесты пройдены, остается самое важное: внедрить алгоритм в бизнес-процессы.

Здесь мы столкнулись с тем, что очень трудно было менять сложившиеся бизнес-процессы, которые были налажены годами. Операторы очень не хотели передавать свои KPI «машине».

С другой стороны, сами партнеры с опаской подходили к новомодной фиче, которую им предлагали протестировать в бою. У них не было уверенности, что такую сложную задачу можно автоматизировать с сохранением прежнего качества. А те, кто отваживались, тестировали странно: предоставляли заведения с маленьким количеством заказов, для которых было достаточно трудно накопить историю для нахождения статистически значимых различий.

Но тут пришел COVID-19…

  • тысячи ресторанов закрывают свои филиалы;
  • увеличиваются зоны доставки;
  • сокращается меню и меняется целевая аудитория;
  • меняется формат работы ресторанов;
  • поменялось еще и географическое распределение заказов: до начала пандемии много заказов приходило из офисов, а во время пандемии все сидели дома и заказывали оттуда.

Всё это отчасти помогло нам убедить партнёров активнее тестировать и переходить на алгоритм автоматического построения зон доставки. В итоге, за первую неделю после начала пандемии и введения ограничения для ресторанов порядка 50% наших партнеров перешло на новые зоны доставки, которые уже были построены автоматически, а в течение следующих 3 недель уже почти не осталось партнеров с зонами, построенными вручную.

Оценка


После решения всех «горящих» проблем нам нужно было немного отдышаться и понять, что мы вообще наделали. Для этого воспользовались A/B-тестом, а точнее его вариацией — switch-back. Мы сравнивали зоны ресторанов с одинаковыми входными параметрами, оценивали GMV и время доставки, где в качестве контроля у нас были простые автоматически отрисованные зоны в виде окружностей и прямоугольников, либо зоны, отрисованные операторами вручную.

wrwu-jeeru8ljkk3ta22baeh9ds.jpeg

В итоге для разных алгоритмов мы получили прирост GMV в тестовых алгоритмических зонах при одинаковом времени доставки, либо уменьшение времени доставки в случае с алгоритмом с фиксированным клиентским покрытием.

А время, затрачиваемое на построение зон для партнера из примера выше, теперь выглядит более оптимистично:

$T = 100 * 3,6\ секунды =\ \sim 6\ минут$


Ускорение в 670 раз!

Текущая ситуация и планы


Сервис работает в production. Зоны автоматически строятся по кнопке. Появился более гибкий инструмент для работы со стоимостью доставки для клиентов в зависимости от их удаленности от ресторана. 99,9% ресторанов (изредка ещё нужно ручное вмешательство) перешли на алгоритмические зоны, а наш алгоритм поспособствовал переходу бэкенда на H3.

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

Работа с географией и зонами открыла нам дорогу к новым проектам: рекомендации для размещения, гранулярная работа с зонами доставки, более точный прогноз длительности доставки для клиента, ценообразование.

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

Всем спасибо!

© Habrahabr.ru