Cos'è il TSP, e perché è il cuore di OptiRoad

Se consegni a 15, 30 o 100 clienti al giorno, hai già fatto, senza saperlo, del TSP: il Traveling Salesman Problem, o problema del commesso viaggiatore. È uno dei problemi più studiati dell'informatica, ed è esattamente quello che risolve OptiRoad ogni volta che clicchi su "Ottimizza". Questa guida spiega in parole semplici di cosa si tratta, perché è più difficile di quanto sembri e come si risolve in pratica.

Il problema, in una frase

Hai un punto di partenza (il tuo deposito, casa) e una lista di indirizzi da visitare nella giornata. Qual è l'ordine di passaggio che minimizza la distanza totale percorsa? Ecco il TSP.

Banale da formulare, brutalmente difficile da risolvere quando si superano una decina di indirizzi. Ed è proprio qui che l'intuito umano arriva presto al limite: l'occhio individua facilmente un buon percorso da 5 tappe, molto meno bene un percorso da 40. Quello che sembra un piccolo dettaglio (in che ordine guido?) in realtà decide buona parte del tuo tempo di guida quotidiano e dei tuoi costi.

Un esempio concreto

Immagina 5 consegne a Milano:

• A: Duomo
• B: Navigli
• C: Stazione Centrale
• D: Porta Romana
• E: Isola

Se parti dal deposito e passi in ordine alfabetico A → B → C → D → E, probabilmente farai zig-zag per la città. In concreto, quel percorso alfabetico ti fa attraversare Milano da una parte all'altra e tornare indietro: conta circa 13 km. Riorganizzando intelligentemente gli stessi 5 indirizzi (per esempio raggruppando le tappe vicine tra loro), l'ordine ottimizzato scende a circa 9 km, ovvero all'incirca il 30% in meno per esattamente le stesse consegne. Su 200 giorni lavorativi all'anno, questo risparmio per percorso sono migliaia di chilometri: ore di guida e un budget carburante nient'affatto trascurabile.

Perché il TSP è difficile

Con 5 indirizzi ci sono 5! = 120 ordini possibili. Un umano può provarli a mano. Con 10 indirizzi si sale a 3,6 milioni. Con 20, sono 2,4 trilioni di trilioni. Nessuna macchina al mondo può testare tutte le combinazioni di un percorso da 30 consegne in un tempo ragionevole.

Il TSP è quello che si chiama un problema NP-difficile: nessun algoritmo noto può garantire la soluzione perfetta in un tempo che scala ragionevolmente con il numero di tappe. Ogni indirizzo aggiunto moltiplica lo spazio delle soluzioni, non si limita a sommarlo.

Da ricordare: per 10 indirizzi o meno, si possono ancora testare tutte le combinazioni e garantire l'ottimo assoluto. Oltre, si usano euristiche, strategie che danno una soluzione molto buona senza garantire la perfezione matematica.

Un po' di storia

Il TSP non è una novità. I matematici lo studiano dagli anni Trenta: il matematico austriaco Karl Menger lo discusse a Vienna all'interno del suo circolo scientifico, e il problema si diffuse rapidamente nelle università americane. La svolta arrivò negli anni Cinquanta alla RAND Corporation, dove George Dantzig, Delbert Ray Fulkerson e Selmer Johnson pubblicarono nel 1954 la risoluzione esatta di un'istanza celebre: un percorso ottimale che collegava 49 città degli Stati Uniti (una per stato, più Washington). Fu un'impresa notevole per l'epoca, ottenuta con metodi di programmazione lineare e molto calcolo a mano. Ancora oggi il TSP resta un banco di prova di riferimento in ricerca operativa e logistica: i nuovi algoritmi si misurano spesso su queste istanze storiche.

Gli approcci in pratica

1. Brute force (≤ 10 tappe)

Si testano tutte le permutazioni possibili, si tiene la migliore. Garantisce l'ottimo assoluto ma diventa impraticabile oltre le 10 tappe.

2. Nearest neighbor (euristica semplice)

A ogni passo si va alla tappa più vicina alla precedente. Veloce, ma spesso lontano dall'ottimo: ci si può ritrovare bloccati lontano dalle tappe rimanenti.

3. 2-opt (miglioramento locale)

Si parte da una soluzione iniziale (spesso da nearest neighbor), poi si cerca di "districare" gli incroci invertendo segmenti del percorso. Iterativo, dà tipicamente risultati a meno del 5% dell'ottimo teorico.

4. Algoritmi più avanzati

Lin-Kernighan, simulated annealing, algoritmi genetici, programmazione vincolata: molti approcci esistono in ricerca operativa. Possono spremere l'ultimo margine di precisione, ma sono più complessi da implementare e mantenere. Per un uso business come la consegna, nearest neighbor + 2-opt offre il miglior compromesso tra semplicità, qualità e velocità: facile da capire, molto rapido e vicino all'ottimo sui percorsi reali.

Ottimo perfetto o subito molto buono?

