Un tecnico deve visitare venti clienti in giornata e tornare in sede. In che ordine conviene passare per percorrere meno chilometri? È il problema del commesso viaggiatore (in inglese TSP, Travelling Salesman Problem), probabilmente il problema di ottimizzazione combinatoria più studiato in assoluto.
Enunciarlo è facile: dato un insieme di città e le distanze tra ogni coppia, trovare il giro più corto che le visiti tutte una sola volta e torni al punto di partenza. Risolverlo all'ottimo è un'altra storia.
Perché è difficile
Con n città, fissata quella di partenza, i giri possibili sono (n − 1)!/2 se le distanze sono simmetriche. Con 10 città sono 181.440, gestibili. Con 20 sono circa 6 · 10^16. Con 50 il numero supera di gran lunga qualunque possibilità di enumerazione.
Il TSP è NP-difficile: non si conoscono algoritmi esatti che lo risolvano in tempo polinomiale. La programmazione dinamica di Held e Karp porta il costo a circa n² · 2^n, enormemente meglio dell'enumerazione ma ancora esponenziale. Per istanze grandi i risolutori esatti basati su programmazione intera e piani di taglio ottengono risultati notevoli, ma nella pratica quotidiana si usano soprattutto euristiche: algoritmi veloci che danno giri buoni senza garanzia di ottimo.
Euristiche costruttive
Costruiscono un giro da zero.
Vicino più prossimo
Si parte da una città e si va sempre alla città non ancora visitata più vicina. Alla fine si torna alla partenza. È semplicissima e veloce, ma tende a lasciare per ultime alcune città lontane e isolate, costringendo a lunghi spostamenti finali. Su istanze tipiche produce giri sensibilmente più lunghi dell'ottimo.
Inserimento
Si parte da un piccolo giro, per esempio tra due città, e si inseriscono le altre una alla volta nella posizione che allunga meno il giro. Cambia il criterio con cui si sceglie la prossima città da inserire:
- inserimento più vicino: la città più vicina al giro attuale;
- inserimento più lontano: la città più lontana dal giro; sembra controintuitivo, ma costruisce presto lo «scheletro» del percorso e spesso dà risultati migliori;
- inserimento più economico: la città il cui inserimento costa meno.
Approssimazione con l'albero ricoprente
Se le distanze rispettano la disuguaglianza triangolare (andare direttamente da A a C non costa più che passare per B), c'è un metodo con garanzia:
- costruisci l'albero ricoprente minimo delle città;
- visita l'albero in profondità, annotando le città nell'ordine in cui le incontri per la prima volta;
- collega le città in quell'ordine e chiudi il giro.
Il giro ottenuto è al massimo il doppio dell'ottimo. Il motivo: l'albero costa meno del giro ottimo (togliendo un arco al giro si ottiene un albero ricoprente), la visita completa percorre ogni arco dell'albero due volte, e le scorciatoie grazie alla disuguaglianza triangolare non allungano. L'algoritmo di Christofides migliora la garanzia a 1,5 aggiungendo un matching di costo minimo tra le città di grado dispari dell'albero.
Miglioramento: la mossa 2-opt
Le euristiche costruttive producono giri con difetti evidenti, come percorsi che si incrociano. Nel piano, un giro che si incrocia non è mai ottimo con distanze euclidee: si può sempre accorciare.
La mossa 2-opt toglie due archi (A, B) e (C, D) dal giro e li sostituisce con (A, C) e (B, D), invertendo il tratto intermedio. Se la nuova lunghezza è minore, si accetta la mossa.
def due_opt(giro, d):
migliorato = True
while migliorato:
migliorato = False
for i in range(1, len(giro) - 2):
for j in range(i + 1, len(giro) - 1):
a, b = giro[i - 1], giro[i]
c, e = giro[j], giro[j + 1]
if d[a][c] + d[b][e] < d[a][b] + d[c][e]:
giro[i:j + 1] = reversed(giro[i:j + 1])
migliorato = True
return giro
Qui il giro è una lista che inizia e finisce con la stessa città. Si ripetono le mosse finché nessuna migliora: il risultato è un ottimo locale rispetto a 2-opt.
Esistono mosse più potenti: 3-opt sostituisce tre archi, e l'euristica di Lin-Kernighan combina in modo adattivo mosse di profondità variabile. Le sue implementazioni moderne sono tra i metodi più efficaci noti per il TSP.
Sapere quanto si è lontani dall'ottimo
Un'euristica dà un giro, ma quanto è buono? Servono limiti inferiori:
- il costo dell'albero ricoprente minimo è sempre minore del giro ottimo;
- il limite di Held-Karp, basato sugli 1-alberi con penalità sui vertici, è molto più stretto ed è spesso vicinissimo all'ottimo;
- il rilassamento lineare di una formulazione intera del TSP fornisce un limite simile.
| Metodo | Velocità | Qualità tipica |
|---|---|---|
| Vicino più prossimo | molto alta | discreta |
| Inserimento più lontano | alta | buona |
| Albero ricoprente | alta | garanzia del doppio |
| 2-opt su soluzione iniziale | media | molto buona |
| Lin-Kernighan | media | eccellente |
Varianti reali
Nella pratica il TSP puro è raro. Ci sono finestre orarie dei clienti, più veicoli con capacità limitata, sensi unici che rendono le distanze asimmetriche, tempi di servizio, pause obbligatorie. Questi problemi di instradamento dei veicoli si affrontano con le stesse idee: costruzione, mosse di miglioramento locale e metaeuristiche che permettono di uscire dagli ottimi locali.
In sintesi
- Il TSP cerca il giro più corto che visita ogni città una volta; le combinazioni crescono in modo fattoriale.
- Vicino più prossimo e inserimento costruiscono giri in fretta, con qualità diverse.
- Con la disuguaglianza triangolare, l'albero ricoprente dà un giro al massimo doppio dell'ottimo.
- La mossa 2-opt elimina gli incroci e migliora molto le soluzioni costruttive.
- Limiti inferiori come Held-Karp dicono quanto un giro è lontano dall'ottimo.
