Skoči na glavni sadržaj

Izvorni znanstveni članak

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

Puni tekst: engleski pdf 4.452 Kb

str. 29-36

preuzimanja: 191



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.

Ključne riječi

Hrčak ID:



Posjeta: 356 *