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

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

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

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

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

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

Примечание

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

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

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

  • Поэтому целевая функция состоит из 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 км.

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

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

По умолчанию алгоритм корректно строит маршрут в диапазоне до 7 дней от времени начала работы склада.

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

Пример

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

Важно

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

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

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

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

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

Написать в службу поддержки