1 of 38

АЛГОРИТМ МАРШРУТИЗАЦИИ БЕЗ КОМПРОМИССА МЕЖДУ КАЧЕСТВОМ И СКОРОСТЬЮ

Максим Берёзов�ML-инженер

2 of 38

О СЕБЕ

Работаю над маршрутизацией для логистических сервисов в сферах e-grocery, e-commerce.

3 of 38

4 of 38

ЗАКАЗОВ ДОСТАВЛЕНО КЛИЕНТАМ �ЗА 2022 ГОД (ВРЕМЯ ДОСТАВКИ �ОТ 15 МИНУТ).

БЫСТРАЯ ДОСТАВКА ПРОДУКТОВ �ДОСТУПНА В 103 ГОРОДАХ РОССИИ.

УНИКАЛЬНЫХ ПОСЕТИТЕЛЕЙ МАРКЕТПЛЕЙСА КАЖДЫЙ МЕСЯЦ.

НАПРАВЛЕНИЙ — ЛОГИСТИЧЕСКОЕ ПОКРЫТИЕ ДЛЯ ДОСТАВКИ ТОВАРОВ.

4

ИТ ДЛЯ РИТЕЙЛА РЕАЛЬНОГО ВРЕМЕНИ

>126 млн

>20 млн

26 тысяч

103 города

5 of 38

ИТ ДЛЯ РИТЕЙЛА РЕАЛЬНОГО ВРЕМЕНИ В ЦИФРАХ:

5

СЕРВИСОВ ОБЕСПЕЧИВАЮТ РАБОТОСПОСОБНОСТЬ СИСТЕМЫ

УСПЕШНО ОБРАБАТЫВАЮТ НАШИ БЭКЕНДЫ

МАКСИМАЛЬНОЕ ВРЕМЯ ОТКЛИКА БЭКЕНДОВ �В 99% СЛУЧАЕВ

РАЗ АВТОМАТИЧЕСКИ ПЕРЕСЧИТЫВАЕМ СПРОС, ОЖИДАЕМЫЙ НА СЛЕДУЮЩИЙ ДЕНЬ

300+

300 MS.

90M

18K RPS

РЕШЕНИЙ ЕЖЕДНЕВНО ПРИНИМАЮТСЯ ДЛЯ АВТОМАТИЧЕСКОГО ПЛАНИРОВАНИЯ ЧАСОВ ДОСТАВКИ

200K

6 of 38

О ЧЕМ ЭТОТ ДОКЛАД?�

  • Задача маршрутизации курьеров
  • Какие модели используем?
  • Как выглядят наши сервисы?
  • Опыт внедрения моделей в бизнес-процессы

6

7 of 38

TRAVELLING SALESMAN PROBLEM (TSP)�

количество вариантов: n! 65! > атомов во Вселенной

7

8 of 38

VRP

8

9 of 38

НО ЭТО ЕЩЕ ДАЛЕКО НЕ ВСЕ...

Что же еще нужно бизнесу?

​

  • Весогабаритные ограничения товаров
  • Схема Pickup/Delivery
  • Учет ресурсов (км, час, кол-во остановок, дозаправок, fixed cost)
  • Учет штрафов (внутри модели) за нарушение временных окон заказов или невыполнение заказов
  • Учет пределов вместимости товаров
  • Учет времени доступности склада
  • Учет временных окон работы курьера
  • Учет жестких временных окон на точке pickup

9

Pickup/Delivery

Ограничения по габаритам

Стоимость курьера

Временные окна на точке сбора

Штрафы за невыполнение заказы

Временные окна работы курьера

Время работы склада

Штрафы за нарушение временных окон

Пробки

Дозагрузка

Группа балансировки

Вместительность

10 of 38

