Skip to the main content

Original scientific paper

Connection Machine Implementation of a Tabu Search Algorithm for the Traveling Salesman Problem

Jaishankar Chakrapani ; Department of Applied Mathematics and Statistics, State University of New York at Stony Brook
Jadranka Skorin-Kapov ; Harriman School for Management and Policy, State University of New York at Stony Brook

Full text: english pdf 4.452 Kb

page 29-36

downloads: 193



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.


Hrčak ID:



Visits: 367 *