Всем привет! Меня зовут Михаил Моловцев, и я алкоголик операционный аналитик в Delivery Club. Наша команда помогает бизнесу и разработке в процессах и исследованиях, связанных с курьерами и доставкой заказов. Я занимаюсь исследованиями систем назначений заказов, прогнозированием времени доставки и курьерскими скорингами. Расскажу о том, как мы обновили подход к скорингу курьеров для системы назначения заказов.

Немного о скоринге


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

У вас могут возникать разные задачи по категоризации пользователей. Например, определять клиентов с высокой лояльностью к сервису, или клиентов, которые точно смогут вернуть кредит, и т.д. То есть нужно будет вычислять степень соответствия каждого клиента той или иной категории.

Если характеристик мало, то задача не кажется сильно сложной, однако при обширном наборе параметров она становится трудоёмкой, хотя и не менее увлекательной. И тут на помощь приходит скоринговая модель: за каждую характеристику пользователя присваивается какой-то балл, а затем все баллы суммируются. Таким образом каждому пользователю ставится в соответствие некоторое число, которое называется score (или скоринговой оценкой), на основе которого можно отнести пользователя к какой-то категории.

Подобная система используется в Delivery Club при выборе наиболее подходящего курьера, который будет доставлять заказ (на самом деле есть и другие параметры, но это уже выходит за рамки статьи). Когда пользователь заказывает, система оценивает различные параметры курьеров — расстояние до ресторана, тип транспорта и т.д., — за каждый параметр присваивает балл, затем всё взвешивает и суммирует.

Недостатки прежней скоринговой системы


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

В результате не было до конца понятно, что и как влияет на бизнес-метрики. Да, все данные лежат в БД, а аналитики с помощью SQL могут посчитать нужные метрики и сделать дашборд. Однако трудности начинались при попытке спуститься на уровень «заказ-курьер» и понять, чем одно назначение курьера лучше другого с точки зрения метрик. Хотелось какого-то интуитивно понятного решения, чтобы глядя на работу модели можно было увидеть, какие метрики она пытается улучшить.

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

Мы в Delivery Club практикуем DataDriven-подход, и любое изменение в моделях скоринга обязательно проверяем с помощью А/В-тестирования (об этом можно почитать тут). В зависимости от его результатов мы либо внедряем изменение, либо дорабатываем модель, либо вообще делаем вывод, что в дальнейшем исследовании нет смысла. И если мы решаем доработать модель, то возвращаемся к предыдущему пункту.

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

Наши идеи


А что если вместо придумывания изощрённых характеристик использовать метрики напрямую? Нет ничего проще, чем посчитать сумму метрик, и выбрать курьера с наибольшим результатом. Однако метрики бывают разные и измеряются в разных единицах.

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

$score=metric_{1}+4000*metric_{2},$


где $metric_{1}$ измеряется в тысячах, $metric_{2}$ — в единицах.

Если не держать постоянно в голове размерности, то не сразу поймёшь, что вторая метрика важнее первой не в 4000 раз, а всего в 4. А хотелось бы понимать это при одном лишь взгляде на веса. Конечно, когда метрик пара десятков и все веса отличаются от единицы всё равно придется прикладывать умственные усилия, чтобы понять, во сколько раз одна метрика важнее другой, но не надо будет помнить про размерности. Таким образом мы пришли к новой формуле:

$score=\sum_{i=1}^{n}w_{i}*f(metric_{i}),$


где:
$w_{i}$ — вес метрики, который соответствует её важности/приоритету;
$metric_{i}$ — метрика, которую оптимизирует формула;
$f()$ — приведение метрик к единой шкале.

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

Казалось бы, теперь всё должно стать проще: придумали функцию, подобрали веса и все счастливы. Вообще-то нет. Помимо того, что скоринг выбирает между несколькими курьерами, надо учитывать, что бывают различные способы доставить заказ:

  1. Свободный курьер. Это когда у курьера нет назначенных заказов или заказов в сумке.
  2. Batching. Это когда курьер доставляет сразу два заказа из ресторана.
  3. Sequence. Курьер доставляет заказ и ему уже назначают следующий заказ, чтобы он доставил его сразу после текущего.

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

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

  • те, которые можно рассчитать для пары «заказ-курьер»;
  • и те, которые нельзя.

Казалось бы, всё просто: оптимизируем первые метрики и верим, что вторые будут вести себя нормально. Однако второй тип метрик тоже очень важен и хотелось бы сделать так, чтобы формула их тоже учитывала. А ведь надо ещё подбирать веса. Так почему бы не подобрать их таким образом, чтобы метрики второй группы принимали оптимальные значения? В результате метрики первой группы мы оптимизируем во время назначения курьеров, а метрики второй группы, которые не получится использовать в формуле, будут оптимизированы с помощью подбора оптимальных весов.

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

  • для одного заказа сразу скорятся несколько курьеров;
  • в один момент времени таких заказов может быть несколько;
  • в логистике есть такое явление, как сетевой эффект: при изменении одной пары «заказ-курьер» будут меняться и дальнейшие. Если все курьеры одинаковые, то нам должно быть всё равно. Но курьеры могут передвигаться пешком, на автомобиле или на велосипеде (остальные случаи не выделяем). А ещё есть Batching и Sequence назначения. Поэтому если раньше какой-то заказ доставлял пеший курьер, то новая формула может решить, что курьер на велосипеде с батчем будет гораздо лучше, и тогда дальнейшие заказы этих и не только курьеров могут измениться. Простым расчётом метрик такое уже не получится учесть.

