La route optimization è la pratica di ordinare le tappe e assegnare i veicoli in modo che una flotta finisca il proprio lavoro nel minor tempo, distanza o costo. È la differenza tra un delivery driver che termina alle 16:00 e uno che termina alle 19:00 con lo stesso furgone e le stesse tappe. Sotto ogni pulsante "percorso ottimizzato" in un'app logistica c'è un solver che ha appena masticato milioni di possibili ordinamenti e ne ha scelto uno.
Questa guida spiega cos'è davvero la route optimization, come la affrontano i solver, dove compare nel mondo reale e quali vincoli e insidie separano una demo dalla produzione.
Cos'è davvero la route optimization
In informatica, la route optimization vive all'interno di due problemi classici. Il Travelling Salesman Problem (TSP) chiede: data una lista di città e le distanze tra di loro, qual è il percorso più breve che visita ogni città esattamente una volta e torna al punto di partenza? È un problema a singolo veicolo. Il Vehicle Routing Problem (VRP) generalizza questo a una flotta: dato un deposito, un insieme di clienti e diversi veicoli, come si dovrebbero suddividere i clienti tra i veicoli, e in che ordine dovrebbe visitarli ciascun veicolo?
Entrambi i problemi sono NP-hard. Il numero di ordinamenti possibili cresce in modo fattoriale con il numero di tappe. Già venti tappe producono più di 10 alla 18 percorsi possibili. Nessun algoritmo esatto può cercare in quello spazio in tempo reale. L'optimization, in produzione, non riguarda quindi la ricerca della risposta perfetta. Riguarda trovare una risposta molto buona abbastanza in fretta da poterci agire sopra.
Come i solver affrontano il problema
Poiché lo spazio di ricerca è enorme, i solver reali combinano diverse tecniche.
Per problemi piccoli (sotto le 15 tappe circa), metodi esatti come branch-and-bound o programmazione intera possono restituire una soluzione provatamente ottima in pochi secondi. Oltre quella scala, i metodi esatti smettono di essere praticabili e il campo passa alle euristiche.
Una pipeline tipica parte con un'euristica costruttiva come nearest-neighbour o l'algoritmo savings di Clarke-Wright per produrre un percorso iniziale. Quel percorso viene poi consegnato a una metaeuristica, che iterativamente scambia tappe, inverte sotto-tour o sposta tappe tra veicoli per migliorare l'obiettivo. Simulated annealing, tabu search, large neighbourhood search e algoritmi genetici sono le scelte più comuni. Hanno tutti la stessa forma: prova un cambiamento, decidi se accettarlo, ripeti per un budget temporale fisso.
L'altro input critico è la distance matrix: una tabella precalcolata di tempo e distanza di viaggio tra ogni coppia di tappe. L'optimizer interroga la matrice milioni di volte durante la sua ricerca, quindi la matrice è costruita una volta in anticipo da un routing engine e tenuta in memoria mentre il solver gira.
Dove si applica la route optimization
La route optimization alimenta silenziosamente una lunga lista di business operativi.
- Last-mile delivery: corrieri di pacchi, consegna della spesa e fulfilment e-commerce sequenziano tutti decine o centinaia di tappe per furgone al giorno
- Field service: tecnici HVAC, installatori telecom e operatori sanitari domiciliari visitano clienti in una regione con finestre di appuntamento e requisiti di skill
- Mobile workforce: squadre delle utility, lettori di contatori e ispettori che coprono territori con tipi di task misti
- Food delivery: aggregatori di ristoranti che raggruppano più ordini in un singolo viaggio del rider quando la geografia lo permette
- Raccolta rifiuti: camion comunali con giri settimanali fissi in cui piccoli riordinamenti fanno risparmiare carburante reale
- Sales rep: pianificazione del territorio in cui un rappresentante visita 8-12 account al giorno e l'ordine conta per tempo di guida e densità di meeting
In ogni caso l'utente vede una lista di tappe nell'ordine giusto. Il lavoro avviene nell'optimizer dietro di esso.
Vincoli che contano
Un solver che minimizza solo la distanza è un giocattolo. Il routing in produzione è definito dai suoi vincoli.
- Capacità del veicolo: ogni furgone ha un limite di peso, volume o pallet che le tappe assegnate non devono superare
- Finestre temporali: i clienti si aspettano la consegna tra, diciamo, le 9 e le 11, e arrivare alle 11:05 è un fallimento
- Turni del driver: ore lavorative massime, pause obbligatorie e partenza/arrivo in depositi specifici
- Match di skill o veicolo: l'installazione di un frigorifero richiede una squadra di due persone, una consegna a catena del freddo richiede un furgone refrigerato
- Multi-depot: le grandi flotte fanno dispatch da più magazzini e il solver decide quale deposito gestisce quale tappa
- Return-to-base: alcuni percorsi sono open (il driver finisce a casa), altri sono closed (il driver torna al deposito)
Ogni vincolo riduce l'insieme dei percorsi fattibili e spinge il solver verso soluzioni che sulla carta sembrano leggermente peggiori ma sono effettivamente realizzabili.
Insidie in produzione
La route optimization è una categoria in cui la demo funziona sempre e il rollout spesso no.
Ottimizzare l'obiettivo sbagliato. Minimizzare la distanza è il default, ma per molte flotte i ricavi o la conformità SLA contano più dei chilometri risparmiati. Un percorso che consegna un pacco extra al costo di 2 km è di solito una vittoria.
Free-flow vs traffic-aware. Una matrice costruita su velocità stradali grezze ti dirà che un percorso impiega 4 ore quando nel traffico dell'ora di punta ne impiega 6. Usa un routing engine che esponga tempi di viaggio traffic-aware per l'orario in cui il percorso verrà eseguito.
Niente replanning real-time. I piani slittano nel momento in cui un driver incappa in traffico imprevisto, un cliente cancella o arriva una nuova tappa. I team operativi hanno bisogno di un modo per ri-ottimizzare le tappe rimanenti a metà giornata senza buttare via il lavoro della mattina.
Frozen plan staleness. Un percorso settimanale fisso sembrava ottimo a gennaio e ora è il 20 percento peggio perché i clienti si sono spostati, i volumi sono cambiati e c'è un nuovo senso unico. Rifai l'optimization periodicamente e confronta il nuovo piano con quello in produzione prima di forzare un cambio sui driver.
La route optimization in MapAtlas
La MapAtlas Optimize Route API risolve problemi di routing single-vehicle e di flotta con i vincoli di cui i team operativi hanno davvero bisogno: capacità, finestre temporali, turni, skill e setup multi-depot. Restituisce un piano sequenziato per veicolo insieme ai tempi di arrivo e partenza previsti per ogni tappa.
Si combina naturalmente con altri due endpoint dello stack MapAtlas. La Distance Matrix API costruisce la tabella di tempi di viaggio che il solver consuma, con tempi traffic-aware così i piani reggono nell'ora di punta. La Directions API disegna i percorsi stradali turn-by-turn effettivi tra tappe consecutive una volta che l'ordine è fissato, così un'app driver può mostrare una polyline reale invece di una linea retta.
La route optimization non sembrerà glamour in una slide deck. È un solver, una matrice e una lista di vincoli. Ma è lo strato che decide se una flotta finisce la giornata in orario e nel budget, e farlo bene è ciò che separa una funzionalità di routing che va in produzione da una che viene silenziosamente spenta.
Domande frequenti
Cos'è la route optimization?
La route optimization è il processo di decidere il miglior ordine in cui visitare un insieme di tappe e, quando è coinvolto più di un veicolo, quale veicolo deve gestire quali tappe. L'obiettivo è minimizzare un criterio come tempo totale di guida, distanza, carburante o costo, rispettando vincoli reali come capacità del veicolo, turni dei driver e finestre temporali dei clienti. In informatica si colloca all'interno di due problemi classici: il Travelling Salesman Problem (TSP) per un singolo veicolo e il Vehicle Routing Problem (VRP) per una flotta.
Qual è la differenza tra route planning e route optimization?
Il route planning risponde alla domanda 'come vado da A a B'. Restituisce un singolo percorso tra due punti, di solito con indicazioni stradali turn-by-turn. La route optimization risponde a 'in che ordine devo visitare queste 80 tappe con questi 6 furgoni, e quale furgone prende quale tappa'. L'optimization sta uno strato sopra al planning: decide la sequenza e l'assegnazione, poi chiama un routing engine per disegnare il percorso stradale effettivo tra ogni coppia di tappe.
Quali algoritmi si usano per la route optimization?
Per problemi piccoli (sotto le 15 tappe circa) metodi esatti come branch-and-bound o programmazione intera possono trovare una soluzione provatamente ottima. Oltre, lo spazio di ricerca esplode e i sistemi in produzione usano euristiche e metaeuristiche: nearest-neighbour e algoritmi savings per una soluzione iniziale, poi local search, simulated annealing, tabu search o algoritmi genetici per migliorarla. La maggior parte dei solver commerciali combina più tecniche e gira per un budget temporale fisso invece che fino all'ottimo dimostrabile.
Quali input servono a una route optimization API?
Come minimo: la lista delle tappe con coordinate, i veicoli con le loro location di partenza e arrivo, e una matrice di distanze o tempi tra ogni coppia di tappe. In pratica si forniscono anche capacità dei veicoli, finestre temporali dei clienti, durate di servizio in ogni tappa, ore di turno dei driver, skill richieste o tipi di veicolo per tappa, e location dei depositi. La matrice è l'input più pesante ed è solitamente prodotta da una distance matrix API separata prima dell'avvio del solver.