НО ЭТО ЕЩЕ ДАЛЕКО НЕ ВСЕ...

  • Учет временных окон на точке доставки
  • Учет мягких временных окон на точках delivery
  • Учет фиксированного графика работы курьера
  • Учет текущих пробок
  • Учет грузовых мест
  • Учет сервисного времени на складе
  • Учет сервисного времени на точке delivery
  • Учет возможности дозагрузки на промежуточном складе
  • Учет необходимости возврата на склад в конце рабочего дня
  • Учет гибкого времени начала работы курьера
  • Учет фиксированных маршрутов
  • Учет групп балансировки

10

Pickup/Delivery

Ограничения по габаритам

Стоимость курьера

Временные окна на точке сбора

Штрафы за невыполнение заказы

Временные окна работы курьера

Время работы склада

Штрафы за нарушение временных окон

Пробки

Дозагрузка

Группа балансировки

Вместительность

11 of 38

КАК ЭТО ВСЕ РЕШАТЬ?

Опытный логист

11

Методы дискретной оптимизации

Обучение с подкреплением

1

2

3

* — Fontaine, Pirmin, Florian Taube, and Stefan Minner. "Human solution strategies for the vehicle routing problem: Experimental findings and a choice-based theory."Computers Operations Research 120 (2020): 104962.

?

?

12 of 38

ФРЕЙМВОРК МЕТОДОВ ДИСКР. ОПТИМИЗАЦИИ

12

Current solution

Acceptor

MoveSelector

Forager

Initial solution

Candidates

Filtered candidates

Chosen candidate

13 of 38

13

https://en.wikipedia.org/wiki/Simulated_annealing

14 of 38

14

https://en.wikipedia.org/wiki/Simulated_annealing

15 of 38

ИМПЛЕМЕНТАЦИЯ / КАКИЕ ОСНОВНЫЕ МЕТОДЫ ИСПОЛЬЗУЮТСЯ?

Технологический стек:

15

Методы:

  • Simulated Annealing
  • Tabu search / Generic Tabu search
  • Guided local search
  • Greedy descent

Python

ORTools (Google)

+

​

16 of 38

ПРИМЕР РЕАЛЬНОГО ЗАПРОСА�

16

17 of 38

КАКИЕ СЛОЖНОСТИ?

  • Модель дискретной оптимизации хороша для малых и средних задач (меньше 200 точек), дальше – сложности.
  • Невозможность параллелизации расчета.
  • Как быть с задачами с неполной информацией на момент запроса?!

17

18 of 38

ЧТО ТАКОЕ �REINFORCEMENT LEARNING

18

область машинного обучения, изучающая то, �как интеллектуальная среда (agent/brain) �должна принимать действия в окружающей среде (environment), чтобы максимизировать кумулятивную награду.

19 of 38

ЧТО ТАКОЕ �REINFORCEMENT LEARNING

19

область машинного обучения, изучающая то, �как интеллектуальная среда (agent/brain) �должна принимать действия в окружающей среде (environment), чтобы максимизировать кумулятивную награду.

20 of 38

ВЗАИМОДЕЙСТВИЕ АГЕНТА И СРЕДЫ

  • Агент наблюдает состояние среды (state);
  • Агент предпринимает действие (action);
  • Агент получает награду (reward);
  • Среда оказывается в новом состоянии.

20

21 of 38

ЗАДАЧА МАРШРУТИЗАЦИИ В ТЕРМИНАХ RL

�

22 of 38

ИМПЛЕМЕНТАЦИЯ / КАКИЕ ОСНОВНЫЕ МЕТОДЫ ИСПОЛЬЗУЮТСЯ?

Технологический стек:

22

  • Wouter et al, "Attention, learn to solve routing problems!."
  • Falkner et al. “Learning to Solve Vehicle Routing Problems with Time Windows through Joint Attention”
  • Falkner et al. “Large Neighborhood Search based on Neural Construction Heuristics”

Python

PyTorch

+

​

Подходы:

23 of 38

ПЛЮСЫ И МИНУСЫ RL

Плюсы:

  • Скорость нахождения хороших решений на больших задачах
  • Модель сама затачивается под каждую конкретную бизнес-задачу

