In this paper we investigate the design of a coarse-grained parallel implementation of Cga-LK, a hybrid heuristic for the Traveling Salesman Problem (TSP). Cga-LK exploits a compact genetic algorithm in order to generate high-quality tours which are then refined by means of an efficient implementation of the Lin-Kernighan local search heuristic. The results of several experiments conducted on a cluster of workstations with different TSP instances show the efficacy of the parallelism exploitation.
A parallel hybrid heuristic for the TSP
Baraglia R;Perego R
2001
Abstract
In this paper we investigate the design of a coarse-grained parallel implementation of Cga-LK, a hybrid heuristic for the Traveling Salesman Problem (TSP). Cga-LK exploits a compact genetic algorithm in order to generate high-quality tours which are then refined by means of an efficient implementation of the Lin-Kernighan local search heuristic. The results of several experiments conducted on a cluster of workstations with different TSP instances show the efficacy of the parallelism exploitation.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
prod_91400-doc_122397.pdf
accesso aperto
Descrizione: A parallel hybrid heuristic for the TSP
Tipologia:
Versione Editoriale (PDF)
Dimensione
158.58 kB
Formato
Adobe PDF
|
158.58 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
