Se hai letto l'articolo sul TSP, sai già come ordinare le consegne per minimizzare la distanza. Ma in pratica, i tuoi clienti non ti aspettano a qualunque ora. Un matrimonio alle 14, un pranzo aziendale alle 12 in punto, uno studio medico chiuso tra le 12:30 e le 14. È esattamente il ruolo del VRPTW, il Vehicle Routing Problem with Time Windows. Prende il testimone quando il TSP raggiunge i suoi limiti.
Dal TSP al VRPTW: l'evoluzione naturale
Il TSP minimizza la distanza, punto. Suppone che ogni indirizzo sia accessibile in qualunque momento. Una semplificazione utile per capire il problema, ma che non riflette la tua realtà quotidiana.
Il VRPTW aggiunge due ingredienti essenziali:
- Più veicoli potenziali (la V di VRP): puoi avere 1, 2, 5 corrieri in parallelo
- Fasce orarie per cliente (il TW di Time Windows): ogni indirizzo ha un intervallo
[apertura, chiusura]
E improvvisamente, quello che era un problema di pura geometria diventa un problema temporale. L'ordine ottimale non è più solo «il più corto», è «il più corto che rispetta tutte le fasce».
Un esempio concreto
Immaginiamo una giornata tipica di catering: 6 consegne da fare, partenza dal deposito alle 10:00.
| Cliente | Indirizzo | Fascia | Tempo in loco |
|---|---|---|---|
| A | Duomo | 11:45 a 12:00 | 5 min |
| B | Navigli | 11:00 a 11:30 | 5 min |
| C | Centrale | 12:00 a 12:15 | 5 min |
| D | Porta Romana | 12:30 a 13:00 | 5 min |
| E | Isola | 11:30 a 12:00 | 5 min |
| F | Brera | 13:00 a 13:30 | 5 min |
Il TSP ti direbbe forse: «passa per A, B, C, D, E, F in questo ordine, è il più corto». Ma se arrivi da A alle 12:05 quando dovevi essere lì tra le 11:45 e le 12:00, sei in ritardo. Il cliente non è contento. Perdi il contratto.
Il VRPTW trova un ordine che:
- Visita ogni indirizzo nella sua fascia
- Minimizza la distanza e il tempo totale tra tutti gli ordini fattibili
- Ti avverte in anticipo se alcune fasce sono irraggiungibili (in tal caso serve un veicolo in più, o anticipare la partenza)
Il risultato EDF su questo esempio
OptiRoad ordina le tappe per orario di chiusura crescente, poi simula la giornata a partire dalla partenza alle 10:00. L'ordine ottenuto è: B (Navigli), poi E (Isola), A (Duomo), C (Centrale), D (Porta Romana) e infine F (Brera). Ecco il planning dettagliato che ottieni a schermo:
| Tappa | Arrivo | Inizio servizio | Partenza |
|---|---|---|---|
| B | 10:18 | 11:00 | 11:05 |
| E | 11:25 | 11:30 | 11:35 |
| A | 11:50 | 11:50 | 11:55 |
| C | 12:05 | 12:05 | 12:10 |
| D | 12:30 | 12:30 | 12:35 |
| F | 13:00 | 13:00 | 13:05 |
Da B arrivi molto in anticipo (10:18): il veicolo attende fino all'apertura alle 11:00, poi consegna. Ogni fascia è rispettata dalla prima all'ultima tappa. Un ordine puramente «distanza più corta» in stile TSP non garantirebbe mai questo risultato: potrebbe farti passare da A o da F nel momento sbagliato e far saltare diverse fasce.
Perché è più difficile del TSP
Il TSP è già NP-difficile (vedi articolo TSP). Il VRPTW lo è ancora di più, perché bisogna simulare il flusso temporale del percorso per validare ogni soluzione candidata:
- A ogni tappa si calcola l'orario di arrivo previsto
- Se arrivi prima dell'apertura, attendi (tempo perso)
- Se arrivi dopo la chiusura, la soluzione non è valida (rifiutata)
- Il tempo di servizio si aggiunge all'orario di partenza verso la prossima
Il solver non può limitarsi a ottimizzare la distanza grezza. Deve costruire il planning dettagliato della giornata per ogni ordine testato.
Fascia rigida o fascia morbida?
In teoria esistono due famiglie di fasce orarie. Una fascia rigida deve essere rispettata: una soluzione che la manca viene semplicemente scartata, come un appuntamento medico o una cerimonia che non si spostano. Una fascia morbida tollera il ritardo, ma al prezzo di una penalità che il solver cerca di minimizzare.
OptiRoad tratta le fasce come rigide per giudicare se un percorso è fattibile. La differenza è che, invece di rompere in silenzio una fascia per risparmiare qualche chilometro, OptiRoad segnala la tappa come in ritardo prima ancora di partire. Decidi tu: avvisare il cliente, aggiungere un veicolo o anticipare l'orario di partenza. Nota: il flag strict posto su una fascia è un dato semantico mostrato nel planning (una gestione più avanzata arriverà in seguito).
Gli approcci per risolvere il VRPTW
1. Earliest Deadline First (EDF)
A ogni passo si sceglie il cliente la cui fascia si chiude prima tra quelli ancora raggiungibili. Semplice, veloce, dà ottimi risultati in pratica. È l'approccio usato da OptiRoad.
2. Insertion heuristics
Si parte da un percorso vuoto, si inseriscono i clienti uno per uno cercando la posizione che minimizza il costo totale rispettando le fasce. Buona qualità, calcolo più lungo.
3. Metaeuristiche (simulated annealing, tabu, genetico)
Per istanze molto grandi (centinaia di tappe, multi-veicolo complesso). Danno soluzioni vicine all'ottimo ma richiedono tempo di calcolo.
4. Programmazione vincolata
Approccio accademico molto potente ma pesante da implementare, riservato a casi specifici.
Il tempo di servizio cambia tutto
Lo si dimentica spesso, ma il tempo passato a ogni tappa (il tempo di servizio) sposta in avanti tutti gli arrivi successivi. Cinque minuti per consegnare un pacco, moltiplicati per quindici consegne, sono più di un'ora che slitta sull'intera giornata. Ignorare questo tempo dà un planning che sembra reggere sulla carta ma che accumula ritardo nella vita reale.
Per questo OptiRoad risolve il tempo di servizio tappa per tappa, secondo una priorità chiara: vince il valore inserito manualmente sulla tappa, altrimenti quello del contatto corrispondente nella tua rubrica (abbinato per coordinate), altrimenti il valore predefinito del tuo account (5 minuti). Così, ogni orario di arrivo stimato include già il tempo realmente passato in loco, e il planning riflette il tuo terreno.
Come OptiRoad implementa il VRPTW
Quando attivi «Fasce orarie» nella dashboard (piano Pro o Business), ecco cosa fa OptiRoad:
- Ordina i clienti per fascia di chiusura crescente (con priorità speciale per le tappe segnate
priority: high) - Costruisce il percorso per inserimento EDF: a ogni passo si prende il cliente successivo che rispetta la fascia corrente e minimizza la deviazione
- Simulazione del planning: a partire dall'orario di partenza, calcola per ogni tappa:
- orario di arrivo previsto (tenendo conto della distanza)
- orario di inizio servizio (= max(arrivo, apertura))
- orario di partenza (= inizio + tempo di servizio)
- Rilevamento ritardi: se l'arrivo previsto supera la chiusura, la tappa è marcata
late: truenella risposta, sei avvisato prima di partire - Niente 2-opt quando VRPTW è attivo: l'ordine EDF prevale sull'ottimizzazione della distanza, per non rompere i vincoli temporali
Il risultato nell'app: una tabella riepilogativa chiara che mostra l'orario di arrivo previsto a ogni cliente, gli eventuali ritardi in rosso, e la durata totale reale della giornata (inclusi i tempi di attesa).
Quando usare VRPTW vs TSP semplice
- TSP: percorso di consegna classico senza forti vincoli orari (e-commerce, posta, ecc.). Arrivi quando arrivi.
- VRPTW: appena almeno alcuni clienti hanno una fascia imposta. Catering, fioristi (cerimonie), assistenza domiciliare (fasce mediche), interventi tecnici su appuntamento.
OptiRoad passa automaticamente al VRPTW non appena imposti almeno una fascia oraria nel percorso.
E il multi-veicolo?
Il VRPTW può essere combinato con multi-veicolo: più corrieri in parallelo, ognuno con il proprio percorso ottimizzato. OptiRoad gestisce questo caso nel piano Business con l'algoritmo Clarke-Wright Savings per ripartire le tappe tra veicoli, poi EDF e simulazione per veicolo. Sarà l'oggetto di un prossimo articolo.
In pratica: cosa cambia per te
Su un percorso tipico con fasce orarie (consegne catering, ad esempio):
- Senza VRPTW: dal 30 al 50% delle consegne rischiano di essere fuori fascia, chiami i clienti per posticipare, ti stressi.
- Con VRPTW: 100% delle consegne nelle fasce o avviso prima della partenza. La giornata si svolge come previsto.
E quando sai in anticipo che una consegna sarà in ritardo, puoi agire: chiamare il cliente, aggiungere un veicolo, anticipare la partenza. Il semplice fatto di saperlo in anticipo vale spesso più del risparmio di chilometri.
Per andare oltre
Il VRPTW è disponibile nei piani Pro e Business. Il piano Free include il TSP semplice (senza fasce), sufficiente per validare la qualità dell'algoritmo su percorsi piccoli. Per attivare le fasce, passa a Pro e attiva il toggle «Fasce orarie» in OptimizePanel.
Vuoi approfondire il multi-veicolo (VRP con Clarke-Wright Savings)? È il prossimo articolo.
Domande frequenti
Cosa succede se una fascia non può essere rispettata?
La tappa interessata viene segnalata come in ritardo prima della partenza, mai scoperta già in strada. Mantieni il controllo: avvisare il cliente, aggiungere un veicolo per distribuire il carico, o anticipare l'orario di partenza in modo che la fascia torni raggiungibile.
Posso mescolare tappe con e senza fascia?
Sì. Le tappe senza fascia non sono vincolate ad alcun orario preciso: OptiRoad le colloca liberamente attorno a quelle vincolate, dove si inseriscono meglio senza disturbare le fasce imposte. Quindi non sei obbligato a impostare una fascia per ogni consegna.
Il VRPTW gestisce più veicoli?
Sì, nel piano Business. OptiRoad ripartisce prima le tappe tra i veicoli con l'algoritmo Clarke-Wright Savings, poi applica l'EDF e la simulazione del planning a ogni percorso separatamente. Ogni corriere ottiene così il proprio itinerario ottimizzato e rispettoso delle fasce.
Quale piano include le fasce orarie?
Le fasce orarie sono disponibili nei piani Pro e Business. Il piano Free si limita al TSP semplice, senza vincolo temporale: perfetto per testare la qualità dell'ottimizzazione su percorsi piccoli, ma non adatto ai mestieri con fasce imposte.