В итоге мы пришли к тому, что нужно сделать имитационную модель автоназначений заказов.

Имитационная модель автоназначений


Под имитационной моделью мы понимаем модель, которая имитирует работу системы автоназначения Delivery Club. Модель берёт курьеров, которые работали в определенный день и все заказы, которые были сделаны в этот день. Далее модель двигается по временной шкале и выполняет следующие шаги:

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

И этот круг повторяется до тех пор, пока заказы могут быть доставлены.

Реализация модели представляет собой скрипт, написанный на Python. Выбор пал на этот язык по нескольким причинам:

  • простота использования;
  • статусы курьеров и заказов удобно представить в паттернах ООП;
  • достаточно простые механизмы для распараллеливания задач, что позволит ускорить работу модели.

Что нам это даст?


Промежуточный вариант между статичным расчетом и A/B-тестом.
Инструмент для проверки гипотез в других частях автоназначения. Например, мы можем протестировать работу нового алгоритма назначения или другой технологии, которая может быть использована в системе автоназначений.

Но тут мы столкнулись с множеством продуктовых и технических тонкостей процесса назначения и доставки заказа. Вот некоторые из них:
Проблема, с которой столкнулись Как решали
Что делает курьер, когда не доставляет заказ? В первой итерации мы решили, что курьеры будут статичными и просто «ждут» следующий заказ, стоя на месте.
Как учитывать длительность приготовления заказа и время, когда ресторан начинает его готовить? Сейчас это не учитывается.
Сколько времени курьер находится у клиента и отдаёт заказ? Для простоты используем константное время.
Как обрабатывать случаи, когда курьер не успел принять заказ? Модель предполагает, что курьер принимает заказ сразу после назначения.
Как учитывать тип транспорта курьера? Сервис для расчёта маршрутов различает типы транспорта.
Как учитывать пробки в пиковые часы? А вот тут сервис расчёта маршрутов даёт погрешность, и иногда значительную, так что мы считаем, что пробок нет.
Произошла какая-то непредвиденная ситуация и курьер не может доставить заказ. В модели предполагается, что таких ситуаций не бывает.
На некоторые ситуации пришлось закрыть глаза, потому что мы их не можем смоделировать. Но важно понимать, что имитационная модель имитирует процесс с некоторыми допущениями. Так что если она не будет учитывать какие-то непредвиденные ситуации, которые происходят с курьером, то это не критично. А учёт некоторых ситуаций вроде длительности приготовления мы отложили до лучших времен из-за того, что ещё нет уверенности в подходе с использованием имитационной модели, и тратить аналитические ресурсы впустую не хочется.

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

Череда вопросов о том, как решить эту проблему, привела меня к разработчикам сервиса, прогнозирующего время доставки (об этом можно почитать тут). Они сказали, что у нас есть инструмент, который позволяет построить маршрут и рассчитать время и дистанцию. Потоков стало больше, вычисления заметно ускорились. А потом начался увлекательный процесс отладки багов в коде и ошибок в логике.

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

А что дальше?


Казалось бы, вот оно счастье, формула готова, есть модель. Осталось прогнать А/В-тест, убедиться, что всё хорошо, и гордиться проделанной работой. Но предстоит решить ещё множество задач:

  1. Хорошо бы подобрать веса формулы, потому что сейчас имитационная модель умеет просто считать метрики для какого-то одного набора весов. Я представляю, что для этого нужно сделать, осталось только подготовиться к этому погружению в мир современных методов оптимизации.
  2. В идеальном будущем эти веса хочется задавать не статически, а динамически, чтобы автоматически подстраиваться под баланс спроса и предложения.
  3. Нужно научиться учитывать в модели все те допущения, которые были сделаны для первой итерации. Хотя бы те, которые возможно учесть. Ведь чем больше модель будет похожа на реальность, тем адекватней будут её результаты.
  4. Также хочется иметь возможность добавлять не только бизнес-метрики, такие как время доставки, но и более сложные характеристики. Например, при назначении можно учитывать оценку качества работы курьера, чтобы не назначать того, кто постоянно опаздывает или на которого много жалоб.

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

Комментарии (3)


  1. yaAubakirov
    10.09.2021 18:26
    +1

    Интересная статья! А для определения траспорта курьера нельзя проанализировать исторические данные по курьерам и разбить их на категории в зависимости от средней скорости? У курьера использующего велосипед и ходящего пешком средние скорости должны быть разные. Скорость новых курьеров принимать как пешеходов.


    1. edo1h
      11.09.2021 00:24

      ИМХО правильнее добавить метрику «скорость исполнения заказов», а как он добивается — его дело


  1. zaiats_2k
    11.09.2021 08:47

    Раз есть такой удобный инструмент, считаю надо первым делом проверить одну гипотезу - выключить всю эту тьму параметров, и отдавать доставку ближайшему курьеру.