Как машинное обучение повысило эффективность курьеров в 3.7 раза
Современная Москва всё больше напоминает улицы Нью-Йорка из американских фильмов - на дорогах жёлтые кэбы такси и транспортных компаний, на тротуарах снующие курьеры. Общество "аутсорсит" свои личные перемещения, а ГИС-сервисы позволяют эффективно удовлетворять этот спрос.
Задача
С вводом карантинных мер и увеличением доли дистанционной работы курьерские службы часто становились бутылочным горлышком, ограничивая возможности компаний. А в убероподобных сервисах оптимальная логистика - один из важнейших критериев достижения успеха.
В апреле 2020 года в Москве у одной очень большой организации появилась срочная задача доставки электронных устройств с определённым программным обеспечением тысячам жителей. Количество граждан, которым нужно было доставить устройство, с каждым днём росло, а курьерами было непостоянное и недостаточное количество волонтёров. Задача маршрутизации перемещений стала критична.
При этом времени на разработку практически не было. Нужно было, как это часто бывает, “вчера”. А организация процессов у заказчика была достаточно слаба, с несогласованностями и банальным хаосом.
Решение
На "входе" у нас были:
- адреса, по которым нужно было осуществить доставку
- количество курьеров на авто
- количество курьеров на общественном транспорте
На "выходе" мы должны были сформировать группы адресов с минимальными перемещениями внутри них, по принципу один курьер - одна группа, для автомобилей и для пеших курьеров в соответствии с их количеством.
Задачу решали в несколько этапов:
1) Преобразовали адреса в геокоординаты.
2) Отфильтровали адреса, которые по ошибке попали в выборку - не относящиеся к Москве.
3) С помощью машинного обучения сгруппировали адреса по 10-30 штук в зависимости от длины маршрута и способа перемещения курьера. Пример для ~100 групп:
Группы с перемещениями на десятки километров отдавались автомобилистам и изначально создавались с небольшим количеством адресов, небольшие по площади кластеры внутри МКАДа брали пешие курьеры, а многоадресные группы в 30 точек создавались только внутри МКАДа и передавались только автомобилистам.
Трудности
Существует множество способов сгруппировать точки и поначалу выбирать наиболее оптимальный пришлось методом проб и ошибок на реальных данных. Примеры работы алгоритмов на разных типах данных:
Во-вторых, любой алгоритм абстрактен и не понимает с чем имеет дело. Иногда пешему курьеру присваивались группы с малым количеством адресов, но большие по расстоянию, даже внутри МКАДа. На начальном этапе для решения этой проблемы добавили метрику площади каждой группы адресов, по которой алгоритм судил о физическом размере.
Периодически у заказчика менялась структура курьеров - например, становилось больше пеших. Зачастую эта информация появлялась уже при начале работ, когда некоторые курьеры уже вышли на маршрут. В этом случае нельзя прогонять алгоритм заново и менять всю сетку маршрутов, так же как нельзя отдать автомобильный кластер пешему курьеру. Для этих ситуаций мы добавили в алгоритм возможность разбивать крупные кластеры на части или объединять небольшие кластеры в один.
Иногда вставали неожиданные преграды: курьеры не обладали наглядной и цельной информацией, так как у курьеров был просто список с адресами. По ряду причин, касающихся вопросов безопасности, вся информация передавалась курьерам в бумажном виде - очередная база данных в даркнете никому не нужна. Поэтому порядок адресов также нужно было определить алгоритмом.
Для экономии времени мы воспользовались услугами Google Directions API для расчёта очерёдности следования. В распечатку для курьеров было добавлено время и суммарная протяжённость маршрута, что также улучшило планирование и позволило точнее договариваться с получателями устройств о времени прибытия.
Результат
Курьеры стали обрабатывать в 3.7 раза больше точек в единицу времени.
Формирование отчёта происходило в течение получаса в автоматическом режиме в отличие от ручного составления неоптимизированных списков в течение нескольких часов.
В следующих статьях мы поделимся другими интересными примерами задач геоаналитики!