Glosario · approach
Ruteo de vehículos con capacidad
Diseño de rutas de vehículos de coste mínimo que empiezan y terminan en un único almacén, visitan a cada cliente exactamente una vez, sin que la demanda total por ruta supere la capacidad del vehículo.
Capacitated Vehicle Routing ProblemCVRPProblema de ruteo de vehículos con capacidadTruck Dispatching Problem
El Capacitated Vehicle Routing Problem (CVRP) es el problema de diseñar un conjunto de rutas de vehículos de coste mínimo que (a) empiezan y terminan en un único almacén, (b) visitan a cada cliente exactamente una vez, y (c) mantienen la demanda total en cada ruta en o por debajo de la capacidad del vehículo. No tiene ventanas horarias — esa extensión es VRPTW. El coste suele ser distancia total, tiempo total, o una combinación de combustible y salario del conductor. CVRP es NP-difícil y es el ancestro canónico de toda la familia VRP; Dantzig y Ramser (1959) lo abrieron como 'The Truck Dispatching Problem'. Libro de referencia: Toth y Vigo (2014). Los métodos prácticos van desde la heurística clásica Clarke-Wright Savings (1964 — todavía benchmark en instancias medianas), pasando por mejoras 2-opt y Or-opt, algoritmos exactos modernos branch-and-cut-and-price (Fukasawa et al. 2006), hasta metaheurísticas ALNS (Adaptive Large Neighborhood Search).
Örnek
Un distribuidor regional reparte diariamente desde un almacén a 80 clientes, cada uno con su demanda en kg; los vehículos cargan 2 toneladas; la pregunta es cuántos vehículos salen, qué clientes en cada uno y en qué orden, para minimizar los kilómetros totales.