Вернуться назад

Как ИИ помог улучшить в 3,7 раза маршрутизацию курьеров

Задача

Современная Москва всё больше напоминает улицы Нью-Йорка из американских фильмов - на дорогах жёлтые кэбы такси и транспортных компаний, на тротуарах снующие курьеры. Общество "аутсорсит" свои личные перемещения, а ГИС-сервисы позволяют эффективно удовлетворять этот спрос.

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

В апреле 2020 года в Москве у одной очень большой организации появилась срочная задача доставки электронных устройств с определённым программным обеспечением тысячам жителей. Количество граждан, которым нужно было доставить устройство, с каждым днём росло, а курьерами было непостоянное и недостаточное количество волонтёров. Задача маршрутизации перемещений стала критична.

При этом времени на разработку практически не было. Нужно было, как это часто бывает, “вчера”. А организация процессов у заказчика была достаточно слаба, с несогласованностями и банальным хаосом.

Решение

На "входе" у нас были:

  • адреса, по которым нужно было осуществить доставку
  • количество курьеров на авто
  • количество курьеров на общественном транспорте

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

Задачу решали в несколько этапов:

1) Преобразовали адреса в геокоординаты.

2) Отфильтровали адреса, которые по ошибке попали в выборку - не относящиеся к Москве.

3) С помощью машинного обучения сгруппировали адреса по 10-30 штук в зависимости от длины маршрута и способа перемещения курьера. Пример для ~100 групп:

Транспортная система Москвы построена, грубо говоря, расходящимся от центра линиями, поэтому алгоритмы обычно группировали адреса вытянутыми кластерами вдоль шоссе

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

Трудности

Существует множество способов сгруппировать точки и поначалу выбирать наиболее оптимальный пришлось методом проб и ошибок на реальных данных. Примеры работы алгоритмов на разных типах данных:

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

Периодически у заказчика менялась структура курьеров - например, становилось больше пеших. Зачастую эта информация появлялась уже при начале работ, когда некоторые курьеры уже вышли на маршрут. В этом случае нельзя прогонять алгоритм заново и менять всю сетку маршрутов, так же как нельзя отдать автомобильный кластер пешему курьеру. Для этих ситуаций мы добавили в алгоритм возможность разбивать крупные кластеры на части или объединять небольшие кластеры в один.

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

Для экономии времени мы воспользовались услугами Google Directions API для расчёта очерёдности следования. В распечатку для курьеров было добавлено время и суммарная протяжённость маршрута, что также улучшило планирование и позволило точнее договариваться с получателями устройств о времени прибытия.

Результат

Курьеры стали обрабатывать в 3.7 раза больше точек в единицу времени.

Формирование отчёта происходило в течение получаса в автоматическом режиме в отличие от ручного составления неоптимизированных списков в течение нескольких часов.

В следующих статьях мы поделимся другими интересными примерами задач геоаналитики!

Другие статьи по этой теме

Машинное обучение на службе урбанистики

Кейс от эксперта: как обучить нейросеть распознавать кроны деревьев и чем это может быть полезно

Где автомобилисту в Москве купить квартиру? Big Data отвечает

Экспертный анализ транспортной ситуации в столице

Контакты
ООО Селадо

г. Москва, метро Павелецкая, Павелецкая набережная д. 2 стр 3, офис 106, БЦ LoftVille

+7 (495) 003-91-37
Свяжитесь с нами: