Problema del commesso viaggiatore

Da Wikipedia, l'enciclopedia libera.

Il problema del commesso viaggiatore, o TSP (dall'inglese Travelling Salesman Problem) è un problema di teoria dei grafi, uno dei casi di studio tipici dell'informatica teorica e della teoria della complessità.

Formulazione del problema[modifica | modifica sorgente]

Il nome nasce dalla sua più tipica rappresentazione: data una rete di città, connesse tramite delle strade, trovare il percorso di minore lunghezza che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta per poi tornare alla città di partenza.

Espresso nei termini della teoria dei grafi è così formulato: dato un grafo completo pesato, trovare il cammino di costo minore visitando tutti i nodi una sola volta e tornando al nodo di partenza. La rete di città può essere rappresentata come un grafo in cui le città sono i nodi, le strade gli archi e le distanze i pesi sugli archi. La sostanziale differenza rispetto al Ciclo Hamiltoniano si trova nel fatto che quest'ultimo viene formulato su di un grafo privo di pesi.

Può essere dimostrato che specificare o meno il ritorno alla città di partenza non cambia la complessità computazionale del problema.

Il problema è di considerevole importanza pratica, al di là delle ovvie applicazioni nella logistica e nei trasporti. Un esempio classico è la costruzione di circuiti stampati, nella pianificazione del percorso del trapano per creare i fori nella piastra. Nelle applicazioni di foratura o di rifinitura automatica eseguite da robot, le "città" sono pezzi da rifinire o fori (anche di varie dimensioni) da praticare, e il "costo di viaggio" include i tempi morti (ad esempio il tempo che il robot impiega, se necessario, per cambiare la punta con cui lavora).

Modello matematico[modifica | modifica sorgente]

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. 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 = \sum_{i=1}^{n}\sum_{j=1}^{n}c_{ij}x_{ij} \quad Min! \quad (1)
sottoposto a
\sum_{i=1}^{n}x_{ij}=1 \quad j=1,...,n \quad (2)
\sum_{j=1}^{n}x_{ij}=1 \quad i=1,...,n \quad (3)
\sum_{i \in Q}\sum_{j \in V-Q}x_{ij} \ge 1 \quad \forall Q \subset V, |Q|\ge 1 \quad (4)
x_{ij}=0/1 \quad i,j=1,...,n

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 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[modifica | modifica sorgente]

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 che implica una complessità esponenziale (in base all'approssimazione di Stirling). 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.

NP-completezza[modifica | modifica sorgente]

È stato dimostrato che TSP è un problema NP-difficile (più precisamente, è NP-completo per la classe di complessità FPNP; 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.

Algoritmi[modifica | modifica sorgente]

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

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

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[modifica | modifica sorgente]

  • 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 la soluzione esatta a un problema di 15.112 città contenuto in TSPLIB , usando il metodo cutting plane, basato sulla programmazione dinamica e originariamente proposto nel 1954 da George Dantzig, Ray Fulkerson e Selmer Johnson.
Il calcolo fu eseguito da una rete di 110 processori della Rice University e della Princeton University. Il tempo di elaborazione totale fu equivalente a 22,6 anni su un singolo processore Alpha a 500 MHz. Nel maggio 2004 fu risolto il TSP per tutte le 24.978 città della Svezia: risultò un percorso di circa 72.500 chilometri che fu provato essere ottimale.

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

Euristiche[modifica | modifica sorgente]

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 varie tipologie d'euristiche.

Euristiche costruttive[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]

Casi speciali[modifica | modifica sorgente]

Locazioni particolari[modifica | modifica sorgente]

  • 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[modifica | modifica sorgente]

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 1,5 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 1,5 volte quella ottimale. È dal 1975 che il tentativo di ridurre la costante 1,5 è un problema aperto.

TSP euclideo[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Altri progetti[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica