An efficient parallel cluster-heuristic for large TSPs

Bachem, Achim and Steckemetz, Barthel and Wottawa, Michael (1994) An efficient parallel cluster-heuristic for large TSPs.
Technical Report , 10 p.


We describe an improved clustering heuristic for the Eucledian Traveling Salesman Problem and its parallelization for a distributed memory machine. A geometric decomposition is used for the clustering-stage and special emphasis has been put on the computation of the global tour through the clusters. The heuristic solves problem instances up to 33,000 cities in a few minutes on the parallel machine, while the obtained tour is only a few percent longer than a tour generated by the sequential Lin-Kernighan-algorithm.

Download: [img] Postscript
Download (381kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr94-150
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 11:19