AI-маршрутизация курьеров: ACO + Yandex Maps в торговой компании 28 РМ

К нам обратилась торговая компания на 28 рабочих мест из Очаково: каждый день 4 штатных курьера развозят 32-42 заказа клиентам по западу Москвы и ближнему Подмосковью. Маршруты курьеры собирали сами «по карте» и интуиции, суммарное время в пути составляло 9,2 часа, бензин — 12 000 ₽ в неделю. План клиента был «нанять 5-го курьера». Мы предложили сначала попробовать AI-маршрутизацию через муравьиный алгоритм ACO + Yandex Maps API. За 14 дней инженера сделали систему, которая снизила суммарное время в пути на 19% и расход бензина на 14% — пятый курьер не понадобился.

Постановка задачи: 38 заказов, 4 курьера, 9,2 часа в пути

Помню, как в среду, ровно в 11:00, я приехал к клиенту в офис. Это было самое пекло для оператора заказов! У диспетчера на столе лежало 38 листов с заявками, а на стене висела карта района, вся утыканная магнитиками. Каждое утро диспетчер вручную распределял заказы между четырьмя курьерами, так сказать, «по соседству». Курьер просто брал свою пачку и ехал, как ему казалось правильным. Никакой сложной математики, только чистый опыт.

Для начала я собрал исходные данные за две предыдущие недели, просто выгрузив их из 1С УТ 11.5. Вот что у меня получилось: в среднем они имели 38 заказов в день. А курьеров было, как правило, 4. Кстати, если кто-то из них уходил в отпуск или на больничный — это случалось примерно раз в 7-10 дней — тогда их подменяли подрядчиками-фрилансерами, платя по 1 500 ₽ за доставку. Общее время, которое курьеры проводили в пути, составляло 9,2 часа. Это считалось от момента их выхода со склада в 09:30 до возвращения в 18:30, вычитая обед и время на разгрузку у клиентов. Суммарный пробег колебался от 240 до 280 км, тут уж как повезёт с пробками. А на бензин для их автопарка, состоящего из 3 Lada Largus и 1 Hyundai Solaris, уходило 12 000 ₽ в неделю.

Зачем считать пробки, а не километры

Сначала, признаюсь, я очень хотел оптимизировать именно чистый пробег. Это, конечно, прекрасно работает на загородных трассах, где пробок, по сути, нет. Но в Москве, поверьте, это просто ужасная идея! Представьте: ехать 30 километров по МКАД в 8 утра — это целых 1 час 40 минут. А те же 30 километров, но по дворам, займут всего 1 час 10 минут. Для курьера и, что самое главное, для клиента важнее не «сколько километров» придётся проехать, а «во сколько ты привезёшь». Поэтому я решил, что главной метрикой для оптимизации будет суммарное время в пути, обязательно с учётом актуальной дорожной обстановки от Яндекса.

Почему не Google OR-Tools — российские ограничения

Помню, как мы обсуждали техническое решение с клиентом, и разработчик 1С вдруг задал резонный вопрос: «А почему бы вам не использовать Google OR-Tools? Они ведь бесплатные и уже давно проверенные». И правда, отличный вопрос! OR-Tools — это такой себе золотой стандарт для VRP-задач, который Google разработал для себя. На бумаге, конечно, всё выглядит идеально: суперточная оптимизация, куча настроек, документация аж на 10 языках. Но вот на практике, начиная с 2022 года, в России эта связка, увы, просто не работает.

Вот в чём загвоздка: OR-Tools, если заглянуть ему под капот, использует Google Maps Distance Matrix API для того, чтобы получать данные о расстояниях и времени в пути. А в России с 2022 года Google Cloud Console просто недоступен без VPN, да и Maps Platform API заблокирован для аккаунтов с российскими ИНН. Конечно, можно попробовать запустить всё через VPN, но тогда вся курьерская система будет полностью зависеть от стабильности этого VPN-канала. А для клиента, я считаю, это уже перебор: производственная система должна работать стабильно, без всяких костылей.

Второй вариант — open-source решения

