Алгоритм маршрутизации
Алгоритм планирования решает vehicle routing problem — строит оптимальные маршруты для парка транспортных средств.
Принципы работы алгоритма
Алгоритм начинает строить маршрут в рамках заданных параметров и постепенно меняет его, чтобы найти наиболее оптимальный вариант:
- Алгоритм строит маршрут.
- Алгоритм вносит изменения в решение.
- Новое решение сравнивается с предыдущим.
- Если изменение улучшает решение, алгоритм принимает его. Если маршрут ухудшается, алгоритм может принять его, но с меньшей вероятностью. Это зависит от того, насколько сильно решение ухудшилось.
- Процесс повторяется с пункта 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
при разных запусках будет различаться незначительно. -
Перебрать все возможные комбинации маршрутов в принципе невозможно, а время на решение задачи ограничено. Поэтому не всегда возможно найти лучшее решение, но, как правило, такие решения лучше тех, которые формируются вручную (подробнее см. Сравнение планирования логиста и автоматического планирования).