Problema del commesso viaggiatore

Il problema del commesso viaggiatore è il più semplice fra i problemi di instradamento e di gestione dei processi. Viene spesso indicato con il suo nome inglese, traveling salesman problem o traveling salesperson problem, in acronimo TSP.

Descrizione

Definizione

Il problema del commesso viaggiatore è uno dei casi di studio tipici dell'informatica teorica e della teoria della complessità computazionale. Il nome nasce dalla sua più tipica rappresentazione: dato un insieme di città, e note le distanze tra ciascuna coppia di esse, trovare il tragitto di minima percorrenza che un commesso viaggiatore deve seguire per visitare tutte le città una ed una sola volta e ritornare alla città di partenza.

Modello matematico

Al problema del TSP è associabile un grafo G=(V,A), in cui V è l'insieme degli n nodi (o città) e A è l'insieme degli archi (o strade). Si indica con $c_{ij}$ il costo dell'arco per andare dal nodo i al nodo j (vedi Cammino minimo). Il TSP è simmetrico se $c_{ij}=c_{ji}\forall (i,j)$, altrimenti si dice asimmetrico. A seconda che il problema sia simmetrico o asimmetrico, esso può essere descritto con modelli matematici differenti. Detta $x_{ij}$ la generica variabile binaria tale che $x_{ij}=1$ se l'arco (i,j) appartiene al circuito e $x_{ij}=0$ altrimenti, nel caso più generale di problema asimmetrico, una possibile formulazione matematica del problema è:

$z=\min \sum _{i=1}^{n}\sum _{j=1}^{n}c_{ij}x_{ij}\quad (1)$

sottoposto a

${\begin{aligned}&\sum _{i=1}^{n}x_{ij}=1&&j=1,...,n&&(2)\\&\sum _{j=1}^{n}x_{ij}=1&&i=1,...,n&&(3)\\&\sum _{i\in Q}\sum _{j\in V\setminus Q}x_{ij}\geq 1&&\forall Q\subset V,|Q|\geq 1&&(4)\\&x_{ij}\in \{0,1\}&&i,j=1,...,n\end{aligned}}$

La relazione (1) è la funzione obiettivo che rappresenta la minimizzazione del costo del cammino. I vincoli (2) e (3) indicano che in ogni nodo i entra ed esce un solo arco, e sono detti vincoli di assegnazione. Poiché tali vincoli non assicurano una soluzione costituita da un unico circuito vengono inseriti anche i vincoli (4) che assicurano l'assenza di sottocircuiti. In particolare essi definiscono che, comunque si scelga un sottoinsieme proprio di nodi Q in V, deve esistere almeno un arco che colleghi un nodo di Q con un nodo non appartenente a Q.

Complessità computazionale - NP-completezza

Non esistono algoritmi efficienti per la risoluzione del TSP, l'unico metodo di risoluzione è rappresentato dall'enumerazione totale, ovvero nell'elaborazione di tutti i possibili cammini sul grafo per la successiva scelta di quello migliore. Tuttavia, la complessità dell'operazione la rende impraticabile per grafi di dimensioni comuni nei problemi reali: in un grafo di n nodi, bisognerà calcolare, nel caso peggiore in cui ogni nodo è connesso con tutti gli altri, n! (n fattoriale) possibili cammini. Il TSP rappresenta inoltre un esempio di problema di programmazione lineare intera nel quale risulta pressoché inattuabile ottenere valutazioni approssimate tramite la tecnica del rilassamento continuo poiché il problema di PL risultante si troverebbe ad avere un numero di vincoli che cresce in modo esponenziale con i nodi, rendendo così intrattabili le matrici associate ad esso. Per scopi pratici, il metodo della ricottura simulata (simulated annealing) ha effettivamente risolto il TSP.
Una rete di mille nodi, molto più comune di quanto si possa pensare, comincerebbe già a creare seri problemi computazionali.

È stato dimostrato che TSP è un problema NP-difficile (più precisamente, è NP-completo per la classe di complessità FP^NP; v. problema di funzione), e la versione decisionale del problema ("dati i pesi e un numero x, decidere se ci sia una soluzione migliore di x") è NP-completa.

Il problema rimane NP-difficile anche in molte sue versioni ridotte, come nel caso in cui le città siano in un piano con distanze euclidee. Inoltre, omettere la condizione di visitare una città "una e una sola volta" non rimuove la NP-difficoltà, poiché si nota facilmente che nel caso piano un cammino ottimale visiterebbe comunque le città una volta sola.

