Vai al contenuto

Problemi di routing

Catalogo dei problemi di ottimizzazione combinatoria · Catalogo (PDF)

  • Date \(n\) città e la distanza \(d_{ij}\) fra ogni coppia ordinata, una soluzione è un giro che visita ogni città esattamente una volta e torna alla prima.

  • L'obiettivo è minimizzare la lunghezza totale del giro; i membri della famiglia differiscono per le proprietà delle distanze: simmetriche, metriche o asimmetriche.

  • Il problema del ciclo hamiltoniano è il problema di decisione su un grafo: chiede se esiste un giro fatto di lati del grafo.

Problema Sigla Differenza
Problema del commesso viaggiatore TSP Il problema centrale della famiglia.
Problema del commesso viaggiatore metrico TSP metrico Il caso particolare del TSP con la disuguaglianza triangolare, in cui esistono garanzie di approssimazione.
Problema del commesso viaggiatore asimmetrico ATSP Il TSP è il caso particolare dell'ATSP in cui \(d_{ij}=d_{ji}\) per ogni \(i,j\); un'istanza dell'ATSP ha \((n-1)!\) giri.
Problema del ciclo hamiltoniano HCP Con \(d_{ij}=1\) sui lati e una distanza grande altrove, \(G\) è hamiltoniano se e solo se \(z(I_G)=n\): il TSP lo contiene.