serkh Mar 11 at 07:00

Доставка день в день: погружение в базовые алгоритмы поиска и назначения курьеров в Яндекс Доставке

Hard

27 min

6.2K

Яндекс corporate blogAlgorithms*Programming*System Analysis and Design*

+29

Comments 10

ildarz Mar 11 at 08:48

Вот так... деревья, Больцано-Вейерштрасс, Дейкстра... А потом Агубаджон несколько часов нарезает круги по микрорайону, развозя другие заказы и при этом раз пять проезжая мимо вашего дома, и в итоге уезжает на другой конец города. А поддержка разводит руками и дает купон на скидку (или нет). Причем это не разовый случай, и именно при доставке "в день", экспресс-доставка гораздо адекватнее.

serkh Mar 13 at 07:05

Обычно такая "некомпактность" возникает из-за дополнительных ограничений при объединении заказов в один маршрут. Например: два заказа нужно доставить в один район, но один заказ ожидается днём, а другой — вечером. В этом случае доставить их подряд не получится, хотя точки их получения находятся близко друг к другу.

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

leotsarev Mar 12 at 04:15

А вот эти куски, они общие с яндекс.такси или нет? По логике должны быть, они один в один.

algol Mar 12 at 16:19

Сервисы Яндекс Такси, Яндекс Доставка, Яндекс Еда и Яндекс Лавка построены на единой технологической базе (Техплатформе), но каждый из них использует собственные алгоритмы оптимизации назначения. Это обусловлено спецификой бизнеса и уникальными требованиями к процессу доставки в каждом случае.

Fedot1986 Mar 13 at 06:19

Могу лишь сказать,что ваш алгоритм не работатет так как вы описываете.

На самом деле все работает иначе.

Не назначает по 2 заказа? Бред, вы обединяете 2-4заказа в 1 заказ с разными точками получения и отдачи и называете это мультизаказом.

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

Это лишь малая часть, того что я на своей спине ощутил, сотрудничая с сервисом.

Допустип, я в качестве пешего курьера вышел на линию, ваша система легко может назначить на пешего курьера заказ превышающий 20кг и 5 километровым путем. И такое довольно часто при назначении заказов для пеших курьеров.

serkh Mar 17 at 11:17

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

nrsmsf Mar 20 at 14:59

Это все очень круто, но вы являетесь единственным сервисом доставки, в котором нельзя получить информацию о доставке по номеру заказа. Информацию можно получить только из приложения, с другим человеком обязательно делиться уникальной ссылкой, содержающей UUID, а не номер заказа. Пример: продавец с Авито, когда заказали товар с Яндекс Доставкой, никак не сможет отследить перемещение своего товара, только если получатель не поделится ссылкой из приложения. Хотя в приложении авито имеется номер яндекс доставки.

Akogay Mar 21 at 17:58

@serkh а можешь ключевые технологии алгоритма объединения заказов рассказать?

Ну если в этой статье ключевыми технологиями считать k‑d-дерево, реализованное в библиотеке nanoflann, алгоритм Дейкстры и венгерский алгоритм

serkh Mar 24 at 16:32

Ключевые технологии для общего случая упомянуты тут (см. раздел "Часть 4. MVRP и пробки"). Более подробно мы обязательно расскажем, но это достаточно большая тема. Stay tuned :)

А еще в некоторых простых случаях можно решать задачу на основе алгоритмов из этой статьи. Приведу пару примеров.

Допустим, у вас есть заказ из точки A в точку B (обозначу его $A \rightarrow B$ ). С помощью k-d-дерева можно решать задачу эффективного поиска "близких" заказов. Заказы $A \rightarrow B$ и $A' \rightarrow B'$ считаем близкими, если расстояние между и не превосходит , а расстояние между и не превосходит . Тогда, если всего в системе заказов, то можно пройтись по всем заказам, и для каждого из них за $O(\sqrt{N})$ найти соседей по точке A в окрестности , и потом из найденных отобрать соседей по точке B в окрестности . Таким образом, для каждого заказа получим небольшое количество ближайших соседей, из которых можно составлять комбинации.
Можно назначать заказы не только на свободных исполнителей, но и на занятых, меняя им маршрут "на лету". В этом случае нужно учесть не только позицию исполнителя, но и точки его маршрута. С помощью k-d-дерева можно искать в каком-то смысле "близкие" маршруты (например, похоже на то, как я выше описал). А ещё прелесть в том, что с точки зрения Венгерского алгоритма назначение одного заказа можно делать как на свободных, так и на занятых исполнителей, при условии что правильно подобраны веса рёбер.