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.

Abstract

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.


Actions:
Download: [img] Postscript
Download (381kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Paper (Technical Report)
Citations: 0 (Google Scholar) |
Uncontrolled Keywords: heuristics Lin-Kernighan message passing parallel algorithms traveling salesman problem
Subjects:
  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B05 Inventory, storage, reservoirs

  • 90-XX Operations research, mathematical programming > 90-08 Computational methods

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C27 Combinatorial optimization

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R99 None of the above, but in this section

    		•
    Divisions: Mathematical Institute
    Related URLs:
      Deposit Information:
      ZAIK Number: zpr94-150
      Depositing User: Archive Admin
      Date Deposited: 02 Apr 2001 00:00
      Last Modified: 19 Jan 2012 11:19
      URI: http://e-archive.informatik.uni-koeln.de/id/eprint/150