भारतीय प्रौद्योगिकी संस्थान दिल्ली
Indian Institute of Technology, Delhi
  • Login
View Item 
  •   Home
  • Faculty Research Publications
  • Electrical Engineering
  • View Item
  •   Home
  • Faculty Research Publications
  • Electrical Engineering
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Parallel techniques for solving large scale travelling salesperson problems

Thumbnail
View/Open
ravikumarpar92.pdf


Collections
  • Electrical Engineering [463]
Metadata
Show full item record
Author: Ravikumar, C P

Advisor: Advisor

Date: 1992

Publisher:
Citation: Microproce

Series/Report no.:
Item Type: Article

Keywords: combinatorial search; parallel algorithms; intel iPSC/2; alliant FX/80; circuit partition; travelling salesperson problem

Abstract: As 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.
Contact Us
Shankar B. Chavan
Computer Applications Division
Central Library, IIT Delhi
shankar.chavan@library.iitd.ac.in
NDLTD
Shodhganga
NDL
ePrints@IISc
etd@IISc
IR@IIT Bombay
NewsClips @IITD
  • Facebook
  • twitter
  • youtube
  • instagram
  • pinterest
  • Linkedin

Browse

All of IITDCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

My Account

LoginRegister
Contact Us
Shankar B. Chavan
Computer Applications Division
Central Library, IIT Delhi
shankar.chavan@library.iitd.ac.in
NDLTD
Shodhganga
NDL
ePrints@IISc
etd@IISc
IR@IIT Bombay
NewsClips @IITD
  • Facebook
  • twitter
  • youtube
  • instagram
  • pinterest
  • Linkedin