È la vera domanda quando si progetta uno strumento di consegna. Un solver può puntare alla soluzione matematicamente perfetta, ma questa può richiedere ore di calcolo su un percorso grande. Sul campo, però, nessuno aspetta ore per partire a consegnare. Una soluzione a pochi punti percentuali dall'ottimo, calcolata in pochi secondi, batte nettamente una soluzione perfetta che arriva troppo tardi.

Perché? Perché gli ultimi punti percentuali di distanza risparmiati non valgono quasi mai l'attesa: tra un percorso da 9,0 km e uno da 8,8 km, la differenza sull'arco della tua giornata è trascurabile, mentre il tempo di calcolo può esplodere. È proprio per questo che le euristiche come nearest neighbor + 2-opt sono la scelta ingegneristica giusta: offrono l'essenziale del guadagno, subito e in modo affidabile. La perfezione teorica è affare dei ricercatori; la redditività quotidiana, dei corrieri.

Le varianti che contano per la consegna

Il TSP "puro" suppone che si torni al punto di partenza alla fine. In pratica, i tuoi vincoli sono più ricchi:

• TSP open-loop: nessun ritorno al deposito (finisci dall'ultimo cliente).
• VRPTW (Vehicle Routing Problem with Time Windows): ogni indirizzo ha una fascia oraria di apertura (es. 9 alle 12). È quello che usi per le fasce di consegna.
• VRP multi-veicolo: più corrieri, quindi come ripartire le tappe tra i veicoli per minimizzare il tempo totale?
• VRP con capacità: ogni veicolo ha un carico utile massimo.

OptiRoad gestisce queste varianti: VRPTW per le fasce orarie (piani Pro e Business) e VRP multi-veicolo con algoritmo Clarke-Wright Savings (piano Business, fino a 10 veicoli).

Come OptiRoad risolve il tuo TSP

A ogni clic su Ottimizza nella dashboard, OptiRoad applica la seguente strategia:

1. Geocodifica i tuoi indirizzi (li trasforma in coordinate GPS) se non lo sono già.
2. Costruisce la matrice delle distanze tra tutti i punti via OpenRouteService (o Google Routes come fallback).
3. Se ≤ 10 tappe: brute force, tutte le permutazioni testate, ottimo assoluto garantito.
4. Altrimenti: nearest neighbor per costruire il percorso iniziale, poi 2-opt per affinare con iterazioni successive.
5. Se VRPTW attivato: il solver rispetta le fasce orarie tramite un approccio Earliest Deadline First, segnalando ogni ritardo prevedibile.
6. Se multi-veicolo: Clarke-Wright Savings per ripartire le tappe, poi TSP locale su ciascun percorso.

Tutto in pochi secondi (3 secondi per 15 tappe, fino a 20 secondi per 150 tappe con timeout adattivo).

In pratica: cosa cambia per te

Su un percorso tipico di 30 consegne in zona urbana:

• Senza ottimizzazione: circa 120 km, circa 5h di strada
• Con OptiRoad: circa 85 a 90 km, circa 3h30 a 4h di strada
• Guadagno tipico: 25 a 30% di distanza, 20 a 30% di tempo

Su 200 giorni lavorativi all'anno, sono migliaia di chilometri e centinaia di ore risparmiate. E tutto questo viene dal risolvere un problema che si chiama "il TSP" dal 1930.

Domande frequenti

Quanti indirizzi può ottimizzare OptiRoad?

Fino a 150 tappe per percorso. Fino a 10 tappe, il brute force prova tutte le combinazioni e garantisce l'ottimo assoluto. Oltre, OptiRoad passa alle euristiche (nearest neighbor e poi 2-opt), che restano eccellenti anche sui percorsi grandi.

Il percorso è sempre il più corto possibile?

Sì, ed è garantito matematicamente fino a 10 tappe. Oltre, il risultato si colloca tipicamente a meno del 5% dall'ottimo teorico grazie al 2-opt: uno scarto impercettibile sul campo, con un calcolo quasi istantaneo.

Mi serve un punto di partenza?

Sì. Serve un punto di partenza: un deposito o un indirizzo di casa. Il punto di arrivo, invece, è opzionale: se non ne indichi uno, OptiRoad considera che torni al tuo punto di partenza (percorso ad anello).

Quanto tempo richiede il calcolo?

Pochi secondi. OptiRoad usa un timeout adattivo: circa 3 secondi per i percorsi piccoli, fino a 20 secondi per 150 tappe. Se il limite viene raggiunto, lo strumento restituisce comunque il miglior percorso trovato. In pratica hai il tuo ordine pronto prima ancora di aver acceso il motore.

Per andare oltre

Se vuoi vedere l'algoritmo all'opera sui tuoi indirizzi, il piano gratuito di OptiRoad include 5 percorsi al mese fino a 10 tappe, esattamente la zona dove il brute force garantisce l'ottimo assoluto. Il modo migliore per misurare concretamente quanto guadagnerai.

Vuoi approfondire le varianti (fasce orarie, multi-veicolo)? Continua con gli altri articoli del blog o leggi la documentazione API.