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

Алгоритм планирования решает 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 км.

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

Ограничение по дням при планировании

Чтобы пропускная способность склада считалась корректно, на листе Options в параметре max_depot_load_range_days (options.max_depot_load_range_days в API) можно указать диапазон в днях от времени начала его работы. По умолчанию значение параметра равно 7.

За пределами диапазона, указанного в параметре max_depot_load_range_days, пропускная способность склада считается равной нулю.

На расширение диапазона может влиять временное окно работы склада (time_window) и гибкое время старта (flexible_start_time). Если на маршруте есть хотя бы один склад с гибким временем старта (flexible_start_time = true) и мягким временным окном (hard_window = false), начало диапазона сдвигается на 26 часов назад. Если помимо первого склада есть еще хотя бы один с мягким временным окном, конец диапазона сдвигается на 24 часа вперед.

Границы временного окна работы склада могут сдвигаться, например из-за гибкого времени старта. Чтобы учесть эту особенность при расчете пропускной способности, рекомендуем указывать значение max_depot_load_range_days с запасом.

Например, указано временное окно первого склада — с 9:00 до 18:00. При этом параметр flexible_start_time указан как true, а hard_window указан как false. У второго склада на маршруте hard_window указан как false. В этом случае диапазон планирования увеличится на 50 часов (26 часов назад от 9:00 и 24 часа вперед от 18:00).

Пример 1

Нужно выполнить заказ, для которого указано временное окно time_window = 10.10:00:00-10.16:00:00. Это значит, что доставить такой заказ можно только на 10 день от текущей даты планирования.

Для склада задано общее время работы time_window = 1.23:00:00-12.22:59:00 и мягкое временное окно (hard_window = false). Значение параметра max_depot_load_range_days явно не указано. По умолчанию оно равно 7 дням.

В результате планирования курьер 3 посещает склад на 9 день, после чего следует длительный период ожидания перед доставкой заказа. Это происходит из-за того, что алгоритм не может корректно рассчитать маршрут.

Пример Excel ⋅ Запрос API (JSON) ⋅ Ответ API ⋅ Открыть на карте

Пример 2

Те же условия, что в примере 1, но значение параметра max_depot_load_range_days равно 9 дням.

В результате курьер 3 посещает склад на 10 день и без ожидания приступает к выполнению заказа.

Пример Excel ⋅ Запрос API (JSON) ⋅ Ответ API ⋅ Открыть на карте

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

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

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

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