Методы и моделиТранспортЛогистика

VRP - задача маршрутизации транспорта

Vehicle Routing Problem: обобщение TSP на парк из нескольких машин, обслуживающих множество клиентов из одного склада.

Дан склад, N клиентов с заявками и парк транспортных средств. Задача - сформировать набор маршрутов минимальной суммарной стоимости так, чтобы каждый клиент был обслужен ровно одним ТС. Расширения: CVRP (ограничение по вместимости), VRPTW (окна доставки), MDVRP (несколько складов), HFVRP (разнородный парк). Практическое ядро TMS-систем маршрутизации.

Демо · VRP (Clarke-Wright)

Маршрутизация парка с ограничением

Ёмкость

Клиентов

12

Суммарный спрос

33

Маршрутов

3

Общая длина

1666

усл. ед.

#1 · 5 клиентов · загрузка 14/15 · 832 ед.

#2 · 2 клиентов · загрузка 8/15 · 248 ед.

#3 · 5 клиентов · загрузка 11/15 · 585 ед.

Склад - фиолетовый квадрат в центре. Число рядом с клиентом - его спрос. Алгоритм Кларка-Райта объединяет маршруты по убыванию экономии, пока не нарушится ёмкость машины.

Где мы это применяем

Услуги Advice Logistics

Часто задаваемые вопросы

Чем VRP отличается от TSP?+

TSP - один маршрут, одна машина, все точки. VRP - парк из K машин, стартующих со склада, каждая обслуживает подмножество клиентов. Целевая функция: минимизировать суммарный пробег (или число машин при ограничении длины смены). CVRP добавляет ограничение по грузоподъёмности.

Какие эвристики применяют для VRP на практике?+

Классика - Clarke-Wright savings (быстрая построительная эвристика для CVRP). Для улучшения: 2-opt/or-opt внутри маршрута, инкрементальный swap между маршрутами, tabu search, ALNS. Коммерческие TMS обычно комбинируют savings + локальный поиск.

Связанные термины

В той же отрасли

← все термины