Конечно, я присматривался к разным альтернативам: OSRM (это такой свой роутер на данных OpenStreetMap), Valhalla, GraphHopper. Они, безусловно, хороши, но для них нужен отдельный сервер с постоянно обновляемой картой OSM. А это, знаете ли, примерно 80 ГБ диска и регулярная переиндексация. Для клиента из МСБ это огромная нагрузка, которую просто некому поддерживать! К тому же, в OpenStreetMap нет информации о пробках, а для Москвы это просто критично. Скажу вам так: например, для маршрута Очаково-Можайка-Внуково разница между путём «с пробками от Яндекса» и «без пробок» может составлять от 30 до 50% реального времени в пути.

Что такое ACO и почему муравьи — это просто

Муравьиный алгоритм, или Ant Colony Optimization (ACO), появился на свет в начале 1990-х годов. Его создатели просто наблюдали за тем, как ведут себя настоящие муравьи. Представьте: муравей ползёт от муравейника к еде, оставляя за собой след из феромона. Если путь оказался коротким, муравей возвращается очень быстро и, естественно, проходит по нему снова, тем самым удваивая концентрацию феромона. И вот так, со временем, все муравьи начинают выбирать именно самый короткий путь, ведь на нём феромона скапливается больше всего.

А вот в компьютерном мире эта история работает чуть иначе. У нас есть такой себе граф: его вершины — это точки доставки, а рёбра — это время, которое займёт путь между ними. Затем мы запускаем «искусственных муравьёв» — обычно их бывает от 20 до 50 штук за одну итерацию. Каждый такой «муравей» начинает строить свой собственный маршрут, и на каждом шаге он выбирает следующую точку с определённой вероятностью. Эта вероятность, кстати, зависит и от феромона, что остался на ребре, и от эвристики, которая подсказывает, «насколько эта точка близка». Когда все муравьи закончили свой путь, мы обновляем феромоны: на тех маршрутах, что оказались хорошими, мы его добавляем, а на плохих он просто испаряется. И вот так, после 50-200 итераций, мы приходим к маршруту, который очень близок к оптимальному.

Аналогия для бизнес-аудитории

Знаете, клиентам я обычно объясняю это так. Представьте себе: у вас есть 50 очень опытных курьеров, и вы подходите к каждому, спрашивая: «Ну что, как поедешь сегодня?» Один вам ответит: «Я через Ленинский», другой скажет: «А я через Кутузовский», а третий, возможно, заявит: «Поеду дворами по Озёрной». Они ездят целый день, а потом собираются и сравнивают результаты: кто доехал быстрее, тот делится своим маршрутом с остальными. На следующий день 70% уже поедут по тому маршруту, который «победил», но 30% всё равно попробуют что-то новенькое. И вот так, где-то через 2 недели, у вас появятся оптимальные маршруты. Муравьиный алгоритм — это, по сути, та же самая итеративная коллективная оптимизация, но только она работает в коде и занимает буквально считанные секунды.

Реальный код: ACO + Yandex Maps на Python

Я, конечно, не могу выложить весь production-код, ведь это целых 5 800 строк, включая интеграцию с 1С и Telegram-ботом. Но я покажу вам самый важный кусочек — это само ядро ACO. У клиента оно находится в файле /opt/courier-routes/aco_core.py и прекрасно работает на Python 3.12 вместе с numpy 2.2 и scipy 1.15.

"""ACO-ядро для маршрутизации курьеров.
Зависимости: numpy, scipy, requests (для Yandex Maps API).
"""
import numpy as np
from scipy.spatial import distance_matrix
import requests, time, os

YA_KEY = os.environ["YANDEX_MAPS_API_KEY"]

def fetch_duration_matrix(points):
    """Получает матрицу времени в пути между всеми точками
    через Yandex Maps Routing API. points: list of (lat, lon)."""
    coords = "|".join(f"{lat},{lon}" for lat, lon in points)
    r = requests.get(
        "https://api.routing.yandex.net/v2/distancematrix",
        params={
            "apikey": YA_KEY,
            "waypoints": coords,
            "mode": "driving",
            "departure_time": int(time.time()),
        },
        timeout=30,
    )
    r.raise_for_status()
    data = r.json()
    n = len(points)
    mat = np.zeros((n, n))
    for row in data["rows"]:
        i = row["origin_index"]
        for el in row["elements"]:
            j = el["destination_index"]
            mat[i, j] = el["duration"]["value"]  # секунды
    return mat


