Задача маршрутизации транспорта (VRP): временные окна, ограничения по вместимости и эвристики

Базовая математическая формулировка — задача маршрутизации транспорта с ограниченной вместимостью (Capacitated VRP, CVRP). В этой модели каждый клиент имеет определенный объем спроса (например, вес или паллеты груза), а каждый грузовик в депо обладает строго фиксированной максимальной грузоподъемностью. Целевая функция заключается в минимизации суммарного пробега всех автомобилей. Ограничения требуют, чтобы каждый клиент был посещен ровно одним грузовиком ровно один раз, и сумма грузов на каждом маршруте не превышала вместимости автомобиля. Поиск абсолютно точного решения (методами отсекающих плоскостей или генерации столбцов) возможен лишь для сетей до 100-200 клиентов; для более масштабных систем требуются мощные приближенные алгоритмы.

Исторически первым и самым знаменитым эвристическим подходом к CVRP стал алгоритм сбережений Кларка-Райта (Clarke-Wright Savings Algorithm), разработанный в 1964 году. Этот жадный алгоритм начинает работу с тривиального (и очень невыгодного) решения: к каждому клиенту из депо отправляется отдельный грузовик и возвращается обратно. Затем алгоритм вычисляет матрицу сбережений (savings) для каждой пары клиентов: сколько километров мы сэкономим, если объединим два маятниковых маршрута в один кольцевой, посетив двух клиентов подряд. Отсортировав эти сбережения по убыванию, алгоритм жадно сливает маршруты воедино, проверяя на каждом шаге, не превысит ли суммарный груз вместимость кузова. Этот элементарный подход за миллисекунды выдает планы, отличающиеся от оптимума не более чем на 5-10 процентов.

Гораздо более сложной модификацией является задача маршрутизации с временными окнами (VRPTW). В современной логистике клиенты (например, супермаркеты) требуют доставки строго в определенный интервал времени (с 10:00 до 12:00). Прибытие раньше времени заставит грузовик простаивать в ожидании открытия ворот, а опоздание приведет к гигантским штрафам или отказу от груза. Временные окна бывают жесткими (опоздание недопустимо математически) и мягкими (опоздание допускается, но накладывает штрафную функцию на целевой критерий). Интеграция фактора времени превращает VRP в многомерный логистический кошмар, так как пространственная близость двух клиентов больше не гарантирует, что их выгодно объединять в один маршрут.

Для решения масштабных практических задач VRPTW исследователи операций применяют двухуровневые алгоритмы локального поиска и метаэвристики. Популярным подходом является эвристика вставки Соломона (Solomon Insertion Heuristics), которая поэтапно вклинивает неназначенных клиентов в существующие маршруты с минимальным увеличением времени в пути. Для улучшения полученных маршрутов используются внутримаршрутные операторы (такие как 2-opt, меняющий порядок объезда) и межмаршрутные операторы (перекрестный обмен, перемещение узлов между разными машинами). Наконец, глобальный оптимум ищется с помощью алгоритмов поиска с запретами (Tabu Search) или адаптивного поиска в больших окрестностях (ALNS). Эти алгоритмы способны временно разрушать хорошие маршруты (ухудшать целевую функцию), чтобы выбраться из локальных оптимумов, обеспечивая работу глобальных систем доставки от Amazon до локальных курьерских служб.