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

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

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

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

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

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

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

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

• Поэтому целевая функция состоит из 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 при разных запусках будет различаться незначительно.

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