Альфа-Банк: алгоритм строит маршруты доставки карт в Москве за минуту вместо получаса

Клиенты Альфа-Банка ежедневно оформляют через сайт и мобильное приложение тысячи заказов на доставку карт. Работу представителей банка нужно планировать каждый день так, чтобы они приезжали к клиенту в нужное время, обслуживали максимум заказов и не перерабатывали. Представители передвигаются пешком, на общественном транспорте или на автомобилях, у каждого свой график, а на время в пути влияет даже погода. Маршруты должны обеспечивать доставку в срок, равномерную нагрузку на сотрудников и отсутствие поездок в разные концы города; от числа завершённых доставок зависят в том числе премии сотрудников.

Отдел геоаналитики банка разработал собственную систему маршрутизации. На входе — адреса доставки на день с координатами, временные интервалы, число сотрудников и их навыки. Сначала заказы группируются алгоритмом K-Means-constrained по географической близости и интервалу доставки; число кластеров равно числу сотрудников на смене, а размер кластера ограничен сверху и снизу. Затем алгоритм сопоставляет кластеры с навыками и графиком сотрудников, перераспределяет оставшиеся заказы, а постбалансировщик выравнивает нагрузку. На последнем этапе собственный комбинаторный алгоритм решает множественную задачу коммивояжёра и строит оптимальные маршруты.

Альфа-Банк описал систему в блоге на vc.ru 2 октября 2023 года. К этому моменту банк уже применял технологию в Москве, Новосибирске, Омске, Томске и нескольких других крупных городах. Система интегрирована с другими внутренними системами банка; логисты могут задавать ограничения на пересечение препятствий и учитывать особенности местности. Для Москвы время построения качественного маршрута сократилось с получаса до одной минуты; благодаря кучности адресов банк практически избавился от заказов, ради которых представители пересекали половину города. Команда планирует учитывать погоду и предпочтительный район сотрудника, а также применить решение в других компаниях группы — АльфаСтраховании и Билайне.