Connection Machine implementation of a tabu search algorithm for the traveling salesman problem
Jaishankar Chakrapani, Jadranka Skorin‐Kapov · Hrčak Portal of scientific journals of Croatia (University Computing Centre) · 1993
A tabu search algorithm for the traveling salesman problem (TSP) is developed. The algorithm is based on the well known 2-opt move which is implemented in parallel on the connection machine CM-2. This involves decomposing the evaluation of the whole 2-opt neighborhood into small independent steps that can be executed in parallel by different processors. The implementation is efficient and highly scalable. Implementation details and results of computation for some TSPs from the literature are presented.