Problemi di routing¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 6 · Dispensa, volume 1 (PDF) · Slide · Esercizi: Problemi di routing
Prerequisiti
-
Da questo modulo, Capitolo 1 «Problemi di ottimizzazione combinatoria»: che cos'è un problema di ottimizzazione combinatoria, come esplode il numero delle soluzioni, e le nozioni di bound primale, bound duale e gap.
-
Dallo stesso capitolo, l'istanza di riferimento del TSP con \(5\) città, che questo capitolo studia in dettaglio.
Obiettivi
Al termine di questo capitolo saremo in grado di:
-
enunciare il TSP, il TSP asimmetrico e il TSP metrico, e descrivere un'istanza e un giro;
-
calcolare la lunghezza di un giro e contare i giri di un'istanza;
-
spiegare perché elencare tutti i giri è senza speranza già con \(20\) città;
-
costruire a mano un primo giro con la nearest neighbour rule;
-
calcolare un lower bound sulla lunghezza ottima a partire dai due archi più corti di ogni città, e misurare il gap rispetto a un giro.
6.1 Panoramica della famiglia¶
-
I problemi di routing di questo capitolo hanno gli stessi dati: un insieme \(\mathscr{V} = \{1,2,\dots,n\}\) di \(n\) città e, per ogni coppia di città distinte \(i,j \in \mathscr{V}\), una distanza \(d_{ij} \in \Z_{\ge 1}\).
-
Una soluzione è un giro, una permutazione \(\sigma\) delle città letta come un percorso chiuso che visita ogni città esattamente una volta; la sua lunghezza \(L(\sigma)\) è la somma delle distanze percorse.
-
L'obiettivo è minimizzare la lunghezza del giro.
Un problema di routing trova un giro più corto attraverso tutte le città. I membri della famiglia differiscono nelle proprietà delle distanze: simmetriche, metriche o asimmetriche.
- La tabella elenca i membri della famiglia, con la sezione che definisce ciascuno di essi.
| Problema | Sigla | Distanze | Sezione |
|---|---|---|---|
| commesso viaggiatore | TSP | simmetriche, \(d_{ij} = d_{ji}\) | 6.2 |
| commesso viaggiatore metrico | TSP metrico | simmetriche, con la disuguaglianza triangolare | 6.6 |
| commesso viaggiatore asimmetrico | ATSP | \(d_{ij}\) può differire da \(d_{ji}\) | 6.6 |
Avanti: 6.2 Il problema del commesso viaggiatore
Esercizi su questo capitolo: Problemi di routing
Approfondimento: che cosa fa il corso su questo problema