Алгоритм маршрутизации курьеров в доставке¶

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

¶Постановка задачи

В формальном виде задача маршрутизации сводится к классической проблеме коммивояжёра (TSP) и её многоагентному расширению — задаче маршрутизации транспорта (VRP). Для доставки курьерами характерны следующие ограничения и условия:

• наличие нескольких курьеров (агентов) с различной грузоподъёмностью и зонами работы;
• временные окна доставки (клиент ожидает заказ в определённый интервал);
• приоритетность заказов (срочные, платные, негабаритные);
• пробки, дорожные ограничения, пешеходные зоны;
• динамическое поступление новых заказов в режиме реального времени.

Целевой функцией чаще всего выступает минимизация суммарного пробега, времени выполнения или затрат на топливо/оплату труда, при условии соблюдения всех ограничений.

¶Основные классы алгоритмов

¶Точные методы

Точные алгоритмы (метод ветвей и границ, динамическое программирование, целочисленное линейное программирование) гарантируют нахождение глобального оптимума. Однако их вычислительная сложность растёт экспоненциально с числом точек, поэтому на практике они применяются только для малых задач (до 20–30 заказов) или в гибридных схемах.

¶Эвристические методы

Эвристики строят решение быстро, но без гарантии оптимальности. К ним относятся:

• Жадные алгоритмы — последовательное добавление ближайшей точки к текущему маршруту. Просты и быстры, но дают результат, в среднем на 15–25 % хуже оптимального.
• Метод Кларка — Райта (экономия по объединению маршрутов) — классическая эвристика для VRP, используемая как стартовая точка для улучшения.
• Алгоритмы локального поиска — 2-opt, 3-opt, перестановки, которые итеративно улучшают текущее решение путём обмена рёбер или вершин.

¶Метаэвристики

Метаэвристики позволяют выйти из локальных оптимумов и применяются для задач с десятками и сотнями точек:

• Генетические алгоритмы — моделируют естественный отбор, оперируя популяцией решений.
• Имитация отжига — вероятностный поиск, допускающий временное ухудшение решения.
• Муравьиные алгоритмы (ACO) — имитируют поведение колонии муравьёв при поиске пищи.
• Роевой интеллект (PSO) и поиск с запретами (Tabu Search).

В промышленных системах чаще всего применяют гибридные схемы: быстрая эвристика для старта + метаэвристика для улучшения + локальный поиск для финализации.

¶Машинное обучение

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

¶Динамическая маршрутизация

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

• Перепланирование (re-optimization) — полный пересчёт всех маршрутов с нуля.
• Инкрементальная вставка — добавление нового заказа в существующий маршрут с локальной проверкой наилучшей позиции.
• Зонирование — предварительное разбиение города на кластеры, закреплённые за конкретными курьерами, что сокращает размерность задачи.

¶Типичная архитектура системы

Алгоритм маршрутизации встраивается в программный комплекс, включающий:

1. Модуль геокодирования — преобразование адресов в координаты.
2. Матрицу расстояний — расчёт времени и дистанции между точками с учётом дорожной сети и пробок (на основе данных картографических сервисов).
3. Оптимизатор — ядро, реализующее выбранный алгоритм.
4. Модуль назначения — распределение заказов между курьерами.
5. Мобильное приложение курьера — отображение маршрута и приём статусов.

¶Применение и ограничения

Алгоритмы маршрутизации используются в сервисах доставки еды (Яндекс Еда, Delivery Club), экспресс-доставки (СДЭК, Boxberry), логистических платформах (Axelot, 1С:TMS). Эффективность внедрения оценивается в снижении пробега на 10–30 % и сокращении времени доставки на 15–25 %.

Ограничения алгоритмов связаны с качеством входных данных (точность геокодирования, актуальность пробок), случайными факторами (отказ клиента, отсутствие парковки) и поведением курьеров, отклоняющихся от предписанного маршрута. Для учёта этих факторов применяются корректирующие коэффициенты и обратная связь по фактическим трекам.

¶Источники

• Toth P., Vigo D. Vehicle Routing: Problems, Methods, and Applications. — SIAM, 2014.
• Канторович Л. В. Математические методы организации и планирования производства. — 1939.
• Документация открытой библиотеки OR-Tools (Google).
• Статьи и публикации компании Яндекс о логистических алгоритмах.