The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.5.4 Traveling Salesman Problem

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A weighted graph G.

Problem: Find the cycle of minimum cost visiting all of the vertices of G exactly once.

Excerpt from The Algorithm Design Manual: The traveling salesman problem is the most notorious NP-complete problem. This is a function of its general usefulness, and because it is easy to explain to the public at large. Imagine a traveling salesman who has to visit each of a given set of cities by car.

Although the problem arises in transportation applications, its most important applications arise in optimizing the tool paths for manufacturing equipment. For example, consider a robot arm assigned to solder all the connections on a printed circuit board. The shortest tour that visits each solder point exactly once defines the most efficient path for the robot. A similar application arises in minimizing the amount of time taken by a graphics plotter to draw a given figure.


Implementations

  • Concorde TSP Solver (C) (rating 10)
  • GOBLIN: A Graph Object Library for Network (C++) (rating 9)
  • TSP solvers (C) (rating 9)
  • Keld Helsgaun's traveling salesman (C) (rating 8)
  • JGraphT: Java graph library (Java) (rating 5)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 4)

  • Recommended Books

    The Traveling Salesman Problem and Its Variations by G. Gutin and A. Punnen The Traveling Salesman Problem : A Guided Tour of Combinatorial Optimization by E.L. Lawler (Editor) and A. H. Rinnooy-Kan

    Related Links

  • Georgia Tech's Traveling Salesman Problem page
  • Lodi and Punnan's TSP Software
  • Library for testing TSPs

    Related Problems


      
    Convex Hull
      
    Hamiltonian Cycle
      
    Minimum Spanning Tree
      
    Satisfiability



    This page last modified on 2008-07-10 .
    www.algorist.com