Glossario · approach
Routing veicoli con capacità
Progettazione di rotte di veicoli a costo minimo che iniziano e terminano in un unico deposito, visitano ogni cliente esattamente una volta, con la domanda totale per rotta che non supera la capacità del veicolo.
Capacitated Vehicle Routing ProblemCVRPProblema di routing veicoli con capacitàTruck Dispatching Problem
Il Capacitated Vehicle Routing Problem (CVRP) è il problema di progettare un insieme di rotte di veicoli a costo minimo che (a) iniziano e terminano in un unico deposito, (b) visitano ogni cliente esattamente una volta e (c) mantengono la domanda totale per rotta pari o inferiore alla capacità del veicolo. Non ha finestre orarie — quella estensione è VRPTW. Il costo è di solito distanza totale, tempo totale o una combinazione di carburante e stipendio dell'autista. CVRP è NP-difficile ed è l'antenato canonico dell'intera famiglia VRP; Dantzig e Ramser (1959) lo aprirono come 'The Truck Dispatching Problem'. Testo di riferimento: Toth e Vigo (2014). I metodi pratici vanno dall'euristica classica Clarke-Wright Savings (1964 — tuttora qualità benchmark su istanze medie), attraverso miglioramenti 2-opt e Or-opt, algoritmi esatti moderni branch-and-cut-and-price (Fukasawa et al. 2006), fino a metaeuristiche ALNS (Adaptive Large Neighborhood Search).
Örnek
Un distributore regionale consegna ogni giorno da un deposito a 80 clienti, ciascuno con la propria domanda in kg; i veicoli portano 2 tonnellate; la domanda è quanti veicoli partono, quali clienti su ciascuno e in che ordine, per minimizzare i chilometri totali.