Как Альфа-Банк делал собственную систему маршрутизации для доставки в 1300 городов

Буквально каждый день решая «задачу коммивояжёра».

Как Альфа-Банк делал собственную систему маршрутизации для доставки в 1300 городов

Одна из самых известных задач в прикладной математике — задача коммивояжера (так раньше называли торговых представителей) — как объехать максимум городов за ограниченное время и потратить как можно меньше денег на билеты. Математики предложили первые решения этой проблемы ещё в 1930 году, но исследования продолжаются, ведь усложняется и сама задача. Однако теперь множественную задачу коммивояжера для нас решают собственные математические алгоритмы. Рассказываем, как это удалось.

Почему банку понадобилась собственная технология

Клиенты Альфа-Банка привыкли пользоваться доставкой. Ежедневно через сайт и мобильное приложение банк получает тысячи заказов на доставку карт. И работу наших представителей нужно ежедневно планировать так, чтобы они появлялись у клиента в нужное время, при этом обслуживали максимум заказов и не перерабатывали.

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

Пример распределения заказов на доставку по Москве
Пример распределения заказов на доставку по Москве

При этом маршруты должны быть составлены так, чтобы:

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

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

Как мы решали «задачу коммивояжёра»

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

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

1. Все заказы. 2. Распределение заказов после кластеризации
1. Все заказы. 2. Распределение заказов после кластеризации

Что такое кластеризация

В переводе с латинского кластер (cluster) означает виноградную гроздь. Множество ягод винограда не разбросаны хаотически по всей лозе, а плотно сгруппированы вокруг скелета грозди. Схожим образом и любые единицы данных могут распределяться неорганизованно, а могут объединяться на основании какого-то принципа в скопления-грозди.

Здесь используется широко известный алгоритм K-Means-constrained: он «разрезает» весь объём адресов-точек на заданное количество кластеров. У каждого кластера есть свои жесткие ограничения сверху и снизу — например, в них может быть не больше 10, но не меньше 4 адресов.

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

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

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

1. Выявление заказов, требующих перераспределения. 2. Перераспределение заказов на менее загруженных сотрудников
1. Выявление заказов, требующих перераспределения. 2. Перераспределение заказов на менее загруженных сотрудников

«Когда мы работали над технологией, мы столкнулись с интересным и по-настоящему сложным моментом — эффективной балансировкой заказов по людям, чтобы их количество было примерно одинаково. Здесь мы применяем специальный постбалансировщик: он вновь проходит все точки-адреса и передаёт какие-то из них от одного человека к другому. Так оптимизируется баланс заказов. Равное количество доставок всё равно не получается у всех, но более-менее выровнять их удаётся».

Алексей Чичерин, ведущий специалист проекта логистики Альфа-Банка

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

Что такое граф

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

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

«Нюанс в том, что мы стараемся группировать заказы наиболее кучно. В таком случае отмена какого-либо заказа не сильно критична. Представитель всё равно будет загружен, но, например, может на следующий заказ поехать чуть раньше. Стандартная история — “вот я в соседнем доме, у вас интервал доставки через два часа, а мог бы я прямо сейчас подъехать” — она невозможна, если маршрут линейный, длинный и узкий. Зато может случаться при высокой кучности адресов доставки».

Эдуард Голубов, руководитель направления геоаналитики Альфа-Банка
1. Подсчёт кучности. 2. Оптимизация распределения — улучшаем показатели общей кучности
1. Подсчёт кучности. 2. Оптимизация распределения — улучшаем показатели общей кучности

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

Что получили

Альфа-Банк уже начал применять технологию в Москве, Новосибирске, Омске, Томске и в нескольких других крупных городах.

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

1. Маршруты для всех представителей. 2. Пример маршрута одного представителя.
1. Маршруты для всех представителей. 2. Пример маршрута одного представителя.

Алгоритм получился очень быстрым. Для Москвы, например, время построения качественного маршрута сократилось с получаса до одной минуты! А благодаря кучности практически удалось избавиться от заказов, ради которых представители банка пересекали половину города.

Что дальше

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

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

5454
65 комментариев

Комментарий недоступен

18
Ответить

Мне кажется эта статья больше подходит для Хабра, тут единицы тех, кому это интересно

5
Ответить

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

12
Ответить

по себе не судят, статья очень интересная

5
Ответить

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

То есть по теме статьи ничего не пишем? Какой-то алгоритм :) Для меня, как алгоритмиста, это кликбейтная статья. K-Means-constrained - это лабораторная работа для студентов.

8
Ответить

Дожили, теперь успешное решение задачки для студента 3ого курса - гордость многомилардной корпорации...

3
Ответить

Это не простая задачка. Пытаюсь решить подобную. Студенты и не рвутся и не могут ее решить.

4
Ответить