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

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

Принципы работы алгоритма

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

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

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

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

  • Ограничения делятся на 2 вида: жесткие и мягкие. Жесткие ограничения нарушать нельзя, стоимость нарушения мягких ограничений задается через штрафы (перечень штрафов см. в разделе Информация о штрафах при маршрутизации).

    Примеры жестких ограничений:

    Примеры мягких ограничений:

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

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

Пример

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

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

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

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

Особенности планирования

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

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

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

Написать в службу поддержки
Предыдущая
Как работает алгоритм планирования
Следующая
Информация о штрафах при маршрутизации