Алгоритм маршрутизации

Алгоритм планирования решает vehicle routing problem — строит оптимальные маршруты для парка транспортных средств.

Для чего нужен алгоритм

Алгоритм заменяет ручное планирование и одновременно учитывает множество факторов: пробки, расстояния, время работы курьеров, сроки доставки и другие. Это помогает:

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

Что учитывает алгоритм

Алгоритм строит маршруты на основе реальных данных и учитывает:

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

Как алгоритм выбирает решение

Алгоритм ищет решение с учетом целевой функции и заданных ограничений.

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

• общий пробег и время выполнения маршрута;
• количество и время опозданий;
• кучность и сбалансированность маршрутов между курьерами.

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

1. Стоимость используемых ресурсов (автомобилей, курьеров).
2. Стоимость нарушения ограничений (штрафы за нарушения).

В итоге оптимизируется их сумма в метрике total_cost_with_penalty. Чем она меньше, тем оптимальнее решение.

Стоимость используемых ресурсов для оптимизации задается параметром cost (подробнее см. в разделах Стоимость автомобиля или курьера и Расширенные настройки стоимости). Фактические затраты можно указать в отдельном поле, которое не участвует в оптимизации, см. Расчет выплаты курьеру.

При поиске оптимального решения алгоритм замещает одну физическую характеристику маршрутов на другую, используя их стоимость. Например, уменьшение количества автомобилей на маршруте может привести к увеличению пробега, но при этом значение total_cost_with_penalty уменьшится. Также уменьшение количества автомобилей может повлечь за собой увеличение количества и времени опозданий.

Пример

У компании есть 2 курьера, которым нужно доставить 2 заказа. Первый заказ находится в 12 километрах от склада, второй — в 20. Между заказами 10 километров. Первый заказ нужно доставить в интервале с 9:00 до 10:00; второй — с 8:30 до 9:00.

Доступно несколько решений:

• 1 курьер доставляет оба заказа с опозданием в 20 минут, пробег 22км;
• 1 курьер доставляет оба заказа без опозданий, пробег 30 км;
• 2 курьера развозят по одному заказу без опозданий, пробег 32 км.

Выбор варианта зависит от стоимости использования автомобиля, стоимости опозданий, необходимости задействовать всех курьеров и т. д.

Ограничения

Ограничения делятся на два вида:

Как работает алгоритм

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

1. Строит начальный вариант маршрута.
2. Вносит изменения в решение. Например, меняет порядок заказов.
3. Сравнивает новое решение с предыдущим.
4. Если изменение улучшает решение, алгоритм принимает его. Если маршрут ухудшается, алгоритм может принять его, но с меньшей вероятностью. Это зависит от того, насколько сильно решение ухудшилось.
5. Повторяет процесс с пункта 2 до тех пор, пока не найдет наиболее оптимальный вариант.

Особенности работы алгоритма

• Поиск решения носит вероятностный характер, поэтому при одинаковых исходных данных могут получиться разные маршруты. Однако целевая метрика total_cost_with_penalty при разных запусках будет различаться незначительно.

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

• Максимальный диапазон корректного построения маршрута — 7 дней. Для более длительных маршрутов используйте параметр max_depot_load_range_days — он помогает корректно считать пропускную способность склада. Подробнее читайте в разделе Пропускная способность склада при многодневных маршрутах.

Дополнительную информацию о работе алгоритма маршрутизации см. в статье Яндекс Маршрутизация: как мы окунулись в логистику и решили поменять будущее.