EPrints@IIT Delhi >
Faculty Research Publicatons  >
Electrical Engineering >

Please use this identifier to cite or link to this item: http://eprint.iitd.ac.in/handle/2074/2520

Full metadata record

DC FieldValueLanguage
dc.contributor.authorRavikumar, C P-
dc.identifier.citationMicroprocessors and Microsystems, 16(3), 149-158p.en
dc.description.abstractAs a hard combinatorial optimization problem, the travelling salesperson problem (TSP) has been of pedagogical interest for more than 50 years. More recently, the problem has generated a great deal of practical interest due to its applications in electronic circuit assembly and the drilling of printed circuit boards. In the simplest terms, the TSP is to find a minimum cost Hamiltonian tour of n cities. Since there is no known polynomial time algorithm to solve the TSP, and since n is quite large for practical problems, it is customary to use heuristic techniques and generate suboptimal tours. Even heuristic algorithms are expensive in CPU time when hundreds (or even thousands) of cities are involved. In this paper, we consider four well known heuristics for the TSP and their parallel implementations. Two constructive algorithms are considered: the farthest insertion heuristic and Christofides' approximation algorithm. Two iterative improvement algorithms are considered: the two-opt and three-opt techniques due to Lin and Kernighan. The results of applying parallel randomized search techniques to large instances of the problem are described. We demonstrate the usefulness of parallel processing in solving hard optimization problems by providing experimental evidence for both speedup improvement and an improvement in the quality of the final solutions. The target machines used for these parallel implementations are the Intel iPSC/2 hypercube and the Alliant FX/80.en
dc.format.extent385088 bytes-
dc.subjectcombinatorial searchen
dc.subjectparallel algorithmsen
dc.subjectintel iPSC/2en
dc.subjectalliant FX/80en
dc.subjectcircuit partitionen
dc.subjecttravelling salesperson problemen
dc.titleParallel techniques for solving large scale travelling salesperson problemsen
Appears in Collections:Electrical Engineering

Files in This Item:

File Description SizeFormat
ravikumarpar92.pdf376.06 kBAdobe PDFView/Open
View Statistics

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback