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
Abstract
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.
Keywords
Hrčak ID:
150514
URI
Publication date:
30.3.1993.
Visits: 545 *