Anche il problema del commesso viaggiatore per collo di bottiglia è NP-difficile.

La seguente frase è un malinteso comune: "La risoluzione di problemi NP-completi (e quindi il TSP) richiede tempo esponenziale." Se fosse vero, ciò implicherebbe P ≠ NP, che è ancora un problema aperto. Inoltre, alcuni problemi NP-completi in realtà non soltanto hanno algoritmi in esecuzione in tempo superpolinomiale, ma anche subesponenziale come O(2^√nn). Ad esempio, i problemi dell'insieme indipendente e dell'insieme dominante per i grafi planari sono NP-completi, ma possono essere risolti in tempo subesponenziale utilizzando il teorema del separatore planare.

Algoritmi

Le strategie tradizionali di soluzione per i problemi NP-difficili sono:

• trovare un caso specifico del problema (sottoproblema) per il quale sia possibile o una soluzione esatta o un'euristica migliore.
• progettare algoritmi euristici, cioè algoritmi che producono soluzioni probabilmente buone, ma impossibili da provare essere ottimali
• progettare algoritmi per trovare la soluzione esatta, ragionevolmente veloci solo per problemi con un numero di città relativamente basso

Per condurre test sugli algoritmi TSP è stata sviluppata la libreria TSPLIB, che contiene istanze d'esempio del problema TSP e relative varianti (v. nella sezione voci correlate). Molti di questi esempi sono liste di città e schemi di circuiti stampati.

Algoritmi esatti

• Algoritmi branch and bound che possono essere usati per problemi TSP con 50-60 città.
• Algoritmi che procedono per raffinamenti successivi usando tecniche derivate dalla programmazione lineare, adatti per problemi fino a 120-200 città.
• Implementazioni recenti di branch and bound e branch and cut basati sulla programmazione lineare, adatti per problemi contenenti fino a 5.000 città. Questo approccio è stato seguito anche per risolvere situazioni con 33.810 città.

Nel 2001 è stata trovata per esempio la soluzione esatta a un problema di circa 15'000 città contenuto in TSPLIB, usando il metodo cutting plane, basato sulla programmazione dinamica e originariamente proposto nel 1954 da George Dantzig, Delbert Ray Fulkerson e Selmer Johnson.
Il calcolo fu eseguito alla Rice University e della Princeton University, da una rete di 110 processori. Il tempo di elaborazione totale fu equivalente a circa 23 anni su un singolo processore Alpha a 500 MHz. Nel maggio 2004 fu risolto il TSP per tutte le circa 25000 città della Svezia: risultò un percorso di circa 72.500 chilometri. Notevole è che questo percorso fu poi provato essere anche il migliore.

Nel marzo 2005, il TSP riguardante la visita di tutti i circa 34'000 punti in una scheda di circuito fu risolto usando CONCORDE: fu trovato un percorso di circa 66 milioni di unità, e provato che non poteva esisterne uno migliore. L'esecuzione richiese approssimativamente circa 16 anni CPU.

Euristiche

Ad oggi sono stati progettati vari algoritmi approssimati, che hanno un'"alta" probabilità di produrre una "buona" soluzione "velocemente". I metodi moderni possono trovare soluzioni in tempo ragionevolmente accettabile per problemi estremamente grandi (milioni di città), con un'alta probabilità che siano differenti del 2-3% dalla soluzione esatta.

Esistono vari tipi d'euristiche.

Euristiche costruttive

• L'algoritmo nearest neighbor, che normalmente è abbastanza vicino alla soluzione ottima, e non impiega troppo tempo. Sfortunatamente, è possibile provare la bontà della soluzione solo in casi particolari del TSP. Nel caso generale, esiste sempre un esempio in cui il nearest neighbor produce una soluzione pessima.

Raffinamenti successivi

• Euristica Pairwise exchange, o euristica di Lin-Kernighan.
• Euristica k-opt

Casi speciali

Locazioni particolari

• Un caso particolare di soluzione banale si ha quando le città sono disposte sul perimetro di un poligono convesso.
• Un buon esercizio sugli algoritmi combinatori riguarda la soluzione del TSP per un insieme di città situate lungo due cerchi concentrici.

Disuguaglianza triangolare e algoritmo di Christofides

Una naturale restrizione del TSP è la disuguaglianza triangolare. Cioè, per tre città qualsiasi $A$, $B$ e $C$, la distanza tra $A$ e $C$ deve essere al massimo la distanza da $A$ a $B$ più la distanza da $B$ a $C$. Molti casi reali di problemi TSP soddisfano questo vincolo.

