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.

The best book available for this problem is The Traveling Salesman Problem : A Guided Tour of Combinatorial Optimization by E.L. Lawler (Editor) and A. H. Rinnooy-Kan.


Implementations

  • TSP solvers (C) (rating 8)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 6)
  • Discrete Optimization Methods (Pascal) (rating 5)
  • GA Playground (Java) (rating 4)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 3)
  • Combinatorica (Mathematica) (rating 3)

    Related Problems

  • Convex Hull
  • Hamiltonian Cycle
  • Minimum Spanning Tree
  • Satisfiability


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .