Как Альфа-Банк делал собственную систему маршрутизации для доставки в 1300 городов
Буквально каждый день решая «задачу коммивояжёра».
Одна из самых известных задач в прикладной математике — задача коммивояжера (так раньше называли торговых представителей) — как объехать максимум городов за ограниченное время и потратить как можно меньше денег на билеты. Математики предложили первые решения этой проблемы ещё в 1930 году, но исследования продолжаются, ведь усложняется и сама задача. Однако теперь множественную задачу коммивояжера для нас решают собственные математические алгоритмы. Рассказываем, как это удалось.
Почему банку понадобилась собственная технология
Клиенты Альфа-Банка привыкли пользоваться доставкой. Ежедневно через сайт и мобильное приложение банк получает тысячи заказов на доставку карт. И работу наших представителей нужно ежедневно планировать так, чтобы они появлялись у клиента в нужное время, при этом обслуживали максимум заказов и не перерабатывали.
Представители банка отправляются на встречу с людьми пешком, на общественном транспорте или автомобилях, у каждого из них свой график работы, а на время в пути влияет даже погода в регионе. Иными словами, факторов очень много и произвольный специалист службы доставки не всегда может обслужить любой заказ — при выдаче маршрутов с адресами всё это нужно учитывать.
При этом маршруты должны быть составлены так, чтобы:
- все запланированные доставки были выполнены вовремя;
- нагрузка на всех специалистов была по возможности равномерной;
- маршруты были составлены оптимально (например, не было поездок в разные концы города);
- рабочего времени хватало на посещение всех адресов маршрута.
И очень важно, чтобы не было дисбаланса нагрузки — один сотрудник отвёз только пару заказов, а другой выполнил 20 за день. Количество завершённых доставок влияет в том числе и на премии людей.
Как мы решали «задачу коммивояжёра»
Специалисты по геоаналитике банка наметили нескольких стадий обработки первичных данных. К ним относятся массив из адресов доставки на конкретный день (здесь важно учесть, что помимо названия улицы и номера дома, каждый адрес это ещё и географические координаты — точка с определённой широтой и долготой), временные интервалы доставки, количество сотрудников службы доставки и их навыки.
На первом этапе эти данные проходят первичную кластеризацию. Заказы группируются по географической близости (как раз по ширине и долготе), а также временному интервалу. Иногда они могут группироваться и по предмету доставки — дебетовые или кредитовые карты.
Здесь используется широко известный алгоритм K-Means-constrained: он «разрезает» весь объём адресов-точек на заданное количество кластеров. У каждого кластера есть свои жесткие ограничения сверху и снизу — например, в них может быть не больше 10, но не меньше 4 адресов.
Количество кластеров соответствует числу специалистов, которые в этот день заступают на работу. Поэтому «нарезаются» они так, чтоб один представитель банка мог обслужить весь объем «своих» адресов за рабочий день.
Помимо первичных кластеров есть и так называемые кластеры после обработки. Предположим, что в первичном кластере какое-то количество заказов не соответствует навыкам сотрудника (допустим, чтобы выполнить эти заказы, нужен автомобиль, а представитель передвигается пешком). Или интервалы заказов не совпадают с его временем работы. В этом случае алгоритм начинает повторный перебор, сопоставляя других сотрудников с этим кластером. Так происходит пока не произойдёт мэтч, словно в приложении для знакомств — характеристики курьера и кластера окажутся взаимно совпадающими. И тогда адреса из данного кластера станут точками его маршрута на сегодня.
Конечно, не всегда удаётся распределить все адреса. Некоторые остаются «подвешенными». Для них используется дополнительная кластеризация и перераспределение — такие заказы может подхватить менее нагруженный или географически наиболее близкий специалист.
В итоге огромный граф с координатами всех адресов доставки в городе разбивается на множество маленьких графов с короткими ребрами и близко расположенными вершинами — точками адресов. Так достигается важный параметр «кучности».
На последнем этапе вступает особый комбинаторный алгоритм, который решает множественную задачу коммивояжера и строит из полученных малых графов оптимальные маршруты. Это полностью разработка отдела геоаналитики Альфы.
Что получили
Альфа-Банк уже начал применять технологию в Москве, Новосибирске, Омске, Томске и в нескольких других крупных городах.
Собственная разработка сразу упростила процесс работы. Очевидное преимущество — бесшовная интеграция с другими внутренними системами банка. Также логисты теперь могут вводить ограничения на пересечение препятствий и строить маршруты сразу с учётом особенностей местности.
Алгоритм получился очень быстрым. Для Москвы, например, время построения качественного маршрута сократилось с получаса до одной минуты! А благодаря кучности практически удалось избавиться от заказов, ради которых представители банка пересекали половину города.
Что дальше
Команда разработчиков планирует добавить несколько полезных функций. Например, при составлении маршрутов и расчёте расстояния учитывать погоду и другие внешние факторы. Ещё одна из задумок — дать возможность специалистам указывать предпочтительный район доставок, чтобы они могли работать недалеко от своего дома.
Создатели планируют применять эти логистические решения и в других компаниях группы — АльфаСтрахование, Билайн и т.д., а затем сделать полностью публично доступным инструментом. Возможно даже выложить его в открытый доступ.
Комментарий недоступен
Мне кажется эта статья больше подходит для Хабра, тут единицы тех, кому это интересно
Вылизанный маркетинговый булшит стилизованный под техническую статью. Всем насрать как альфа решает задачу коммиваяжера. Условный яндекс/сбер/2гис и еще миллион бизнесов это сделали давно и молча. Давайте лучше очередного басту/моргенштерна форсить, так честнее
по себе не судят, статья очень интересная
"На последнем этапе вступает особый комбинаторный алгоритм, который решает множественную задачу коммивояжера и строит из полученных малых графов оптимальные маршруты. Это полностью разработка отдела геоаналитики Альфы."
То есть по теме статьи ничего не пишем? Какой-то алгоритм :) Для меня, как алгоритмиста, это кликбейтная статья. K-Means-constrained - это лабораторная работа для студентов.
Дожили, теперь успешное решение задачки для студента 3ого курса - гордость многомилардной корпорации...
Это не простая задачка. Пытаюсь решить подобную. Студенты и не рвутся и не могут ее решить.
Хорошо, когда крупные структуры начинают слезать с иглы зависимостей от API
Пересесть с иглы API на лицо разработчика. #нивкакиерамки
Согласен
Насыщенный курс по теории графов слушал в вузе лет 8 назад, профессор очень толковый. Если бы теорию подкреплял примерами задач из web и логистики, бизнеса в целом... Думаю увлекло бы совсем иначе. Спасибо за статью.
А в расчёте как-то учитывается дорожная обстановка и дата/время посещений?
Так же не понятно, что произойдет, если много точек окажутся вне границ кластеров, но не рядом, а в удаленных зонах? Например по 1 точке в пригородах, а ехать туда экономически не выгодно
Данные о дорожной обстановке пока не учитываем — это в планах, как и учёт других внешних факторов.
Один из примеров, как быть в ситуации, которую вы описали во втором вопросе — используем дополнительную кластеризацию или перераспределим заказ, чтобы его подхватил менее нагруженный или географически наиболее близкий сотрудник.
Комментарий удален автором поста
Зачем было так заморачиваться и тратиться на разработку, когда на рынке есть готовый зрелый продукт Relog для этих задач?
NIH - Синдром же))
NIH == Not Invented Here - изобретено не у нас, синдром неприятия чужой разработки.
Если память мне не изменяет, то у Яндекса подобный инструмент сто лет как существует и он также доступен за денежку. Называется "Яндекс Маршрутизация". Так что расходимся. Ничего нового))
Устал продираться через скучный технический текст. Благодаря этому всему теперь быстрее будут доставлять? Так в Альфе и так быстро доставляли, что поменялось?
Теперь будем ещё быстрее 🚀
Решить задачу коммивояжера на 4-10 "городов" это, конечно, не rocket science, но все равно приятно, что коммерческие предприятия занимаются этим.
С промежуточной кластеризацией решение все равно получается эвристическим, так что я бы лучше сразу использовал эвристику для решения множественной задачи коммивояжера. Например, для вашей задачи можно использовать алгоритм муравьиных колоний (Ant Colony Optimization). Количество муравьев на каждой итерации соответствует числу сотрудников, муравьи стартуют с места жительства сотрудников и пытаются обойти "города" в соответствии с теми ограничениями, что вы наложили. При этом помимо ограничений на граф, вы можете динамически поддерживать ограничения такие как максимальное число "городов" у каждого сотрудника, или задать набор навыков у сотрудника и набор навыков требуемого для каждого "города", тогда "муравьи"-сотрудники смогут выбирать только те, "города" которые соответствуют их навыкам.
Как на это ответит Альфа банк? 😅
После доставки карты жене и детской карты сломался перевод по СБП, нельзя перевести теперь не жене, ни ребенку. Звонки в поддержку и попытки разобраться непосредственно в офисе ни к чему не привели. Высокие технологии столнулись с человеческим фактором)
Некогда чинить рутинные проблемы, велосипедостроение намного интереснее!
Напишите, пожалуйста, ваши ФИО и дату рождения нам в личные сообщения. Во всём разберёмся.
При этом ближайшая дата доставки карты в моем городе была через 20 дней, приходилось 3 раза переносить потому что он на выбор давал всего 2 даты. Лучше уж бы выдавали карты в отделениях. Своего курьера я за 2 месяца не дождался. У тинькоффа такого не было.
Здравствуйте!
Чтобы разобраться в этой ситуации, понадобятся ваши данные. Проверьте личные сообщения, мы запросили всё там.
Ничего нового не придумали.
Банк во всех направлениях гавно, особенно для ИП, не ведитесь на типа инновации ))))))
Ну в яндексе я давно не видел чтобы не было отображения препятствий, только если это сбои в навигации, и, в основном в центре города, но раньше они конечно страдали от этого. Когда до каршеринга, например, нужно было действительно переплыть реку для начала
А потом ещё и через парки и скверы до дома доехать) Но тут речь о другом совершенно в статье)
Интересно было бы послушать мнение представителей на этот счет
Ага, что может быть интереснее, чем почитать мнение банковского курьера на портале про венчурный капитал. Это ведь всё еще портал про венчурный капитал?
Хочешь сделать хорошо - сделай сам
Хочешь быстро зарелизить, возьми готовое..
Интересно узнать ещё время/трудо/финансо затратность для каждой из технологии, объективно у яндекса больше заказов в разы, какое процентное соотношение косяков у каждой из систем
А почему Подели стало многим отказывать без всяких причин, и тем кто без просрочек 10+ рассрочек закрыл?
Сервис Подели — сторонний, поэтому о причинах лучше уточнить в их службе поддержки.
В алгоритме еще наверняка не присутствует "обратная связь" с клиентом. Предположим, что клиенту не важно в какой день недели вечером ему доставят карточку. Но форма выбора слота времени доставки не предлагает ему удобно и быстро указать множество слотов и как следствие теряется оптимальный слот
Комментарий удален модератором
Комментарий удален модератором
Интересно. А курьеры на машинах ездят или на общественном транспорте, велосипедах/самокатах? Как решается задача, когда точки по карте близко, но на деле транспорта между ними нет, а пешком далеко? Или наоборот, пешком можно пройти, а на машине крюк в 3 км?
Наши сотрудники отправляются на встречу с клиентами, пешком, общественном транспорте или автомобиле.
Мы заранее составляем маршруты так, чтобы они были оптимальными, и все запланированные заявки выполнялись вовремя.
А как же пионеры - тинькофф?
Комментарий недоступен
Aha bank its not take by allianze? i see some employe who have onlyfans in web https://criew.com
Комментарий недоступен
Задача для первокурсника любой ит специальности из курса дискретки.
Статья интересная, аж молодость и злосчастная дискретная математика вспомнились. А по поводу практического применения, может в Мск и других вышеупомянутых городах это заработало, но в СПб жене карту принесли на 3-й день после оговоренной даты доставки, но там как будто человеческий фактор. Внимание курьер просил подъехать в нужный (внимание! ) ему район в назначенную для вручения дату, на следующий день не брал трубку, пришлось через горячую линию добиваться новой доставки. Может быть первый под солями был, Питер все же.
Отличная стать! Но комментарии к статье, особенно разбирающихся и понимающих лучше)) плюс нравится мне переходить по рекламе всяких альф и сберов , виси своё заработал)) в общем, все огромные молодцы. Альфой не пользовался , не рекомендуют альфу люди.
Удивляет, что после всех историй как у вас курьеры фотки клиентов с паспортом сливали, кто-то таки доверяет доставке карт от вас вообще.
В Рокетбанке такое делали лет 5 назад 😂 ко мне в команду приходил работать человечек из альфы. Бедолага, пока был в альфе, катался из одного конца города в другой.
В рокете уже тогда алгоритм сам раскидывал все встречи с клиентами, а специальный человек утром проверял и если что фиксил за 1-2 минуты, чтобы представители были равномерно нагружены без разброса адресов. Остался бы Рокет — уделали бы всех на рынке доставки банковских продуктов.
Быстро доставим, а вот чтобы отключить плечи в альфа-инвестициях, идите в офис.
Мдааа, в БКС то все дистанционно через приложение можно сделать. Видимо не дошли некоторые до этого
А есть тут такие настройки, чтобы ввести слово Альфа и никогда не видеть публикации этого г….. банка ?
Альфа банк сделал собственную систему маршрутизации. А норм систему в отделениях не сделал.
Пришел вчера за картой, эл. очередь не работает, просидел в живой 50 минут, встал и ушел, ожидания еще часа на 1,5
Приветствуем!
Можем помочь не сразу, если к нам обратилось много клиентов. Извините, что заставили ждать.
Хотим разобраться и решить вопрос, уже запросили данные в личных сообщениях. Ждём вашего ответа 🙏
зачем нужны доставки карт или их выдача в офисе, если вы их тупо не выдаете?
имеется в виду отказ в выдаче Премиум карты, из-за того что я честно сказал что прямо сейчас вам налик заносить не буду в банк, а налик у меня освобждался через пару мес.
я вашему менеджеру по работе с Премиум клиентами озвучил, что она позорит банк, у меня есть две премиум карты, я без сопливых сам решу когда и сколько мне заносить денег
у вас оборзевшие менеджеры )))))
в общем Альфа в очередной раз облажался как банк
ну а что, зачем вам клиенты с бабками и с мозгом?
гораздо прикольнее лопушков без бабок окучивать ))))))))))))
Статья интересная, спасибо!
Но так и не понял, откуда взялось 1300 городов, если в РФ их, если верить вики, 1119. Или это на несколько стран?