'The travelling salesman problem' is actually two problems – the classical and practical problems.
In the classical problem, each vertex must be visited exactly once before returning to the start vertex.
In the practical problem, each vertex must be visited at least once before returning to the start vertex.
In both problems we seek to minimise the total distance travelled – technically, we are seeking a walk that gives a minimum tour, with a walk defined as a finite sequence of edges such that the end vertex of each edge in the tour is the start vertex of the next, and a tour defined asa walk that visits every vertex before returning to the starting vertex.
The is no algorithm for the solution of the travelling salesman problem. In practice we find upper and lower bounds for length of the optimal tour. If the upper and lower bounds are close, then the solution may be close enough to the optimal solution to be acceptable.
We can find a lower bound by finding the minimum spanning tree (using Prim's algorithm for example), and then the length of it, and an upper bound by finding the minimum spanning tree and doubling the length, in effect retracing each arc.
The bounds found by the method above are quite wide and must be narrowed. The lower bound can be increased by the following method:
-
Remove each bound in turn, together with it's arcs.
-
Find the residual minimum spanning tree and its length.
-
Add to the residual minimum spanning tree the two shortest distinct arcs and find the length of the resulting tree.
-
The greatest of these is used for the lower bound.
-
An optimal solution has been found if either the lower bound gives a tour or the lower bound is the same as the upper bound.
The upper bound can be reduced by finding short cuts from node to node once the minimum spanning tree has been drawn, but it can be difficult to find shortcuts in a large network. Other algorithms to find upper bounds exist. One such is the nearest neighbour algorithm:
Select each vertex in turn as a starting point.
Go to the nearest as yet unvisited vertex.
Repeat 2 until all the vertices have been visited and return to the start vertex using the shortest route.
Once all vertices have been used as the start vertex,select the tour with the smallest length as the upper bound.