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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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