Минусы:

  • Требует обучения
  • Проблема холодного старта
  • Плохая интерпретируемость
  • Для небольших задач лучше классические методы

23

24 of 38

МОДЕЛИ МОЖНО КОМБИНИРОВАТЬ

24

More than 200 points?

Discrete optimization model

Reinforcement �Learning model

No

Yes

25 of 38

МОДЕЛИ МОЖНО КОМБИНИРОВАТЬ

25

Solution 1

Discrete optimization model

Reinforcement �Learning model

Compare �solutions

Task

Solution 2

Final �solution

26 of 38

МОДЕЛИ МОЖНО КОМБИНИРОВАТЬ

26

Discrete

optimization model

Reinforcement �Learning model

Task

Solution

Final �solution

27 of 38

КЕЙС №1. �ОСНОВНЫЕ МЕТРИКИ E-GROCERY

27

Процент �опозданий

Процент ранних �приездов

Среднее время �в пути на курьера

Среднее расстояние �на курьера

< 6,1%

< 3,8%

< 5963 с.

< 19,3 км

28 of 38

КЕЙС №1. КАКИЕ РЕЗУЛЬТАТЫ?

28

​

Процент опозданий

Процент ранних приездов

Среднее время в пути на курьера

Среднее расстояние на курьера

​

Результат

​

​

​

​

​

До

6,1%

3,8%

5 963 сек.

19,3 км

​

0,52%

5 464 сек.

18,9 км

4,4%

29 of 38

КЕЙС №2. САМОКАТ BEAUTY

29

​

Алгоритм построения

Время построения маршрута

Интерфейс для построения маршрутов

Онлайн трекинг результатов

​

Результат

​

​

​

​

​

До

Логист

600 секунд

Excel + Карты

Нет

​

1-2 секунды

Сервис для логиста

В разработке

Модель DS

30 of 38

САМОКАТ BEAUTY. БЫЛО

30

Excel

Excel

Запрос

Маршрутизация

Логист

31 of 38

САМОКАТ BEAUTY. ПИЛОТИРОВАНИЕ

31

Excel

Excel

Запрос

Маршрутизация

Запрос

Router

DS

32 of 38

САМОКАТ BEAUTY. СЕЙЧАС

32

optimize

Логист

Application

Router

get result

33 of 38

КАКИЕ СЛОЖНОСТИ ПРИ ПРОВЕДЕНИИ ПИЛОТОВ?

  • Невозможность проведения онлайн-сравнения планов маршрутизации.
  • Курьеры иногда выбирают неоптимальные маршруты между точками А и Б. Мы это учитываем!
  • Масштабирование входных запросов. Внедряем новую модель специально для больших запросов!
  • Необходимо быстро проектировать новые матрицы времени/расстояния.

33

34 of 38

НЕВОЗМОЖНОСТЬ ОНЛАЙН-СРАВНЕНИЯ

34

  1. Точка А в 12.00
  2. Точка Б в 12.30
  3. Точка С в 13.00
  1. Точка А в 12.37
  2. Точка Б в 14.00
  3. Точка С в 14.45

План маршрутизации

Реальность

План маршрутизации и реальная маршрутизация часто отличаются :-(

35 of 38

ОЦЕНКА ВРЕМЕНИ НА УЧАСТКЕ А—Б

35

​

Время (А,Б) = 15 минут, а не 10 минут

​

А

Б

10 минут

15 минут

Мы закладываем возможные риски, которые могут возникнуть при перемещении от точки А к точке Б

​

36 of 38

АДАПТАЦИЯ ПОД ТРЕБОВАНИЯ БИЗНЕСА. �НОВЫЕ ГРАФЫ

36

Петровский�парк

Аэропорт

Савеловская

Динамо

ЦСКА

37 of 38

ПОДВЕДЁМ ИТОГИ

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

37

НАЗВАНИЕ ПРЕЗЕНТАЦИИ

38 of 38

СПАСИБО�ЗА ВНИМАНИЕ

ПИШИТЕ:

mberezov@samokat.ru

Tg. @MaximBer