Classical and practical travelling salesman problem

  • Finds a tour of minimum total weight
  • You must find an upper and lower bound to know whether your solution is optimal enough to be accepted
  • In the classical problem,  each vertex must be visited exactly once before returning to the start.
  • In the practical problem, each vertex must be visited at least once before returning to the start.
  • If you convert the network into a complete network of least distances, the classical and practical travelling salesmen problems are equivalent.


  • Triangle inequality:
    • The longest side of any triangle <= the sum of the two shorter sides
  • If the triangle inequality doesn't hold true for one or more triangles in a network, replace the longest arc by the sum of the two shorter ones.

  • A table of least distances is a distance matrix for a complete network of least distances.