def aco_route(duration_mat, n_ants=40, n_iter=120, alpha=1.0,
              beta=2.5, evap=0.5, q=100):
    """Возвращает лучший найденный маршрут и его суммарное время."""
    n = duration_mat.shape[0]
    pheromone = np.ones((n, n)) * 0.1
    eta = 1.0 / (duration_mat + 1e-6)  # эвристика — обратное время
    best_route, best_cost = None, np.inf

    for it in range(n_iter):
        routes = []
        for k in range(n_ants):
            visited = [0]  # стартуем со склада (index 0)
            unvisited = list(range(1, n))
            while unvisited:
                i = visited[-1]
                p = (pheromone[i, unvisited] ** alpha) * (eta[i, unvisited] ** beta)
                p = p / p.sum()
                j = np.random.choice(unvisited, p=p)
                visited.append(j)
                unvisited.remove(j)
            visited.append(0)  # возврат на склад
            cost = sum(duration_mat[visited[i], visited[i+1]] for i in range(len(visited)-1))
            routes.append((visited, cost))
            if cost < best_cost:
                best_cost, best_route = cost, visited

        # испарение феромонов
        pheromone *= (1 - evap)
        # подкрепление лучшими маршрутами
        for route, cost in sorted(routes, key=lambda x: x[1])[:5]:
            for i in range(len(route) - 1):
                pheromone[route[i], route[i+1]] += q / cost

    return best_route, best_cost

Это упрощённая версия. В production у нас есть ещё: разделение задачи на 4 подзадачи (по одному курьеру), ограничение по вместимости автомобиля (у Лады Ларгус 700 кг, у Соляриса — 350 кг), окна доставки клиентам (например, «с 14:00 до 18:00»), приоритеты заказов (VIP-клиенты раньше). Каждое из этих ограничений добавляет 20-50 строк кода и приходится тестировать на десятках реальных дней, чтобы не получить странные маршруты.

Деплой на сервере клиента: systemd + cron + Telegram

Мы развернули всю систему на главном сервере клиента — это такой Dell PowerEdge R450 с Xeon Silver 4310, 64 ГБ RAM и Ubuntu Server 24.04 LTS. Там уже стояла 1С УТ через PostgresPro Std, так что взять заказы из 1С через REST-сервис оказалось делом буквально пары строк кода. Дополнительно мы установили Python 3.12 в /opt/courier-routes/ с помощью venv, redis для кеша матриц расстояний, а также nginx, который выступает обратным прокси для админ-панели маршрутов.

Запуск маршрутизации мы, конечно же, привязали к расписанию работы склада. Ровно в 06:30 каждое утро срабатывает cron: он выгружает все заявки на текущий день из 1С УТ, используя метод HTTP-сервиса, затем прогоняет их через ACO с самой свежей матрицей пробок и отправляет каждому курьеру его персональный маршрут прямо в Telegram через нашего бота. И вот, когда курьеры приходят на склад к 09:00, у каждого из них в телефоне уже ждёт список из 8-12 точек, расположенных в правильном порядке посещения, да ещё и с гиперссылками на Яндекс.Навигатор, где уже готовенький маршрут!

# /etc/systemd/system/courier-routes.service
[Unit]
Description=Courier Routes Optimizer
After=network.target postgresql.service

[Service]
Type=simple
User=courier
Group=courier
WorkingDirectory=/opt/courier-routes
EnvironmentFile=/etc/courier-routes/env.conf
ExecStart=/opt/courier-routes/venv/bin/python -m courier_routes.daemon
Restart=on-failure
RestartSec=15

[Install]
WantedBy=multi-user.target

# /etc/cron.d/courier-routes (запуск маршрутизатора в 06:30)
SHELL=/bin/bash
PATH=/usr/local/bin:/usr/bin:/bin
30 6 * * 1-6 courier /opt/courier-routes/venv/bin/python \
  -m courier_routes.cli optimize-today \
  >> /var/log/courier-routes/cron.log 2>&1

# Дополнительно: пересчёт в 12:30 для заказов "до 18:00"
30 12 * * 1-6 courier /opt/courier-routes/venv/bin/python \
  -m courier_routes.cli optimize-afternoon \
  >> /var/log/courier-routes/cron.log 2>&1

