6.2 Il problema del commesso viaggiatore¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 6 · Capitolo 6: Problemi di routing · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di routing
Definizione 6.1: Problema del commesso viaggiatore
Dati:
-
un insieme \(\mathscr{V} = \{1,2,\dots,n\}\) di \(n\) città,
-
per ogni coppia di città distinte \(i,j \in \mathscr{V}\), una distanza \(d_{ij} \in \Z_{\ge 1}\), con \(d_{ij}=d_{ji}\),
il problema del commesso viaggiatore (TSP) chiede di trovare un percorso chiuso che parte da una città, visita ogni altra città esattamente una volta e ritorna alla città di partenza, in modo che la distanza totale percorsa sia minima.
-
Un'istanza del TSP è specificata da:
-
un numero intero:
- il numero di città \(n \in \Z_{\ge 3}\),
-
una matrice simmetrica di numeri interi di dimensione \(n \times n\):
- \(D=(d_{ij})\), che contiene le distanze; gli elementi diagonali non si usano.
-
-
Una soluzione ammissibile del TSP, detta giro, è una permutazione delle città
\[ \sigma = (\sigma_1,\sigma_2,\dots,\sigma_n), \]letta come il percorso chiuso \(\sigma_1 \to \sigma_2 \to \dots \to \sigma_n \to \sigma_1\). La sua lunghezza è
\[ L(\sigma) = \sum_{k=1}^{n-1} d_{\sigma_k \sigma_{k+1}} + d_{\sigma_n \sigma_1}, \]dove l'ultimo termine è la distanza percorsa per ritornare alla città di partenza.
-
Permutazioni diverse possono descrivere lo stesso giro: la città di partenza può essere una qualunque delle \(n\) città e, poiché le distanze sono simmetriche, il giro può essere percorso in entrambi i versi.
Data un'istanza del TSP, il TSP si può enunciare formalmente come:
\[\begin{equation*} \label{TSP} \tilde{\sigma} \in \argmin_{\sigma} \left\{ L(\sigma) = \sum_{k=1}^{n-1} d_{\sigma_k \sigma_{k+1}} + d_{\sigma_n \sigma_1} \;:\; \sigma \text{ è una permutazione di } \mathscr{V} \right\}. \tag{6.1} \end{equation*}\] -
Indichiamo con \(z(I)\) la lunghezza di un giro ottimo \(\tilde{\sigma}\) dell'istanza \(I\).
6.2.1 Ipotesi¶
-
Facciamo le seguenti ipotesi:
-
Ci sono almeno tre città (con una o due città c'è un solo percorso). Formalmente:
\[ n \ge 3 \] -
Le distanze sono simmetriche (andare da \(i\) a \(j\) costa quanto andare da \(j\) a \(i\)). Formalmente:
\[ d_{ij}=d_{ji},~~~~ \forall i,j \in \mathscr{V},~ i\neq j \]
-
Esempio 6.1: Istanza del TSP
Consideriamo un insieme \(\mathscr{V}=\{1,2,3,4,5\}\) di \(5\) città (\(n=5\)), con le seguenti distanze:
L'istanza si può disegnare come un grafo completo, con un nodo per ogni città e un arco, etichettato con la distanza, per ogni coppia di città. Gli archi in grassetto formano il giro \(\sigma=(1,3,5,2,4)\), e le città sono disegnate nell'ordine del giro:
La sua lunghezza è \(L(\sigma)=d_{13}+d_{35}+d_{52}+d_{24}+d_{41}=2+7+4+3+2=18\).
6.3 Contare i giri¶
Proposizione 6.2
Un'istanza del TSP con \(n \ge 3\) città ha
giri distinti.
-
Le permutazioni delle città sono \(n!\). Ogni giro è descritto da \(n\) permutazioni, una per ogni possibile città di partenza, quindi ci sono \(n!/n=(n-1)!\) ordinamenti ciclici delle città.
-
Le distanze sono simmetriche, quindi il giro percorso all'indietro ha la stessa lunghezza e non è una nuova soluzione: ogni giro è contato due volte, e dividiamo per \(2\).
Esempio 6.2: enumerazione dei giri
L'istanza dell'Esempio 6.1 ha \(\frac{(5-1)!}{2}=12\) giri distinti, che si possono enumerare:
| giro | \(L\) | giro | \(L\) | giro | \(L\) |
|---|---|---|---|---|---|
| \((1,3,5,2,4)\) | \(18\) | \((1,3,4,2,5)\) | \(22\) | \((1,2,3,5,4)\) | \(25\) |
| \((1,3,2,5,4)\) | \(19\) | \((1,4,3,2,5)\) | \(23\) | \((1,3,2,4,5)\) | \(25\) |
| \((1,2,5,3,4)\) | \(22\) | \((1,2,4,5,3)\) | \(24\) | \((1,4,2,3,5)\) | \(25\) |
| \((1,2,5,4,3)\) | \(22\) | \((1,2,4,3,5)\) | \(28\) | ||
| \((1,2,3,4,5)\) | \(29\) |
Quindi il giro \(\sigma=(1,3,5,2,4)\) è l'unico giro ottimo, e \(z(I)=18\).
-
Il numero di giri cresce più velocemente di qualunque funzione esponenziale:
\[ \begin{array}{rrrrr} \hline {n} & {5} & {10} & {15} & {20} \\ \hline {\frac{(n-1)!}{2}} & {12} & {181\,440} & {\approx 4.4\cdot 10^{10}} & {\approx 6.1\cdot 10^{16}} \\ \hline \end{array} \] -
Un calcolatore che valuta \(10^9\) giri al secondo impiega circa \(6.1\cdot 10^{7}\) secondi, ossia circa due anni, per elencare i giri di \(20\) città. L'enumerazione è quindi utile solo come verifica su istanze piccolissime, e gli algoritmi di questo corso devono fare di meglio.
6.4 Un primo giro a mano¶
- Il modo più semplice per costruire un giro è la nearest neighbour rule: si parte da una città e, finché ci sono città non visitate, ci si sposta nella città non visitata più vicina; alla fine si ritorna alla città di partenza. In caso di pareggio prendiamo la città di indice minimo.
Esempio 6.3: nearest neighbour dalla città \(1\)
Sull'istanza dell'Esempio 6.1, partendo dalla città \(1\):
-
da \(1\) le città più vicine sono \(3\) e \(4\), entrambe a distanza \(2\): andiamo in \(3\);
-
da \(3\) le città non visitate \(2\) e \(4\) sono entrambe a distanza \(4\): andiamo in \(2\);
-
da \(2\) la città non visitata più vicina è \(4\), a distanza \(3\); poi resta solo \(5\), a distanza \(d_{45}=7\);
-
ritorniamo da \(5\) a \(1\) a distanza \(d_{51}=9\).
Il giro è \(\sigma=(1,3,2,4,5)\), di lunghezza \(2+4+3+7+9=25\).
-
Gli ultimi archi del giro nearest neighbour sono forzati, e possono essere molto lunghi: qui l'arco finale \(\{5,1\}\) costa \(9\). Il giro di lunghezza \(25\) è peggiore di quello ottimo, di lunghezza \(18\), di \(7\).
-
Dal solo giro nearest neighbour non possiamo dire quanto siamo lontani dall'ottimo: serve un lower bound.
6.5 Un lower bound combinatorio¶
- Per una città \(i\), siano \(a_i \le b_i\) le due distanze più piccole da \(i\) alle altre città.
Osservazione 6.3
Per ogni istanza simmetrica del TSP, la lunghezza ottima soddisfa
-
In un giro, in ogni città si entra con un arco e se ne esce con un altro, quindi ogni città ha esattamente due archi del giro, lunghi almeno \(a_i\) e \(b_i\) rispettivamente.
-
Sommando su tutte le città, ogni arco del giro è contato due volte, una per ciascuna delle sue città estreme: quindi \(2L(\sigma) \ge \sum_i (a_i + b_i)\) per ogni giro \(\sigma\).
-
Le distanze sono intere, quindi lo è anche \(L(\sigma)\), e possiamo arrotondare il bound per eccesso.
Esempio 6.4: il bound sull'istanza di riferimento
Per l'istanza dell'Esempio 6.1 le due distanze più piccole di ogni città sono:
| città \(i\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | somma |
|---|---|---|---|---|---|---|
| \(a_i\) | \(2\) | \(3\) | \(2\) | \(2\) | \(4\) | |
| \(b_i\) | \(2\) | \(4\) | \(4\) | \(3\) | \(7\) | |
| \(a_i+b_i\) | \(4\) | \(7\) | \(6\) | \(5\) | \(11\) | \(33\) |
Quindi \(z(I) \ge \lceil 33/2 \rceil = 17\). Insieme al giro nearest neighbour otteniamo
un gap assoluto di \(8\), ossia un gap relativo di \(\frac{8}{17} \approx 47.1\%\). Il giro \((1,3,5,2,4)\) di lunghezza \(18\) ne chiude la maggior parte, e solo l'enumerazione dei \(12\) giri dimostra che \(18\) è ottimo.