Problema del commesso viaggiatore (TSP)¶
Definizione 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.
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 \]
-
Che cosa fa il corso su questo problema¶
| Tecnica | Dove |
|---|---|
| Definizione | Cap. 6 «Problemi di routing» |
| Formulazioni | Cap. 13 «Formulazioni dei problemi di routing» |
| Euristiche | Cap. 29 «Algoritmi euristici: definizioni»; Cap. 30 «Euristiche costruttive»; Cap. 31 «Ricerca locale»; Cap. 32 «Metaeuristiche» |
| Euristiche MIP | Cap. 33 «Euristiche MIP per i problemi classici» |
| Approssimazione | Cap. 39 «TSP: il caso generale e il caso metrico» |
| Esercizi | Cap. 6 (7 esercizi); Cap. 13 (5 esercizi); Esercizio 29.3; Cap. 30 (3 esercizi); Cap. 31 (3 esercizi); Cap. 32 (7 esercizi); Cap. 39 (3 esercizi) |
Proprietà¶
-
NP-difficile in senso forte: contiene il problema del ciclo hamiltoniano (Cap. 1).
-
Lower bound \(\lceil \frac12 \sum_i (a_i+b_i) \rceil\), con \(a_i, b_i\) i due lati più corti incidenti nella città \(i\) (Cap. 6).
-
Il nearest neighbour dalla città \(1\) dà \(25\) sull'istanza a cinque città del Cap. 6, il cui ottimo è \(18\) (Cap. 6).
Formulazioni¶
-
Il modello MTZ elimina i sottogiri con \(n-1\) variabili di posizione \(u_i\); il modello DFJ con \(2^{n-1}-n\) vincoli di eliminazione dei sottogiri, aggiunti solo quando sono violati (Cap. 13).
-
Il rilassamento MTZ è debole; sull'istanza del Cap. 6 i bound sono \(16\) (assegnamento), \(17\) (MTZ) e \(18\) (DFJ) (Cap. 13).
Euristiche¶
-
Il nearest neighbour multi-start e le euristiche di inserimento NI, FI e CI raggiungono tutti \(18\) sull'istanza del Cap. 6 (Cap. 30).
-
2-opt valuta ciascuna delle sue \(\frac{n(n-3)}{2}\) mosse in \(O(1)\) e trasforma il giro di lunghezza \(25\) in un giro ottimo in due mosse (Cap. 31).
-
Or-opt e la VND sfuggono agli ottimi locali di 2-opt (Cap. 31).
-
Simulated annealing, tabu search, iterated local search, GRASP e LNS sono confrontati su TSP20 (ottimo \(291\)) (Cap. 32).
Euristiche MIP¶
- Con i vincoli di eliminazione dei sottogiri l'ottimo del rilassamento lineare dell'istanza del Cap. 6 è intero: l'arrotondamento dà \(18\), gap \(0\%\) (Cap. 33).