Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/F4E3B362-7273-4653-A901-C52BA1DB8358 | ||
| Έτος | 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 https://doi.org/10.1109/RSP.2007.24 | ||
| Εμφανίζεται στις Συλλογές |
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.
Copyright © DIAS 2013
