Show simple item record

dc.contributor.authorRavikumar, C P
dc.date.accessioned2007-02-27T03:31:48Z
dc.date.accessioned2019-02-09T07:42:05Z
dc.date.available2007-02-27T03:31:48Z
dc.date.available2019-02-09T07:42:05Z
dc.date.issued1992
dc.identifier.citationMicroprocessors and Microsystems, 16(3), 149-158p.en
dc.identifier.urihttp://localhost:8080/xmlui/handle/12345678/2520
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.format.mimetypeapplication/pdf
dc.language.isoenen
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
dc.typeArticleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record