VRP multi-veicolo: Clarke-Wright Savings spiegato

Hai letto del TSP (ordinare le tappe) e del VRPTW (rispettare le fasce orarie). Resta un caso pratico molto comune: hai più veicoli. 2 corrieri al mattino, 5 operatori sul campo, 3 catering che partono insieme. Come ripartire i clienti tra di loro per minimizzare il tempo totale?

È il VRP (Vehicle Routing Problem) e il metodo più usato in pratica risale al 1964: l'algoritmo di Clarke e Wright, detto Savings algorithm. È quello che OptiRoad usa nel piano Business per gestire da 2 a 10 veicoli.

Il problema in una frase

Hai 1 deposito e N clienti da consegnare. Hai M veicoli disponibili. Come ripartire gli N clienti tra gli M veicoli affinché il tempo totale sia minimo?

Sembra semplice. Non lo è.

Perché è difficile

Con 20 clienti e 3 veicoli, il numero di partizioni possibili supera i 3,5 milioni. E per ogni partizione, bisogna ancora risolvere un TSP (o VRPTW se ci sono fasce) su ciascun veicolo. La forza bruta è impossibile oltre i 10 a 15 clienti.

Il VRP, come il TSP, è NP-difficile: nessun algoritmo garantisce la soluzione ottima in tempo ragionevole. Quindi usiamo euristiche. Quella che domina da 60 anni nel mondo reale è Clarke-Wright Savings.

L'idea geniale di Clarke-Wright (1964)

George Clarke e John Wright pubblicarono il loro articolo "Scheduling of vehicles from a central depot to a number of delivery points" nel 1964. L'idea è di un'eleganza disarmante.

Passo 1: la soluzione ingenua

Si parte da una soluzione degenere: ogni cliente ha il proprio veicolo. 20 clienti = 20 mini-percorsi deposito → cliente → deposito. Spreco, ma è il nostro punto di partenza.

Costo totale: per ogni cliente i, il veicolo fa d(deposito, i) + d(i, deposito) = 2 × d(deposito, i).

Passo 2: il concetto di "saving"

Immaginiamo di fondere i percorsi di due clienti i e j in uno solo. Invece di:

deposito → i → deposito   +   deposito → j → deposito

Facciamo:

deposito → i → j → deposito

Il risparmio (il saving) è:

s(i,j) = d(deposito, i) + d(j, deposito) - d(i, j)

Più i e j sono vicini tra loro e lontani dal deposito, più grande è il saving. È intuitivo: vale la pena raggrupparli.

Passo 3: la fusione greedy

1. Calcola s(i,j) per tutte le coppie di clienti
2. Ordina questi savings in ordine decrescente
3. Per ogni coppia (i,j), nell'ordine:
   • Se i e j sono su percorsi diversi
   • E sono alle estremità dei rispettivi percorsi
   • E ci sono ancora veicoli disponibili (≤ M)
   • Fonde i due percorsi
4. Continua finché non ci sono più coppie utili

Alla fine, ottieni M percorsi (o meno) che coprono tutti i clienti, con una distanza totale molto migliore della soluzione ingenua, e tipicamente entro il 5 a 10% dell'ottimo teorico.

Savings, sweep o metaeuristica?

Clarke-Wright non è l'unica famiglia di algoritmi per il VRP. Coesistono tre grandi approcci.

L'algoritmo sweep (Gillett e Miller, 1974) raggruppa i clienti per il loro angolo attorno al deposito, come una lancetta d'orologio che spazza il piano. È estremamente semplice da programmare, ma la qualità dei percorsi resta inferiore: segui la geometria, non il costo reale.

Le metaeuristiche (ricerca tabù, algoritmi genetici) esplorano lo spazio delle soluzioni in modo più fine e raggiungono risultati leggermente migliori. Il rovescio della medaglia: sono più lente e più delicate da tarare. Bisogna calibrare numerosi parametri, il che le rende pesanti da portare in produzione.

Clarke-Wright Savings si colloca nel punto di equilibrio ideale: risultati vicini all'ottimo, esecuzione rapida, una robustezza a tutta prova e una grande facilità di estensione con capacità o fasce orarie. È esattamente per questo che domina l'ottimizzazione di flotte in condizioni reali da 60 anni.

Un esempio concreto

Immaginiamo 6 clienti da consegnare da un deposito in Milano-Centro, con 2 veicoli disponibili:

Soluzione ingenua (1 veicolo per cliente, 6 veicoli):

• Costo totale: 2 × (4 + 5 + 8 + 6 + 9 + 7) = 78 km

Con Clarke-Wright Savings e 2 veicoli:

1. Calcolo dei savings per le 15 coppie possibili
2. Ordinamento decrescente
3. Fusioni successive rispettando il limite di 2 veicoli
4. Risultato possibile: Veicolo 1 = deposito → A → B → D → deposito (~22 km), Veicolo 2 = deposito → C → F → E → deposito (~28 km)

• Costo totale: ~50 km (-36% vs ingenua)

Su casi reali, si osservano comunemente guadagni del 30 a 40% rispetto a una partizione manuale "a occhio".

Varianti ed estensioni

L'algoritmo originale è per il VRP base. In pratica, lo arricchiamo:

