Представьте себе: вы специалист по обработке данных, работающий в одной из крупнейших в мире фирм по доставке товаров для удобства. Последние несколько дней вы работали над новым алгоритмом, который ускорит доставку и сократит расходы! Этот алгоритм представляет собой новый способ решить, какой партнер по доставке должен быть назначен для того или иного заказа. Этот алгоритм хорош, потому что он использует входные данные из нескольких прогнозов машинного обучения. Прогнозы, которые помогли вам учесть все потенциальные переменные — ожидания клиентов, трафик в реальном времени и знание местности партнером по доставке.
Вы охотно развертываете этот алгоритм, чтобы проверить его в городе. Но это не сработает. Почему? Потому что он просто слишком тяжелый. Просто бежать долго! Заказы продолжают накапливаться, а партнеры по доставке продолжают ждать своей следующей обязанности — но алгоритм слишком медленный! Вы можете увеличить его скорость, сделав его простым, удалив функцию здесь, дерево там. Но все, что он делает, это превращает ваш алгоритм в Random Forest Gump!
В команде Swiggy по обработке данных Core-Logistics, которая занимается алгоритмами для улучшения качества доставки, это сценарий конца света, которого мы все боимся! С момента своего основания Swiggy росла впечатляющими темпами. С недавним набегом на доставку продуктов рост вряд ли замедлится в ближайшее время! Судный день еще не наступил, и мы активно работаем над тем, чтобы его избежать! Решения были довольно забавными — например, объединение встраивания слов с картографическими данными для создания кластеров местоположений. Это может звучать как случайное сопоставление модных словечек машинного обучения. Но решение, которое мы рассмотрим в следующем блоге, делает именно это. Во-первых, давайте начнем с краткого обзора самого алгоритма присваивания.
Алгоритм назначения
Пакет состоит из одного или нескольких заказов, которые доставляются вместе одним партнером по доставке. Алгоритм назначения решает, какая партия заказов должна быть назначена какому партнеру по доставке. На одну партию может быть назначен не более одного партнера. Это алгоритм оптимизации целочисленной линейной программы (ILP), который пытается минимизировать общую стоимость доставки и максимально повысить качество обслуживания клиентов. Для достижения оптимального решения все партии и партнеры по доставке, которые могут влиять друг на друга, должны вместе участвовать в оптимизации. Таким образом, алгоритм назначения работает для всех активных пакетов и партнеров из определенного города. Забеги происходят через короткие и регулярные промежутки времени.
Запуски для разных городов также асинхронны и размещаются на разных машинах. Таким образом, задержка выполнения любого задания ограничена количеством пакетов и партнеров, присутствующих в конкретном городе. Есть две причины увеличения латентности этого алгоритма:
- Увеличение количества заказов: Это приводит к увеличению количества партий. Мы также нанимаем больше партнеров по доставке, чтобы обслуживать большее количество заказов. Оба эти фактора приводят к увеличению латентности.
- Алгоритмы машинного обучения: Алгоритмы машинного обучения используются для вычисления входных данных для алгоритма назначения. Например: стоимость доставки зависит от общего расстояния, пройденного партнером, и времени, проведенного в ожидании в ресторане. Отдельные алгоритмы ML используются для прогнозирования обоих этих компонентов. Алгоритмы машинного обучения интегрированы с помощью API. При вызове модели соответствующие функции извлекаются из платформы DSP. Таким образом, каждый вызов модели имеет некоторую задержку. По мере увеличения количества и сложности таких алгоритмов увеличивается задержка.
Назначение уровня логистической зоны или кластера
Одним из способов поддержания низкой задержки, несмотря на эти факторы, является разделение города на логистические зоны и запуск независимых алгоритмов назначения для каждой логистической зоны. Это уменьшит количество заказов, рассматриваемых для назначения в любом отдельном запуске алгоритма, и, таким образом, уменьшит общее время выполнения.
Субоптимальность при назначении на уровне кластера
Как упоминалось в разделе об алгоритме назначения, на одну партию заказов может быть назначен не более одного партнера. Это одно из ограничений в настройке алгоритма назначения, необходимого для обеспечения допустимого решения. Это ограничение легко реализуется при выполнении одного задания на уровне города. Однако при назначении на уровне кластера, поскольку назначение для нескольких кластеров может выполняться параллельно, один партнер по доставке может быть назначен двум или более пакетам из двух разных кластеров.
В таком сценарии мы назначаем партнера первому кластеру, чтобы выполнить его назначение. Пакет из другого кластера теперь должен ждать до следующего запланированного запуска, чтобы быть назначенным новому партнеру по доставке. Если он назначен партнеру, который находится дальше от ресторана и ему нужно будет больше путешествовать, стоимость доставки может увеличиться. Доставка заказа также может быть задержана из-за задержки в назначении, что приведет к ухудшению качества обслуживания клиентов. Окончательная стоимость назначения для такой партии может быть выше, чем ее первоначальная стоимость назначения. Этот сценарий, который возникает из-за назначения на уровне кластера, может быть источником неоптимального назначения.
Методология создания логистических зон
Способ создания логистических зон для назначения должен иметь следующие характеристики:
- Минимизируйте неоптимальные назначения: метод должен минимизировать количество случаев, когда один и тот же партнер по доставке назначается более чем одной партии из разных логистических зон.
- Автоматическое масштабирование. Ожидаемое время выполнения алгоритма назначения зависит от количества комбинаций (партнер по доставке, пакет), участвующих в назначении. Увеличение числа кластеров приведет к увеличению неоптимальных назначений. Таким образом, метод должен автоматически выбирать правильное количество кластеров в зависимости от ожидаемого времени выполнения. Количество кластеров должно увеличиваться по мере увеличения ожидаемого времени выполнения.
Исходя из этого, мы предлагаем следующий метод создания логистических зон (или ресторанных кластеров):
Шаг 1. Обучение внедрению ресторана
Создайте вложения для каждого ресторана. Обучите эмбеддинги таким образом, чтобы заказы из ресторанов с похожими эмбеддингами обычно присваивались партнерам из похожих локаций.
В примере на рисунке 2 заказы из ресторанов R1 и R2 исторически назначаются партнерам из местоположения 1, а заказы из ресторанов R3 и R4 исторически назначаются партнерам из местоположения 2. Вложения будут обучены таким образом, что R1 и R2 будут имеют высокое сходство, в то время как R1 и R3 будут иметь низкое сходство
Шаг 2. Получение кластеров из вложений
Создавайте иерархические кластеры ресторанов на основе вложений. Рестораны с высоким сходством будут иметь больше шансов принадлежать к одному и тому же кластеру. Это уменьшит вероятность того, что партнер по доставке будет назначен двум пакетам из разных кластеров. В примере на рисунке 3 R1 и R2 образуют кластер 1, а R3 и R4 образуют кластер 2. Поскольку партнерам из местоположения 1 обычно назначаются заказы из кластера 1, а партнерам из местоположения 2 обычно назначаются заказы из кластера 2, вероятность межкластерного назначения уменьшается.
Шаг 3. Динамический характер кластеров
Иерархическая кластеризация поддерживает иерархию ресторанов на основе их сходства. Кластеры разных размеров могут быть получены из одной и той же иерархии. При низких задержках мы могли бы оказаться на вершине дерева без кластеров. По мере увеличения задержек мы могли бы двигаться вниз по иерархии и создавать большее количество кластеров.
Встраивания ресторана
Мы рассмотрели общее предложение по созданию иерархических зон в предыдущем разделе. Самая интересная часть головоломки — это создание встраивания ресторана. Цель состоит в том, чтобы обучить вложения таким образом, чтобы заказы из ресторанов с похожими вложениями назначались партнерам из аналогичных мест. Вот тут-то и появляется пересечение местоположения-разведки/nlp!
- Во-первых, давайте абстрагируемся от ресторанов с их расположением. Ресторанам, расположенным в непосредственной близости друг от друга, также будут назначены партнеры по доставке из аналогичного населенного пункта. Таким образом, мы создаем вложения для ресторанных локаций, а не для ресторанов.
- Расположение ресторанов фиксируется с помощью геохэшей. Каждый геохеш обозначает прямоугольную сетку. Geohash кодирует географическое положение в короткую строку букв и цифр. Геохеши имеют иерархическую структуру, как показано на рисунке 4. Все рестораны из определенного геохеша7 (150*150 метров) имеют одинаковое вложение.
Мы получаем обучающие данные из всех комбинаций (партия, партнер по доставке), которые рассматривались для назначения за исторический период. Учебные данные разработаны следующим образом:
- Рассмотрите все комбинации (batch,dp), которые когда-либо рассматривались для назначения. Каждая такая комбинация называется ребром
- Пусть r = r(партия) будет соответствующим рестораном для партии.
- Пусть g(r) будет геохешем ресторана r.
- Пусть g(dp) будет геохэшем для местоположения партнера по доставке, когда он/она рассматривался для назначения с пакетом
- g(r) и g(dp) — буквенно-цифровые обозначения соответствующих географических местоположений. Таким образом, их можно рассматривать как слова.
- Таким образом, каждую комбинацию (g(r),g(dp)) можно рассматривать как предложение
Возвращаясь к философии ресторанных кластеров, ресторанам с похожими вложениями следует назначать партнеров из схожих мест. Таким образом, ресторанные геохеши, которые часто встречаются вместе с аналогичными dp-геохэшами, должны быть похожими.
Это очень похоже на идею вложений слов, таких как word2vec — слова, которые часто встречаются вместе с похожими словами (и, следовательно, имеют схожий контекст), должны иметь аналогичные вложения. Поскольку мы рассматриваем геохэши как слова, мы можем использовать методы встраивания слов для получения вложений для местоположений наших ресторанов!
И вот оно! Логистика, геолокация и НЛП вместе взятые! Мы рассматриваем два разных метода создания встраивания слов:
- Word2Vec: Word2Vec создает вложения слов таким образом, что два слова с похожим контекстом имеют аналогичные вложения. Вспомните примеры из прошлого: король:мужчина::королева:женщина!
- FastText: FastText является расширением Word2Vec. Наряду со словами, он рассматривает отдельные n-граммы, из которых состоит слово. Вложение слова — это среднее значение вложений отдельных n-грамм, из которых состоит слово. В классическом НЛП это позволяет нам получать вложения для новых слов, которые не являются частью обучающих данных. В нашем случае FastText служит совсем другой цели!
- В нашем случае мы рассматриваем геохэши как слова. Как было показано ранее, геохеши имеют иерархическое представление. Например, геохэш6, такой как «gbsuv1», «gbsuv2», «gbsuv3» и т. д., будет сопоставляться с общим геохешем5 — «gbsuv». Это, в свою очередь, сопоставит общий геохеш4 — «gbsu» и так далее.
- Таким образом, n-граммы, полученные из геохэшей, фиксируют географическую информацию! Скажем, мы планируем получить вложение для геохэша6, такого как «gbsuv1». Если при обучении встраивания мы установим минимальную длину n-грамм на 5, то при обучении будут рассматриваться две возможные n-граммы — «gbsuv» и «bsuv1». Первый из них будет эффективно фиксировать географическую близость «gbsuv1» ко всем родственным геохэшам.
- Как мы увидим в следующем разделе, по этой причине встраивания ресторанов, полученные из FastText, работают намного лучше, чем vanilla word2vec.
Оценка кластеров ресторанов
Как было показано ранее, назначение на уровне кластера приводит к неоптимальности, когда один партнер по доставке назначается двум или более пакетам из разных кластеров.
Партнер по доставке (dp) считается подверженным риску, если он/она рассматривается для назначения двух или более партий из разных кластеров. Каждая (пакетная, dp) комбинация или ребро, созданное этим dp, считается подверженным риску. Наилучший метод встраивания минимизирует процент таких ребер, подверженных риску.
Было замечено, что кластеры, созданные с помощью FastText, имеют значительно меньший процент рисковых ребер по сравнению с кластерами, созданными с помощью Word2Vec.
Оценка воздействия кластеров на землю
Чтобы оценить влияние разделения назначения внутри кластеров на землю, мы создали версию этих кластеров в нашей среде моделирования. Результаты этих симуляций показали, что мы смогли сократить время выполнения алгоритмов назначения с минимальным влиянием на какие-либо бизнес-показатели, такие как стоимость или качество обслуживания клиентов.
На этом мы завершили наш POC для кластерных заданий. В настоящее время ведется работа по фактической интеграции этих кластеров в алгоритм производственного задания. Мы поделимся результатами реального внедрения этих кластеров в будущем!
Благодарности
Спасибо Адиту Капуру за упорную работу над проектом. Особая благодарность Годе Доресвами за визуализацию проекта и руководство его реализацией!
