Solution

Suppose a set of points with their coordinates is given. The problem facing the traveling salesman is one of finding a tour among the points in this set, such that every point is visited only once, the traveler returns to the initial point, and the length of the tour is minimized.

This can be modeled as a mathematical programming problem with a linear objective function (sum of all tour segments); decision variables associated with links between two points and taking values 0 or 1, depending of whether the link is a tour segment or not; and a large number of constraints (the so-called subtour elimination constraints) which enforce that all points are visited exactly once, and that the solution is a tour (no separate subtours).

This problem belongs to a class of difficult combinatorial problems. There are (N-1) ! possible tours to choose from and one has to look through that many tours to find the best one. In our example with 15 cities, there are 87,178,291,200 possible tours.

An algorithmic framework called "branch and bound" or "implicit enumeration" is used to eliminate large portions of the set of feasible tours from further consideration when it can be mathematically proven that those tours can not be optimal. A good algorithmic strategy should eliminate as many tours as possible.

One optimal tour is 7341 miles long: Olympia, Sacramento, Phoenix, Santa Fe, Austin, Jackson, Atlanta, Charlston, Richmond, Providence, Madison, Topeka, Salt Lake City, Helena, Boise, and back to Olympia.

Back to Puzzle