Методы и моделиЛогистикаТранспорт
Алгоритм Кларка-Райта (savings)
Классическая эвристика построения маршрутов VRP через объединение парных маршрутов по величине экономии.
Для каждой пары точек считается экономия от их объединения в один маршрут вместо двух радиальных. Маршруты объединяются в порядке убывания savings, пока не нарушены ограничения по вместимости и времени. Быстро строит разумное стартовое решение для промышленных VRP перед 2-opt и метаэвристиками.
Формула
sᵢⱼ = d(0,i) + d(0,j) − d(i,j)
Где мы это применяем
Услуги Advice LogisticsСвязанные термины
- Методы и модели · Транспорт · ЛогистикаVRP - задача маршрутизации транспорта
Vehicle Routing Problem: обобщение TSP на парк из нескольких машин, обслуживающих множество клиентов из одного склада.
- Методы и модели · Транспорт · ЛогистикаCVRP - VRP с ограничением по вместимости
Capacitated VRP: каждое ТС имеет предельную грузоподъёмность, суммарный заказ на маршруте не должен её превышать.
- Методы и модели · ИТ-системыЭвристики и метаэвристики
Приближённые алгоритмы, дающие хорошее (не обязательно оптимальное) решение за разумное время.