Как Альфа-Банк делал собственную систему маршрутизации для доставки в 1300 городов
Буквально каждый день решая «задачу коммивояжёра».
Одна из самых известных задач в прикладной математике — задача коммивояжера (так раньше называли торговых представителей) — как объехать максимум городов за ограниченное время и потратить как можно меньше денег на билеты. Математики предложили первые решения этой проблемы ещё в 1930 году, но исследования продолжаются, ведь усложняется и сама задача. Однако теперь множественную задачу коммивояжера для нас решают собственные математические алгоритмы. Рассказываем, как это удалось.
Почему банку понадобилась собственная технология
Клиенты Альфа-Банка привыкли пользоваться доставкой. Ежедневно через сайт и мобильное приложение банк получает тысячи заказов на доставку карт. И работу наших представителей нужно ежедневно планировать так, чтобы они появлялись у клиента в нужное время, при этом обслуживали максимум заказов и не перерабатывали.
Представители банка отправляются на встречу с людьми пешком, на общественном транспорте или автомобилях, у каждого из них свой график работы, а на время в пути влияет даже погода в регионе. Иными словами, факторов очень много и произвольный специалист службы доставки не всегда может обслужить любой заказ — при выдаче маршрутов с адресами всё это нужно учитывать.
При этом маршруты должны быть составлены так, чтобы:
- все запланированные доставки были выполнены вовремя;
- нагрузка на всех специалистов была по возможности равномерной;
- маршруты были составлены оптимально (например, не было поездок в разные концы города);
- рабочего времени хватало на посещение всех адресов маршрута.
И очень важно, чтобы не было дисбаланса нагрузки — один сотрудник отвёз только пару заказов, а другой выполнил 20 за день. Количество завершённых доставок влияет в том числе и на премии людей.
Как мы решали «задачу коммивояжёра»
Специалисты по геоаналитике банка наметили нескольких стадий обработки первичных данных. К ним относятся массив из адресов доставки на конкретный день (здесь важно учесть, что помимо названия улицы и номера дома, каждый адрес это ещё и географические координаты — точка с определённой широтой и долготой), временные интервалы доставки, количество сотрудников службы доставки и их навыки.
На первом этапе эти данные проходят первичную кластеризацию. Заказы группируются по географической близости (как раз по ширине и долготе), а также временному интервалу. Иногда они могут группироваться и по предмету доставки — дебетовые или кредитовые карты.
Здесь используется широко известный алгоритм K-Means-constrained: он «разрезает» весь объём адресов-точек на заданное количество кластеров. У каждого кластера есть свои жесткие ограничения сверху и снизу — например, в них может быть не больше 10, но не меньше 4 адресов.
Количество кластеров соответствует числу специалистов, которые в этот день заступают на работу. Поэтому «нарезаются» они так, чтоб один представитель банка мог обслужить весь объем «своих» адресов за рабочий день.
Помимо первичных кластеров есть и так называемые кластеры после обработки. Предположим, что в первичном кластере какое-то количество заказов не соответствует навыкам сотрудника (допустим, чтобы выполнить эти заказы, нужен автомобиль, а представитель передвигается пешком). Или интервалы заказов не совпадают с его временем работы. В этом случае алгоритм начинает повторный перебор, сопоставляя других сотрудников с этим кластером. Так происходит пока не произойдёт мэтч, словно в приложении для знакомств — характеристики курьера и кластера окажутся взаимно совпадающими. И тогда адреса из данного кластера станут точками его маршрута на сегодня.
Конечно, не всегда удаётся распределить все адреса. Некоторые остаются «подвешенными». Для них используется дополнительная кластеризация и перераспределение — такие заказы может подхватить менее нагруженный или географически наиболее близкий специалист.
В итоге огромный граф с координатами всех адресов доставки в городе разбивается на множество маленьких графов с короткими ребрами и близко расположенными вершинами — точками адресов. Так достигается важный параметр «кучности».
На последнем этапе вступает особый комбинаторный алгоритм, который решает множественную задачу коммивояжера и строит из полученных малых графов оптимальные маршруты. Это полностью разработка отдела геоаналитики Альфы.
Что получили
Альфа-Банк уже начал применять технологию в Москве, Новосибирске, Омске, Томске и в нескольких других крупных городах.
Собственная разработка сразу упростила процесс работы. Очевидное преимущество — бесшовная интеграция с другими внутренними системами банка. Также логисты теперь могут вводить ограничения на пересечение препятствий и строить маршруты сразу с учётом особенностей местности.
Алгоритм получился очень быстрым. Для Москвы, например, время построения качественного маршрута сократилось с получаса до одной минуты! А благодаря кучности практически удалось избавиться от заказов, ради которых представители банка пересекали половину города.
Что дальше
Команда разработчиков планирует добавить несколько полезных функций. Например, при составлении маршрутов и расчёте расстояния учитывать погоду и другие внешние факторы. Ещё одна из задумок — дать возможность специалистам указывать предпочтительный район доставок, чтобы они могли работать недалеко от своего дома.
Создатели планируют применять эти логистические решения и в других компаниях группы — АльфаСтрахование, Билайн и т.д., а затем сделать полностью публично доступным инструментом. Возможно даже выложить его в открытый доступ.
Решить задачу коммивояжера на 4-10 "городов" это, конечно, не rocket science, но все равно приятно, что коммерческие предприятия занимаются этим.
С промежуточной кластеризацией решение все равно получается эвристическим, так что я бы лучше сразу использовал эвристику для решения множественной задачи коммивояжера. Например, для вашей задачи можно использовать алгоритм муравьиных колоний (Ant Colony Optimization). Количество муравьев на каждой итерации соответствует числу сотрудников, муравьи стартуют с места жительства сотрудников и пытаются обойти "города" в соответствии с теми ограничениями, что вы наложили. При этом помимо ограничений на граф, вы можете динамически поддерживать ограничения такие как максимальное число "городов" у каждого сотрудника, или задать набор навыков у сотрудника и набор навыков требуемого для каждого "города", тогда "муравьи"-сотрудники смогут выбирать только те, "города" которые соответствуют их навыкам.
Как на это ответит Альфа банк? 😅
Новой картой с фейсом модного певца ртом