Hardware implementation of 2-Opt local search algorithm for the traveling salesman problemHardware implementation of 2-Opt local search algorithm for the traveling salesman problem Πλήρης Δημοσίευση σε Συνέδριο Conference Full Paper 2015-11-152007enIn this paper we discuss how one of the most famous local optimization algorithms for the Traveling Salesman Problem, the 2-Opt, can be efficiently implemented in hardware for Euclidean TSP instances up to a few hundred cities. We introduce the notion of "symmetrical 2-Opt moves" which allows us to uncover fine-grain parallelism when executing the specified algorithm. We propose a novel architecture that exploits this parallelism. A subset of the TSPLIB benchmark is used to evaluate the proposed architecture and its ASIC implementation, which exhibits better final results and an average speedup of 20 when compared with the state-of-the-art software implementation. Our approach produces, to the best of our knowledge, the fastest to date TSP 2-Opt solver for small-scale Euclidean TSP instances.http://creativecommons.org/licenses/by/4.0/41 - 4718th IEEE/IFIP International Workshop on Rapid System Prototyping Papaefstathiou Ioannis Παπαευσταθιου Ιωαννης Pnevmatikatos Dionysios Πνευματικατος Διονυσιος Mavroidis I. Institute of Electrical and Electronics Engineers