A PARALLEL 2-OPT ALGORITHM FOR THE TRAVELING-SALESMAN PROBLEM

Authors
VERHOEVEN MGA AARTS EHL SWINKELS PCJ
Citation
Mga. Verhoeven et al., A PARALLEL 2-OPT ALGORITHM FOR THE TRAVELING-SALESMAN PROBLEM, Future generations computer systems, 11(2), 1995, pp. 175-182
Citations number
23
Categorie Soggetti
Computer Science Theory & Methods
Journal title
Future generations computer systems → ACNP
ISSN journal
0167739X
Volume
11
Issue
2
Year of publication
1995
Pages
175 - 182
Database
ISI
SICI code
0167-739X(1995)11:2<175:AP2AFT>2.0.ZU;2-H
Abstract
We present a scalable parallel local search algorithm based on data pa rallelism. The concept of distributed neighborhood structures is intro duced, and applied to the Traveling Salesman Problem (TSP). Our parall el local search algorithm finds the same quality solutions as the clas sical 2-opt algorithm and has a good speed-up. The algorithm is implem ented on a Parsytec GCel, consisting of 512 transputers. Its performan ce is empirically analyzed for TSP instances with several thousands of cities.