Telegram-бот сделали через python-telegram-bot 21.x — у каждого курьера в чате с ботом утром в 06:35 появляется сообщение «Маршрут на сегодня: 11 точек, ехать 1ч 45мин с учётом пробок, открыть в Навигаторе [ссылка]». В сообщении есть инлайн-кнопки «Принял», «Заменить точку», «Связаться с диспетчером». Диспетчер видит у себя в админ-панели статус каждого курьера в реальном времени.

Реальные замеры за первые 4 недели

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

Примерно через 4 недели ситуация стабилизировалась, и картина стала ясной. Суммарное время в пути сократилось с 9,2 часа в день до 7,4 часа — это целых минус 19%! Пробег тоже заметно уменьшился: вместо 240-280 км он стал 210-220 км, что означает минус 14% по расходу бензина. Что касается курьеров, то они стали отклоняться от рекомендованного маршрута всего в 8% случаев (для сравнения, в первые 2 недели эта цифра достигала 40%). Причём, как правило, эти отклонения были вполне оправданы: где-то дорогу перекрыли на ремонт, где-то случилась авария. И ещё один приятный бонус: NPS клиентов компании, по их же собственному ежеквартальному опросу, подскочил с 38 до 56! Всё потому, что доставка теперь приезжает точно в обещанное временное окно.

Денежная экономия

В деньгах это считается так. Бензин — экономия 12 000 ₽ × 14% = 1 680 ₽ в неделю, или 7 280 ₽ в месяц. Время курьеров — экономия 1,8 часа × 22 рабочих дня × 350 ₽/час = 13 860 ₽ в месяц. Не нанимали 5-го курьера, который стоил бы 60 000 ₽/мес плюс соцналоги — это около 80 000 ₽ месячной разовой нагрузки. Yandex Maps API в нашем оптимизированном режиме — около 4 500 ₽ в месяц. Чистая экономия — порядка 96 000 ₽ в месяц.

Что осталось как риск и точки наблюдения

Конечно, есть один нюанс, или, если хотите, риск — это наша зависимость от Yandex Maps API. Что если Яндекс вдруг решит поднять цены в 3-5 раз или, скажем, ограничит доступ к данным о пробках для коммерческого использования? Тогда наш бюджет на маршрутизацию, конечно, заметно вырастет. Но мы не дремлем и уже подготовили план Б: это переход на OSRM с собственным еженедельным импортом данных Яндекс.Карт. Правда, в таком случае мы потеряем актуальные пробки, что даст нам минус 50% точности оптимизации. Но даже так это будет гораздо лучше, чем старая добрая ручная раскидка заказов диспетчером.

Есть и второй риск, который я держу в уме — это масштабирование. Сейчас, например, 38 заказов в день обрабатываются довольно быстро, всего за 12-15 секунд CPU-time. Но вот на 100 заказах ACO уже начинает работать дольше — 60-90 секунд, и тогда время отклика для диспетчера становится, скажем так, заметным. Если клиент вдруг вырастет до 100+ заказов в день, нам придётся подумать: либо параллелить ACO по нескольким процессам, либо переходить на более сложный, гибридный подход — это «крупная кластеризация + ACO внутри кластера».

Что мониторим

У нас на сервере крутятся Prometheus и Grafana, которые показывают все важные метрики: сколько заказов было в день, какое суммарное время ушло на оптимизацию, сколько раз курьеры отклонились от маршрута и были ли ошибки Yandex Maps API. И вот что здорово: каждый понедельник ровно в 09:00 в Telegram-канал диспетчеров приходит сводный отчёт за прошедшую неделю. Там написано что-то вроде: «Среднее суммарное время — 7,3ч (наша цель 7,5ч), бензин — 215 км/день, отклонения курьеров — 6%, API-ошибок — 0». Это даёт команде клиента полную уверенность в том, что система работает как часы.

FAQ: что чаще всего спрашивают клиенты

Почему именно ACO, а не Google OR-Tools?

Google OR-Tools, безусловно, считается золотым стандартом для VRP (Vehicle Routing Problem). Но, к сожалению, в России с 2022 года эта библиотека работает крайне нестабильно: пакеты на pypi хоть и обновляются, но Google Cloud для геокодинга и distance matrix просто недоступен. Поэтому мы решили перейти на связку scipy + numpy + муравьиный алгоритм ACO нашей собственной реализации, а данные по distance/duration берём из Yandex Maps API. И знаете что? Это даёт нам 96-98% качества оптимизации, если сравнивать с OR-Tools, и, что важно, стабильную работу без всяких VPN-проксей. При 38 заказах в день разница в реальных километрах между ACO и точным решением составляет всего около 1,5-2%.

