La decisione classica del distributore che consegna ogni giorno da un unico deposito a 5-30 clienti: quanti veicoli partono, quale veicolo serve quali clienti e in che ordine — senza superare la capacità e con chilometraggio totale minimo. Nome accademico: Capacitated Vehicle Routing Problem (CVRP); antenato canonico della famiglia VRP, aperto da Dantzig e Ramser nel 1959.
In breve
Ti suona familiare?
- Consegnamo ogni giorno dal nostro deposito a 30-100 clienti — distribuzione a rivenditori, ricambi B2B, distribuzione alimentari-bevande, operazione a deposito unico.
- L'ordine di ogni cliente è noto in kg o m³; il dispatcher raggruppa i clienti d'intuito per non superare la capacità di 2-5 t.
- I clienti non hanno finestre o le hanno molto larghe (accettano tra 08:00 e 18:00) — ricevono a qualsiasi ora.
- Due clienti vicini finiscono talvolta su due veicoli diversi — la decisione 'quale veicolo in quale zona questa settimana' segue il piano precedente.
- Quanti veicoli partono al mattino lo decide il dispatcher — certi giorni bastano 3, altri ne partono 5, senza regola chiara.
- Carburante più stipendi degli autisti sono il 30-50 % delle spese operative, ma nessuno sa quanti km farebbe risparmiare un cambio di rotta.
- Quando si aggiunge un cliente nuovo, 'su quale veicolo sta' si decide a sensazione, non con un calcolo.
Perché è importante
Come si risolve
Profondità tecnica
Come si risolve
Profondità tecnicaIn una frase: Invece di fare un viaggio deposito-cliente separato per ciascuno, calcola quanti km si risparmiano mettendo due clienti sullo stesso camion, fondi le coppie con maggior risparmio finché la capacità lo consente — gira in secondi; aggiungi ricerca locale per più qualità.
CVRP è il membro canonico e più antico della famiglia VRP nella letteratura di Ricerca Operativa (disciplina che usa matematica e informatica per risolvere decisioni di business). L’articolo del 1959 (“The Truck Dispatching Problem”) aprì il campo. Un solo deposito, più veicoli, vincolo di capacità, domanda dei clienti; nessuna finestra oraria. Soluzione in tre fasi:
1. Modellazione. Dati di input: posizione del deposito (una coordinata), posizioni dei clienti e quantità di domanda (kg, m³, colli — qualsiasi unità, la somma non deve superare la capacità), flotta di veicoli (omogenea — tutti con stessa capacità; eterogenea — capacità diverse), matrice delle distanze deposito-cliente e cliente-cliente (simmetrica — A→B = B→A; asimmetrica — vie a senso unico). Vincoli: ogni cliente è visitato esattamente una volta, ogni tour inizia e termina al deposito, la domanda totale di un tour non supera la capacità. Opzionali: lunghezza massima del tour (turno autista), numero massimo di clienti per tour, open VRP (il veicolo finisce all’ultimo cliente, non torna — scenari di noleggio), multi-deposito. La funzione obiettivo è di solito distanza totale minima (o carburante); si può aggiungere numero di veicoli come obiettivo secondario.
2. Decisione tramite solver. Tre approcci principali:
- Euristica classica — Clarke-Wright Savings (1964): Ogni cliente parte sul proprio tour (deposito → cliente → deposito). Si calcola il “risparmio” del fondere due tour: se A e B sono su tour separati e vengono fusi, quanta distanza si risparmia. Si fonde la coppia con risparmio maggiore finché la capacità lo permette. Calcolabile anche senza computer; gira in secondi per 100-200 clienti; arriva tipicamente al 5-10 % dall’ottimo. Sessanta anni dopo è ancora un punto di partenza pratico per operazioni medie.
- MIP esatto — branch-and-cut-and-price (ramificazione-taglio-prezzo — ricerca ad albero rafforzata dalla generazione di colonne): fornisce l’ottimo su 50-200 clienti, ma il tempo di soluzione va da minuti a ore. Adatto a pianificazione settimanale o stagionale — pesante per pianificazione dinamica giornaliera. MIP = Mixed-Integer Linear Programming (ottimizzazione con alcune variabili 0/1 e altre continue).
- Metaeuristiche — 2-opt, Or-opt, ALNS (Adaptive Large Neighborhood Search — ricerca adattativa a grande vicinato, metodo intelligente che rimuove e reinserisce porzioni di soluzione): operatori di miglioramento locale (“scambia due archi”) applicati sull’output Clarke-Wright fanno salire la soluzione passo dopo passo. Pratiche per 200-1000 clienti; arrivano al 2-5 % dall’ottimo in pochi minuti.
Preferenza pratica: meno di 50 clienti — MIP esatto (ottimo garantito); 50-200 clienti — Clarke-Wright + miglioramento 2-opt; 200+ clienti — ALNS o altra metaeuristica.
3. Deployment sul campo. L’output è una lista ordinata che arriva sul tablet dell’autista o sulla stampa: “Veicolo 1 — 08:30 parte dal deposito → cliente A (1,2 t) → cliente C (0,8 t) → cliente F (1,5 t) → rientra al deposito.” Il sistema di gestione ordini (ERP o software di dispatch indipendente) alimenta il solver CVRP: lista ordini, domande, stato flotta, stock al deposito. Calcolato di sera o presto al mattino; se entrano ordini durante il giorno, ripianificazione con orizzonte mobile (5-15 minuti). Riunione mensile operativa: km reali vs piano, numero veicoli reale vs piano, rapporto di risparmio.
Alternative
Manuale + foglio di calcolo + giudizio del dispatcher
GratuitoNessuna licenza
Per chi: 1-3 veicoli, 15-30 clienti/giorno, territorio fisso
- + Costo software zero
- + L'esperienza del dispatcher in primo piano
- + Aggiustamenti rapidi al telefono
- − Qualità del piano cala oltre 30-50 clienti
- − Nessuna garanzia di utilizzo ottimale della capacità
- − Lunga curva di apprendimento per nuovi dispatcher
- − Nessuno storico km/veicolo
Software locale di routing (mercato PMI)
Aziendale300-1.500 EUR setup + 100-400 EUR/mese
Per chi: 5-15 veicoli, 50-200 clienti/giorno, deposito unico
- + Dati di mappe e indirizzi locali integrati
- + Interfaccia in italiano, supporto locale
- + App mobile per autisti inclusa
- − Motore tipico: un metodo 'savings' o nearest-neighbor semplice; debole con vincoli complessi
- − Multi-deposito o flotta con capacità miste poco supportati
- − Trasparenza algoritmica limitata — 'perché questa rotta' difficile da rispondere
Software internazionale specializzato in routing
Aziendale100-500 EUR/veicolo/mese o 50.000-250.000 EUR/anno licenza
Per chi: 20-100 veicoli, multi-deposito, flotta eterogenea, vincoli complessi
- + Maturo: pianificazione capacitata più estensioni (flotta con capacità miste, tour senza rientro al deposito, multi-deposito) pienamente supportate
- + Motori di ricerca avanzati per grandi scale
- + Confronto scenari forte
- − Licenza alta + 3-6 mesi di implementazione
- − Supporto in italiano può essere limitato
- − Programma di formazione ampio
Solver open-source + sviluppo interno
Open SourceLicenza gratuita; sviluppo interno 8-16 settimane o 30.000-100.000 EUR di consulenza
Per chi: Distributore con team tecnico, integrazione ERP desiderata
- + Nessun costo di licenza
- + Pianificazione capacitata ben supportata nei solver open-source
- + Implementazioni di riferimento 'savings' + miglioramento locale ampiamente disponibili
- − Richiede competenza interna in ottimizzazione e software
- − 6-12 mesi per arrivare a maturità produttiva
- − Manutenzione a carico dell'operatore
Raccomandazione
Chiedi nell'incontro
- Qual è il motore — metodo 'savings', solver con garanzia di ottimo, motore di ricerca avanzato o nearest-neighbor semplice? In una demo con 50 clienti, quale metodo produce il risultato?
- Solo flotta con stessa capacità o anche flotta con capacità miste? In una flotta con capacità miste, la scelta veicolo-cliente la fa il motore?
- Sono supportati tour senza rientro al deposito (veicoli a noleggio, il veicolo termina all'ultimo cliente) e routing multi-deposito?
- Come si calcola la matrice delle distanze — linea retta, distanza reale stradale o tempo con traffico? Come è stata validata l'accuratezza regionale?
- Se arriva un nuovo ordine durante la giornata, il piano viene ri-risolto? In quanti secondi la rotta aggiornata arriva all'autista?
- I limiti di lunghezza tour (es. max 6 h o 300 km) e i vincoli di turno autista sono applicati a livello di motore o post-filtrati?
- In un pilot di 8-12 settimane con dati operativi reali, quale rapporto di risparmio può essere prodotto rispetto alla pianificazione manuale precedente?
- Se concludiamo il contratto, in quale formato aperto (CSV, GeoJSON o simile) possiamo esportare posizioni dei clienti, storico ordini, storico rotte e matrice delle distanze?
Dettagli tecnici
Nota della redazione
Nel linguaggio quotidiano questo problema si chiama “pianificazione delle rotte”, “piano di consegne” o “sequenza di dispatch”. In letteratura accademica il nome è Capacitated Vehicle Routing Problem (CVRP) — il membro più antico e canonico della famiglia VRP. Dantzig e Ramser aprirono il campo nel 1959. La domanda che vi ponete ogni mattina — “quanti veicoli, quale veicolo a quali clienti, in che ordine, senza superare la capacità” — è la domanda su cui la ricerca lavora da oltre 60 anni.
Questa pagina non va confusa con VRPTW (#002): VRPTW aggiunge una finestra oraria per ogni cliente (“il negozio è aperto solo 09:00-12:00”). CVRP non ha finestre — il cliente è disponibile tutto il giorno. È la differenza tra l’orario di consegna vegano e la consegna B2B a tempo flessibile. CVRP è più facile (più morbido); VRPTW è più realistico ma matematicamente più difficile. Se i vostri clienti hanno davvero orari di ricezione flessibili — distribuzione a rivenditori, ricambi B2B, distribuzione acqua-bevande — questa è la vostra pagina. Se ci sono finestre strette (consegna a domicilio e-commerce, catena del freddo), vedere #002.
Punto più trascurato del settore: la forza pratica dell’algoritmo Clarke-Wright Savings. Sviluppato nel 1964 per essere calcolato con carta e penna prima dell’avvento dei computer, questa euristica continua a portarsi al 5-10 % dall’ottimo sessanta anni dopo su operazioni medie, in pochi minuti. Quando un fornitore pubblicizza un “motore euristico proprietario” o un “motore di ottimizzazione brevettato”, chiedete un benchmark su 50 clienti contro Clarke-Wright + 2-opt. Se la differenza è inferiore al 2 %, il costo extra di licenza non si giustifica. Secondo punto trascurato: qualità della matrice delle distanze. Molti strumenti usano distanza Euclidea (linea retta); la distanza reale urbana è 1,3-1,8 volte maggiore. Distanza sbagliata significa rotta sbagliata — la matrice stradale reale va testata durante il pilot.
Cammino passo passo per una PMI
Fase 1 — Prima misurare, poi pianificare. Per almeno 4 settimane tenere una tabella: km giornalieri per veicolo, numero di clienti, utilizzo della capacità (carico/massimo), durata del tour deposito-deposito, ore autista. Senza questa baseline non si può valutare alcun software.
Fase 2 — Costruire la tabella cliente-domanda. Per ogni cliente: quantità tipica d’ordine (kg o m³), indirizzo, coordinate, vincoli (limite di dimensione veicolo — “camion grande non entra”, tempo di scarico manuale). Nella maggior parte delle PMI questa informazione vive solo nella testa del dispatcher; scriverla porta già il 5-10 % di efficienza.
Fase 3 — Pilot. 6-10 settimane. 1-3 veicoli. Criterio di successo per iscritto prima dell’inizio: “in 60 giorni km totali -10 %, utilizzo capacità +5 %, numero giornaliero veicoli -1.” Se manca, il pilot termina — assicurare il diritto di uscita nel contratto.
Fase 4 — Rollout. 2-4 mesi su tutta la flotta. Formazione autisti 1-2 settimane. Un autista “campione” per zona. Riunione mensile operativa: km reali vs piano, utilizzo capacità, costo per cliente.
Rischi — cosa può andare storto
- Deviazione della previsione di domanda. Se la quantità giornaliera ordinata è 20-50 % fuori dal piano, la capacità è mezza vuota o superata. Cut-off ordini e calcolo rotte il più vicini possibile; ripianificazione con orizzonte mobile imprescindibile.
- Guasto al veicolo in giornata. Se un veicolo si guasta in strada, la riassegnazione intuitiva dei clienti rimasti ad altri veicoli supera la capacità o salta qualcuno. Il software deve supportare il re-solve in giornata e produrre un nuovo piano in 30 minuti.
- Richiesta di finestre orarie emergente. Un cliente che dice “in realtà ricevo solo al mattino” rompe il modello CVRP — il problema diventa VRPTW. Quando il numero di finestre nel portafoglio supera 10-20, serve migrare a un solver VRPTW.
- Dipendenza da un unico fornitore TMS. Senza clausola contrattuale di esportazione annuale in formato standard (CSV o GeoJSON) di posizioni clienti, storico ordini e rotte, abbandonare il sistema significa perdere la memoria operativa del distributore.
Vista tecnica del metodo di soluzione
Principali approcci nella letteratura CVRP:
| Approccio | Scala tipica | Tempo | Ottimo garantito? |
|---|---|---|---|
| Euristica (dispatcher + regola) | 1-3 veicoli, 15-30 clienti | immediato | No, 50-80 % ottimo |
| Clarke-Wright Savings (1964) | 50-200 clienti | sec-min | No, 5-10 % dall’ottimo |
| Clarke-Wright + 2-opt / Or-opt | 50-300 clienti | minuti | No, 3-7 % dall’ottimo |
| MIP esatto — branch-and-cut-and-price | 50-200 clienti | min-ore | Sì (a scala limitata) |
| Metaeuristica ALNS | 200-1000 clienti | minuti | No, 2-5 % dall’ottimo |
| Generazione di colonne | 100-500 clienti, multi-tour | ore | Praticamente vicino all’ottimo |
Scelta di formulazione:
- Formulazione 2-indici: una variabile decisionale per arco (i, j). Facile da capire, ma pesante a grande scala per i vincoli di eliminazione dei sotto-tour (SEC).
- Formulazione 3-indici: una variabile decisionale per (i, j, veicolo k). Più flessibile per flotta eterogenea o open VRP; il numero di variabili si moltiplica.
Funzione obiettivo:
- Distanza totale minima: la più comune; focus carburante + manutenzione.
- Tempo totale minimo: quando il costo dell’autista supera quello del carburante.
- Numero di veicoli + distanza (gerarchico): prima veicoli, poi distanza — decisione di riduzione flotta.
- Carburante + stipendio combinati: costo operativo diretto come obiettivo.
Estensioni — parenti pratici del CVRP:
- VRP a flotta eterogenea: veicoli con capacità diverse — si combina con “il veicolo grande non entra in centro storico”.
- Open VRP: il veicolo termina all’ultimo cliente, non torna.
- VRP multi-deposito: più depositi; ogni cliente è assegnato a quello più conveniente.
- VRP con vincolo di distanza: lunghezza del tour limitata dal turno dell’autista.
- CVRP asimmetrico: A→B diverso da B→A per sensi unici urbani.
VRPTW (#002), PDPTW (#046), DARP (#047) e TSP (#068) sono parenti stretti. CVRP è il membro più semplice e più antico; capirlo è il primo passo verso gli altri.
Fonti accademiche
Elencate nel blocco sources del frontmatter.
Fonti
- Dantzig, G. B. e Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80-91. Articolo fondativo della famiglia VRP — prima definizione come ‘TSP con capacità’.
- Clarke, G. e Wright, J. W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568-581. Algoritmo classico dei risparmi — tuttora benchmark pratico.
- Toth, P. e Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications (2ª ed.). SIAM-MOS. Libro canonico del campo VRP.
- Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3), 345-358. Panoramica storica e metodologica.
- Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P., Reis, M., Uchoa, E. e Werneck, R. F. (2006). Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Mathematical Programming, 106(3), 491-511. Algoritmo esatto moderno per CVRP.
- Centro Tesi YÖK — parola chiave: ‘kapasiteli araç rotalama’ o ‘CVRP’ — oltre 30 tesi dall’accademia turca. tez.yok.gov.tr
Glossario
- 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.
- Clarke-Wright Savings
- Euristica classica del 1964 per il Capacitated Vehicle Routing Problem: ogni cliente parte sulla propria rotta e le coppie di rotte vengono fuse iterativamente per il maggior 'risparmio' finché la capacità non blocca ulteriori fusioni.
- VRP
- La decisione su quali veicoli, partendo da uno o più depositi, visitano quali clienti e in che ordine.
- MIP
- Modello di ottimizzazione in cui alcune variabili decisionali devono essere numeri interi (es. numero di camion, numero di turni).
Problemi correlati
Cosa entra in un camion o container, e in che ordine si carica?
Dato un camion, container o veicolo merci di dimensioni fisse, quale disposizione di scatole (o pallet) con dimensioni, pesi e regole di impilamento diversi dà il più alto tasso di utilizzo? Il nome matematico è Three-Dimensional Bin Packing Problem (3D-BPP), oppure nella variante pratica Container Loading Problem (CLP). I metodi che risolvono contemporaneamente volume, limiti di peso, regole di impilamento, distribuzione del peso (bilanciamento) e sequenza di consegna (multi-drop) sono studiati dagli anni '90. Anche un miglioramento del 5% nell'utilizzo aumenta in modo concreto le consegne per veicolo per una PMI.
Da un nodo all'altro — come calcolo il cammino minimo su un grafo pesato?
Per PMI che devono calcolare il percorso più rapido o più breve tra due punti: squadre di servizio sul campo con 10-50 veicoli (idraulici, elettricisti, riparazione elettrodomestici), operatori urbani di corriere/pacchi o centrali operative che coordinano interventi di emergenza. Ogni giorno arrivano centinaia di domande 'come vado adesso più veloce da A a B?'; la risposta cambia con traffico, chiusure stradali e tipo di mezzo. Un percorso sbagliato costa al tecnico uno-due interventi saltati nella giornata, al corriere una consegna in ritardo e all'azienda un cliente. Una pianificazione manuale o a occhio lascia tipicamente 20-60 minuti sprecati per veicolo al giorno rispetto a un calcolo basato sulla rete.
Dove Apro il Nuovo Magazzino?
Un distributore, un operatore di e-commerce o un produttore pmi prevede di aprire 1–5 nuovi magazzini, filiali o centri di distribuzione nei prossimi 2–5 anni. La decisione: in quale città o regione, quanti siti, di quali dimensioni, e quali magazzini esistenti trasferiscono quale volume di clienti o ordini al nuovo sito. Una localizzazione sbagliata significa 5–10 anni di alti costi di trasporto, consegne in ritardo e perdita di clienti; una buona localizzazione vale 300.000–1,5 milioni di EUR di risparmio annuo nello stesso periodo. Quando la decisione viene presa a sensazione (per esempio 'accanto allo stabilimento, gli operai abitano vicino'), raramente colpisce l'ottimo — perché costo di trasporto, affitto, tasse, costo del lavoro e tempo di servizio sono vincoli da bilanciare insieme.