• Capacità: ogni veicolo ha un carico massimo. Si verifica a ogni fusione che non si superi la capacità.
• Multi-deposito: più depositi. Euristica: assegnare ogni cliente al deposito più vicino, poi Clarke-Wright su ogni sottoproblema.
• Fasce orarie: combinare con VRPTW. Fondere due percorsi solo se l'ordine risultante rispetta tutte le fasce.
• Limite sul numero di veicoli: se vuoi esattamente M veicoli, si ferma la fusione prima.
• Asimmetria: la distanza A→B può differire da B→A (sensi unici, ecc.). Il calcolo dei savings resta valido.

Come OptiRoad implementa il VRP multi-veicolo

Nel piano Business puoi ottimizzare fino a 10 veicoli in parallelo. Ecco cosa fa OptiRoad quando attivi il modo multi-veicolo:

1. Configurazione: indichi il numero di veicoli, il loro deposito (comune o proprio per ciascuno) e opzionalmente il loro punto di arrivo.
2. Clarke-Wright Savings: calcolo dei savings su tutte le coppie, ordinamento decrescente, fusioni greedy rispettando il limite di veicoli.
3. Multi-deposito: se ogni veicolo ha un deposito diverso (sharedDepot: false), pre-assegnazione delle tappe per prossimità prima dell'esecuzione di Clarke-Wright su ogni cluster.
4. TSP locale per veicolo: una volta trovata la partizione, ogni percorso viene riottimizzato individualmente con nearest neighbor + 2-opt per minimizzare la distanza interna.
5. Se VRPTW attivo: EDF (Earliest Deadline First) su ogni percorso, rispettando le fasce di ogni cliente.
6. Colori distinti: ogni veicolo riceve un colore sulla mappa (#3B82F6, #EF4444, #10B981, ecc.) per visualizzare facilmente i percorsi.

Timeout adattivi: 15 secondi per 2 a 4 veicoli, 30 secondi per 5 a 10 veicoli. Se superato, OptiRoad restituisce il miglior risultato trovato con un flag partial: true.

Drag and drop per aggiustamento manuale

Se la ripartizione automatica non ti convince (un cliente deve assolutamente essere assegnato a un corriere preciso per ragioni commerciali), puoi trascinare una tappa da un veicolo all'altro nell'app. OptiRoad ricalcola allora l'ordine TSP per ogni veicolo impattato rispettando la nuova partizione. Endpoint: POST /api/optimize/reorder (solo piano Business).

Bilanciare i percorsi

Nella sua forma grezza, Clarke-Wright insegue una cosa sola: minimizzare la distanza totale. Di conseguenza, può produrre percorsi sbilanciati, un corriere carico di 25 tappe mentre un altro ne ha solo 8. Sulla carta la distanza è ottima, nella vita reale è ingestibile lato pianificazione.

In pratica, quindi, si limita il numero di tappe o la capacità per veicolo per forzare una ripartizione più omogenea. Poi si riequilibra a mano quando il campo lo richiede. OptiRoad ti permette di fissare il numero di veicoli e spostare le tappe da uno all'altro con il drag and drop: ogni percorso interessato viene ricalcolato all'istante, così mantieni un ordine ottimizzato senza perdere il controllo del carico di ciascun corriere.

Quando usare il multi-veicolo

• 2 a 3 veicoli: utile non appena la giornata supera le 30 tappe, o se consegni in zone geografiche distinte.
• 5 a 10 veicoli: per flotte strutturate (servizi alla persona, catering con team, e-commerce in scala).
• Oltre 10 veicoli: contattaci, possiamo attivare un solver dedicato per flotte molto grandi.

In pratica: cosa cambia per te

Su una giornata tipica di 60 consegne da ripartire tra 3 corrieri:

• Senza ottimizzazione (ripartizione manuale "a occhio"): ~280 km, 12 ore cumulative
• Con Clarke-Wright Savings di OptiRoad: ~190 km, 8 ore cumulative
• Guadagno: -32% di distanza, -33% di tempo cumulativo

Oltre ai chilometri, il vero guadagno è organizzativo: ogni corriere parte con il suo foglio di ruta chiaro, il suo colore sulla mappa, ETA precisi. Niente più "chi prende chi" la mattina.

Per andare oltre

Il VRP multi-veicolo è disponibile esclusivamente nel piano Business (49 €/mese). Il piano Pro resta mono-veicolo (con o senza fasce orarie).

Questa serie di 3 articoli (TSP → VRPTW → VRP multi-veicolo) copre le basi concettuali di OptiRoad. I prossimi articoli affronteranno temi pratici: quanti risparmi reali, come integrare l'API al tuo negozio e-commerce, ecc.

Domande frequenti

Quanti veicoli gestisce OptiRoad? Da 2 a 10 veicoli nel piano Business. Oltre, contattaci: possiamo attivare un solver dedicato per flotte molto grandi.

Ogni veicolo può avere un deposito diverso? Sì, il modo multi-deposito è pensato per questo. Le tappe vengono pre-assegnate al deposito più vicino prima che Clarke-Wright giri su ogni cluster, il che garantisce percorsi coerenti per zona.

Posso vincolare un cliente a un veicolo preciso? Sì, con il drag and drop. Sposti la tappa sul veicolo desiderato e OptiRoad ricalcola subito l'ordine TSP dei veicoli interessati per mantenere ogni percorso ottimizzato.

Quale piano serve? Solo il piano Business. Il piano Pro resta mono-veicolo, con o senza fasce orarie.