The Traveling Salesman Problem (TSP) is a well known hard combinatorial problem. A TSP site provides historical perspective. A magazine contest in 1964 challenged its readers to find the optimum route for a traveling salesman who was to visit 33 specific cities in the United States. This was a challenge for the readers, but it was also a challenge to the computers of that time. Actually a problem of 49 cities was solved earlier in by G. Dantzig, R. Fulkerson, and S. Johnson in 1954. In 2004 the optimum TSP tour for visiting all 24,978 cities in Sweden was computed. The problem was solved on a cluster of 96 dual processor Intel Xeon 2.8 GHz workstations. The cumulative CPU time used was equivalent to approximately 84.8 CPU years on a single Intel Xeon 2.8 GHz processor.

The increase in problem size by a factor of almost 500 in 50 years is indicative in both the advances in algorithms and computers. Despite this significant advance the TSP remains a hard problem. No matter how fast computers become, there will always be problems that will be impossible to solve.

The general TSP combinatorial model considered here involves n cities and only allows solutions that form a tour.

Although the general model allows any objective function or constraint set, the objective function for the usual TSP is the sum of the arc lengths in the tour. In the following we assume all tours are feasible, however the set G could easily be adapted to restrict the set.

Excel Model

The general TSP-COP is implemented in the Optimize add-in. The special case of the model when the distance between cities has a Euclidean measure is provided by the Combinatorics add-in. The figure below shows the model form for the TSP-COP. Exhaustive enumeration was used to obtain the optimum solution for this six city (node) case. Highlighted cells are links in the optimum tour. The solution vector is in range D9:J9. The associated tour is in D10:J10. Node 7 represents a copy of node 1.

In terms of the model notation the solution is:

The figure constructed by the add-in shows the optimum tour.

This is not the optimum solution, but a solution obtained with a 2-change procedure starting from a greedy solution.

One might say that this Excel approach has reached a level of competence obtained 50 years ago by Dantzig and his famous co-authors. The commenter should remember, however, that this solution was obtained with a computer that is similar to those on millions of desktops, with a spreadsheet program used daily by a great number of many all over the world, with an add-in that is freely distributed on the web. This solution was found in 21 seconds and certainly running the program longer will improve it. Moreover, the source code is open to all to modify for specific applications and add new heuristics. Our purpose was to make the solution of this and other combinatorial problems easily accessible to a wide audience, and these add-ins are a good start.

The problem of finding the optimum sequence of jobs through a flow shop has a solution that may be represented by a tour. The Combinatorics add-in has a model that incorporates lateness penalties, setup times and time windows. The objective value depends on a complex series of Excel calculations, some involving logical IF expressions. It would be very difficult to write this function in a closed form algebraic expression. The solution is found using the same heuristics as used for the traditional TSP.

The routing problem addressed by the Combinatorics add-in is also similar to the TSP, but here we are dealing with a vehicle that starts at a depot, visit several sites and returns to the depot. The objective is to minimize the travel cost plus a cost that depends on the times of deliveries to the cities.