In questo caso, si ha un algoritmo di approssimazione con fattore di approssimazione costante (grazie a Christofides, 1975), che produce sempre un percorso lungo al massimo 2 volte il percorso ottimo.

La lunghezza dell'albero di copertura minimo della rete è un limite inferiore naturale per la lunghezza del percorso ottimale. Nel TSP con disuguaglianza triangolare è possibile determinare un limite superiore in termini dell'albero di copertura minimo, e progettare un algoritmo che abbia un limite superiore dimostrabile sulla lunghezza della soluzione.

Il primo e più semplice algoritmo è:

1. costruire l'albero di copertura minimo (1-albero)
2. Considerare solo i nodi di grado dispari e costruire il "perfect matching"
3. aggiungere il matching al grafo: ora tutti i nodi avranno grado pari. Questo produce un grafo euleriano.
4. trovare al suo interno un circuito euleriano. Ovviamente, la sua lunghezza è il doppio della lunghezza dell'albero.
5. convertire il circuito euleriano in un ciclo hamiltoniano nel seguente modo: percorrendo il ciclo euleriano, ogni volta che si sta per toccare un vertice già visitato, saltarlo e cercare di raggiungere il prossimo (sempre seguendo il cammino euleriano).

È facile dimostrare che l'ultimo passo funziona. Inoltre, grazie alla disuguaglianza triangolare, ogni volta che si salta un vertice al passo 4 si ha di fatto una scorciatoia, garantendo che la lunghezza del ciclo non aumenti. Questo ci permette di avere una soluzione che sicuramente non è più lunga del doppio di quella ottima.

L'algoritmo di Christofides segue un approccio simile, ma combina l'albero di copertura minimo con una soluzione di un altro problema, il minimum-weight perfect matching. Questo garantisce una soluzione che è al massimo 2 volte quella ottimale. È dal 1975 che il tentativo di ridurre la costante 2 è un problema aperto.

TSP euclideo

TSP euclideo o TSP planare, è il caso particolare in cui si usano le ordinarie distanze euclidee. Nonostante il problema rimanga NP-difficile, molte euristiche lavorano meglio.

Il TSP euclideo è un caso particolare del TSP con disuguaglianza triangolare, poiché le distanze nel piano obbediscono a tale vincolo; ciò nonostante sembra essere più semplice del caso generale con disuguaglianza triangolare. Per esempio, l'albero di copertura minimo del grafo associato a un caso di TSP euclideo è un albero di copertura minimo euclideo e come tale può essere calcolato in tempo $O(n\log {n})$ per $n$ punti . Questo permette all'algoritmo illustrato in precedenza di computare più velocemente.

In generale, per ogni $c>0$ esiste un algoritmo polinomiale che individua, su qualsiasi grafo, un percorso lungo al massimo $(1+c)$ volte quello ottimale (Arora, 1997); questo è detto schema d'approssimazione polinomiale. Questo algoritmo è però troppo lento nella pratica per poter essere utilizzato; al suo posto vengono usate euristiche che danno garanzie più deboli ma che lavorano meglio nei casi di TSP euclideo piuttosto che in casi generali.

TSP asimmetrico

Il più delle volte si ha che la distanza tra due nodi della rete TSP è la stessa in entrambe le direzioni. Il caso generale in cui la distanza da $A$ a $B$ non sia uguale alla distanza da $B$ ad $A$ è chiamato TSP asimmetrico. Un esempio pratico può essere la ricerca di un percorso nelle strade di una città, in cui sono presenti sensi unici.

Voci correlate

• Ricerca operativa
• Vehicle routing problem

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul problema del commesso viaggiatore
• Wikibooks - Problema del commesso viaggiatore con il linguaggio Julia

Collegamenti esterni

• Commesso viaggiatore, problema del, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• Traveling Salesman Problem (TSP), in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) traveling salesman problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Traveling Salesman Problem, su MathWorld, Wolfram Research.
• (EN) travelling salesman problem, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• (EN) TSPLIB, su iwr.uni-heidelberg.de. URL consultato il 4 gennaio 2006 (archiviato dall'url originale il 25 marzo 2017).
• (EN) Pagina dedicata al TSP, su tsp.gatech.edu. URL consultato il 4 gennaio 2006 (archiviato dall'url originale il 26 dicembre 2008).
• Rete di Kohonen Archiviato l'11 giugno 2007 in Internet Archive. applicata al problema del commesso viaggiatore (in 3 dimensioni)