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 journalArticleScientificpeer-review

    35 Citations (Scopus)


    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 languageEnglish
    Pages (from-to)175-182
    Number of pages8
    JournalFuture Generation Computer Systems
    Issue number2
    Publication statusPublished - 1995


    Dive into the research topics of 'A parallel 2-opt algorithm for the traveling salesman problem'. Together they form a unique fingerprint.

    Cite this