A parallel 2-opt algorithm for the traveling salesman problem

E.H.L. Aarts; P.C.J. Swinkels; M.G.A. Verhoeven

doi:10.1016/0167-739X(94)00059-N

A parallel 2-opt algorithm for the traveling salesman problem

E.H.L. Aarts, P.C.J. Swinkels, M.G.A. Verhoeven

Research output: Contribution to journal › Article › Scientific › peer-review

38 Citations (Scopus)

Abstract

We present a scalable parallel local search algorithm based on data parallelism. The concept of distributed neighborhood structures is introduced, and applied to the Traveling Salesman Problem (TSP). Our parallel local search algorithm finds the same quality solutions as the classical 2-opt algorithm and has a good speed-up. The algorithm is implemented on a Parsytec GCel, consisting of 512 transputers. Its performance is empirically analyzed for TSP instances with several thousands of cities. Author Keywords: Local search; Traveling Salesman Problem; Data parallelism

Original language	English
Pages (from-to)	175-182
Number of pages	8
Journal	Future Generation Computer Systems
Volume	11
Issue number	2
DOIs	https://doi.org/10.1016/0167-739X(94)00059-N
Publication status	Published - 1995

Access to Document

10.1016/0167-739X(94)00059-N

Cite this

@article{4b5d8f77800a45548ba869a63b30bac2,

title = "A parallel 2-opt algorithm for the traveling salesman problem",

abstract = "We present a scalable parallel local search algorithm based on data parallelism. The concept of distributed neighborhood structures is introduced, and applied to the Traveling Salesman Problem (TSP). Our parallel local search algorithm finds the same quality solutions as the classical 2-opt algorithm and has a good speed-up. The algorithm is implemented on a Parsytec GCel, consisting of 512 transputers. Its performance is empirically analyzed for TSP instances with several thousands of cities. Author Keywords: Local search; Traveling Salesman Problem; Data parallelism",

author = "E.H.L. Aarts and P.C.J. Swinkels and M.G.A. Verhoeven",

year = "1995",

doi = "10.1016/0167-739X(94)00059-N",

language = "English",

volume = "11",

pages = "175--182",

journal = "Future Generation Computer Systems",

issn = "0167-739X",

publisher = "Elsevier B.V.",

number = "2",

}

TY - JOUR

T1 - A parallel 2-opt algorithm for the traveling salesman problem

AU - Aarts, E.H.L.

AU - Swinkels, P.C.J.

AU - Verhoeven, M.G.A.

PY - 1995

Y1 - 1995

N2 - We present a scalable parallel local search algorithm based on data parallelism. The concept of distributed neighborhood structures is introduced, and applied to the Traveling Salesman Problem (TSP). Our parallel local search algorithm finds the same quality solutions as the classical 2-opt algorithm and has a good speed-up. The algorithm is implemented on a Parsytec GCel, consisting of 512 transputers. Its performance is empirically analyzed for TSP instances with several thousands of cities. Author Keywords: Local search; Traveling Salesman Problem; Data parallelism

AB - We present a scalable parallel local search algorithm based on data parallelism. The concept of distributed neighborhood structures is introduced, and applied to the Traveling Salesman Problem (TSP). Our parallel local search algorithm finds the same quality solutions as the classical 2-opt algorithm and has a good speed-up. The algorithm is implemented on a Parsytec GCel, consisting of 512 transputers. Its performance is empirically analyzed for TSP instances with several thousands of cities. Author Keywords: Local search; Traveling Salesman Problem; Data parallelism

U2 - 10.1016/0167-739X(94)00059-N

DO - 10.1016/0167-739X(94)00059-N

M3 - Article

SN - 0167-739X

VL - 11

SP - 175

EP - 182

JO - Future Generation Computer Systems

JF - Future Generation Computer Systems

IS - 2

ER -

A parallel 2-opt algorithm for the traveling salesman problem

Abstract

Access to Document

Fingerprint

Cite this