Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/F4E3B362-7273-4653-A901-C52BA1DB8358 | - |
| Identifier | https://doi.org/10.1109/RSP.2007.24 | - |
| Language | en | - |
| Title | Hardware implementation of 2-Opt local search algorithm for the traveling salesman problem | en |
| Creator | Papaefstathiou Ioannis | en |
| Creator | Παπαευσταθιου Ιωαννης | el |
| Creator | Pnevmatikatos Dionysios | en |
| Creator | Πνευματικατος Διονυσιος | el |
| Creator | Mavroidis I. | en |
| Publisher | Institute of Electrical and Electronics Engineers | en |
| Content Summary | In 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. | en |
| Type of Item | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Type of Item | Conference Full Paper | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2015-11-15 | - |
| Date of Publication | 2007 | - |
| Bibliographic Citation | I. Papaefstathiou, D. Pnevmatikatos, I, Mavroidis, "Hardware Implementation of 2-Opt Local Search Algorithm for the Traveling Salesman Problem," in 18th IEEE/IFIP International Workshop on Rapid System Prototyping, 2007, pp. 41 - 47. doi: 10.1109/RSP.2007.24 | en |
Copyright © DIAS 2013
