Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/F4E3B362-7273-4653-A901-C52BA1DB8358 | - |
| Αναγνωριστικό | https://doi.org/10.1109/RSP.2007.24 | - |
| Γλώσσα | en | - |
| Τίτλος | Hardware implementation of 2-Opt local search algorithm for the traveling salesman problem | en |
| Δημιουργός | Papaefstathiou Ioannis | en |
| Δημιουργός | Παπαευσταθιου Ιωαννης | el |
| Δημιουργός | Pnevmatikatos Dionysios | en |
| Δημιουργός | Πνευματικατος Διονυσιος | el |
| Δημιουργός | Mavroidis I. | en |
| Εκδότης | Institute of Electrical and Electronics Engineers | en |
| Περίληψη | 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 |
| Τύπος | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Τύπος | Conference Full Paper | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-11-15 | - |
| Ημερομηνία Δημοσίευσης | 2007 | - |
| Βιβλιογραφική Αναφορά | 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