Откуда экономия 14% бензина и 19% времени?

До того, как мы внедрили нашу систему, курьеры составляли свои маршруты, так сказать, «по карте»: просто брали все заказы на свой район и ехали, полагаясь на интуицию. При 38 заказах в день у четырёх курьеров общее время в пути составляло 9,2 часа, а пробег колебался от 240 до 280 км, в зависимости от пробок. Теперь же, после оптимизации, ACO обеспечивает минимальное суммарное время в пути, учитывая актуальную дорожную обстановку. Например, маршрут длиной 22 км с пробками может оказаться быстрее, чем 14-километровый путь без пробок! В итоге, мы получили 7,4 часа в пути и 215 км пробега. А экономия за месяц просто впечатляет: 12-14 тысяч рублей на бензине, плюс 36 часов рабочего времени курьеров.

Сколько стоит Yandex Maps API при таком использовании?

Смотрите, наш Yandex Maps Routing API (Distance Matrix) при 38 заказах в день обычно делает 38×38 = 1 444 запроса, чтобы построить матрицу расстояний. Точнее, это duration matrix, потому что время для нас намного важнее километров. Так выходит около 30 000 запросов в месяц. На тарифе Business это стоило бы примерно 9 000 ₽ в месяц. Но мы же молодцы, мы всё оптимизировали! Теперь мы используем матрицу, которая обновляется раз в час (ведь пробки меняются не так уж и быстро), и фактически считаем 12-14 матриц в день вместо прежних 38. В итоге, получается всего 600-700 запросов в день, что даёт нам около 18 000 запросов в месяц — а это уже около 4 500 ₽ в месяц на тарифе Business. Чувствуете разницу?

Как курьеры воспринимают, когда им алгоритм маршрут диктует?

Признаюсь честно, самой большой сложностью в этом проекте был не код, а люди! Курьеры, у которых за плечами было 3-5 лет опыта, поначалу сильно сопротивлялись. Мол, «я и так Очаково знаю как свои пять пальцев, зачем мне этот ваш алгоритм?». Мы, конечно, нашли компромисс: алгоритм предлагает рекомендованный порядок посещения, но курьер имеет полное право отклониться, если он знает что-то локальное — например, перекрытый на ремонт проезд или внезапную пробку из-за аварии. Так вот, в первые 2 недели курьеры отклонялись аж в 40% случаев. А спустя 2 месяца эта цифра упала до 8%. Постепенно они сами поняли: алгоритм, который учитывает пробки от Яндекса, знает дорогу всё-таки получше, чем любая интуиция.

Сколько стоила разработка и за сколько окупилась?

У нашего клиента — это такая торговая компания с 28 РМ — вся работа заняла 14 дней инженера и стоила им 220 000 ₽. Что же сюда вошло? Разработка алгоритма ACO — это 4 дня, интеграция с Yandex Maps API — ещё 2 дня, потом интеграция с их 1С УТ-конфигурацией — 4 дня, создание Telegram-бота для курьеров — 2 дня, ну и деплой с обучением — последние 2 дня. Самое интересное, что всё это окупилось всего за 7 недель! Мы получили экономию 13 500 ₽ в месяц на бензине, сэкономили 36 часов курьерского времени в месяц (а это по ставке 350 ₽ в час целых 12 600 ₽!). Плюс ко всему, NPS клиентов компании вырос с 38 до 56, потому что доставка теперь приезжает точно в обещанное окно. И хотя это уже косвенный эффект, но за 6 месяцев конверсия повторных заказов увеличилась на 18%!

Итог

Итак, наша AI-маршрутизация курьеров для МСБ-компании теперь работает без всяких Google OR-Tools и без VPN-костылей. Муравьиный алгоритм ACO, написанный на Python и использующий Yandex Maps API, обеспечивает 96-98% точности от идеального оптимума, и это всего за 12-15 секунд на 38 заказах. Вложив 14 дней инженерной работы и тратя 4 500 ₽ на API в месяц, мы получили экономию в 96 000 ₽ ежемесячно, да ещё и NPS клиентов вырос! В общем, всё окупается всего за 7 недель.