Sales and Chips
Posted September 2005.
If a particular country which manufactured computer chips could find better solutions to large TSP problems, it could manufacture those chips more cheaply...
What do the problems of designing an efficient drop-off route for individuals who have decided on a group cab ride home from an airport and the manufacture of a computer chip have in common? The answer is that both problems can be formulated in terms of the mathematical problem known as the Traveling Salesman Problem (TSP). (Nowadays, of course, the traveling salesman might well be a traveling saleswoman, but I will use the problem's traditional name.) The phrase "traveling salesman" rightly conjures up the image of a salesman, starting out from his home (or place of business), making his appointed rounds to show off the goods he is selling, and then returning to his starting point. The goal of the salesman and his employer might be different. The salesman, who must travel by car, might want to route himself via his favorite cousin's hometown and perhaps take in an antiques show on the way, while the employer might want to have the salesman follow the cheapest route possible.
History and Basic Ideas
As with many historical questions, it is complex to pin down exactly where the TSP as a mathematical problem came from. There is a reference to it as a practical problem in a German book from 1832. Some people credit Karl Menger with popularizing the problem to the European mathematical community in the 1920's. Merrill Flood, who studied at Princeton, also popularized the problem and brought it to the attention of the mathematics and operations research community (in the US). He indicated that he heard of the problem from A. W. Tucker in 1937.
Flood claimed that Tucker had been told about the problem by Hassler Whitney, but when Tucker was asked about this he was unable to confirm or deny it - he no longer remembered!
(Courtesy of Alan Tucker, A. W. Tucker's son)
In any case Flood (whose name is also associated with the theory of games) encouraged the study of the problem by the Rand Corporation. From its earliest days Rand was actively involved in work in operations research and, as we shall see below, there are many operations research problems that take the form of the TSP.
Figure 1 (A 4-city TSP problem)
What we have above is a diagram consisting of dots and lines known as a graph. This is a special kind of graph known as a complete graph because each vertex is joined to every other one. Furthermore, we have assigned to each edge of the complete graph a weight, which could be a time, road distance, cost of a train or airplane ticket, etc. for the trip between the two locations at the endpoints of the edge. Usually these weights are taken as nonnegative numbers (but it is interesting to consider what interpretation might be put on using negative weights) which obey the triangle inequality. This means that given three locations X, Y, and Z the sum of the weights for any pair of the three edges the locations determine is at least as large as the weight on the third edge. (For a distance function, satisfying the triangle inequality is part of the usual definition, as is the requirement that the distance from A to B be the same as the distance from B to A.) In our example, we are assuming that we have a symmetric TSP - the cost in going from X to Y is the same as the cost in going from Y to X - but many interesting applications give rise to an asymmetric TSP in which the cost of going from X to Y may not be the same as the cost in going from Y to X.
The goal in solving a TSP is to find the minimum cost tour, the optimal tour. A tour of the vertices of a graph which visits each vertex (repeating no edge) once and only once is known as a Hamiltonian circuit. Thus, one can think of solving a TSP as finding a minimum cost Hamiltonian circuit in a complete graph with weights on the edges.
The Euclidean TSP
An interesting special case of the TSP is to consider the optimal route passing through a collection of n points (sites) in the Euclidean plane (or more generally, n-dimensional Euclidean space). The weights between the points (sites) involved are taken to be the Euclidean distance between the points. If in an optimal tour some pair of edges AC and BD cross as shown below (Figure 4, top), then this can not be an optimal tour. Why? Consider the tour where the edges A'B' and D'C' replace the edges AC and BD in our tour. Let us compare the cost of the tour ACBDA with the tour A'B'C'D'A' (Figure 4, bottom). Note that the edges AC and BD meet at a point Q which is not one of the original sites involved in the TSP. We know that AQ + QB is larger than A'B' (because in the triangle AQB, the sum of any two sides has Euclidean length greater than the third side). Similarly DQ + QC is longer than D'C'. Thus, AQ + QB + DQ + QC is longer than A'B' + D'C'. However AQ + QC = AC and DQ + QB = DB and hence, if we replace AC and DB by A'B' and D'C', we get a shorter tour.
Insights from Computer Science
In attempting to get insights into how hard it is to solve TSP problems, it turns out to be convenient to distinguish between two ways of thinking about the TSP situation. In one perspective, what one has is a decision problem. Given a weighted complete graph with n vertices, locate a tour which visits each vertex once and only once whose total weight is less than a fixed constant k. However, there is also the optimization version of the problem, the one we have emphasized here, where the goal is finding the tour of the vertices once and only once with total weight the smallest possible.
Figure 6 (Matrix representation of Figure 5)
Figure 7 (List representation of Figure 5)
The list representation of a graph with many vertices and few edges will have fewer symbols than the matrix representation for the same graph. Some problems might lend themselves to easier algorithms when the data is given in one data structure rather than another.
It is widely believed that no polynomial time algorithm for the TSP will be found. The optimization version of the TSP is known to be NP-hard. This means that the problem is known to be in NP, and if some polynomial time solution to this problem existed, then some (hence, every) NP-complete problem would be solvable in polynomial time. To be in NP means that all problems in NP reduce to this problem in polynomial time. To be in NP means that one can verify (not necessarily find) that a solution given to one is correct in polynomial time. If someone gives a good "guess" for a solution we can very quickly verify that it works.
A relatively recent breakthrough shows that a polynomial time approximation scheme exists for a special type of TSP, namely when the weights (costs) in the problem are Euclidean distances, whereas for general values no such approximation scheme exists.
Variations on a Theme
Mathematicians are trained to take an important problem and find related problems that are also of interest. The variations that mathematicians find for a problem are carried out on many fronts. This reflects the fact that the methods that have proved useful in solving a particular problem are often useful in carrying out related or "nearby" problems. One way to extend what one knows is in the applied arena: Take the problem of interest and change to an application related to the original one. For example, one might have originally wanted to solve a problem for a salesman but realize that the problem of picking up children and taking them to a day camp is a related problem but one with the constraint that one can not exceed the size of the minibus. As another example, we have considered applications where a tour is found which starts and ends at the same site and visits each vertex once and only once. What about the problem of starting at a site, visiting each vertex once and only once, but ending at a different site?
These are only some of the many examples of how mathematics is being used to find increasingly efficient solutions to harder and more subtle operations research problems, thereby improving all of our lives.
Applegate, D. and R. Bixby, V. Chvatal, W. Cook, TSP cuts which do not conform to the template paradigm, In Computational Combinatorial Optimization, Optimal or Provably Near-Optimal Solutions, LNCS, Volume 2241, Springer-Verlag, 2001, p. 261-304.
Arkin, E. and M. Bender, J. Mitchell, S. Skiena, The lazy bureaucrat scheduling problem, Proceedings of the 6th International Workshop on Algorithms and Data Structures, 1999, p. 122.-133.
Arora, S., Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of ACM, 45 (1998) 753-782.
Chiang, Y-J, New approximation results for the maximum scatter TSP, Algorithmica, 41 (2005) 309-341.
Christofides, N., Worst-case analysis of a new heuristic for the traveling salesman problem, Report 388, Graduate School of Industrial Administration, Carnegie Mellon U, 1976.
Kruskal, J., On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem, Proc. Amer. Math. Soc. 7 (1956) 48-50.
Lawler, E., A solvable case of the traveling salesman problem, Math. Programming 1 (1971) 267-267.
Lin, S. "Computer Solutions of the Traveling Salesman Problem." Bell System Tech. J. 44 (1965) 2245-2269.
NOTE: Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal, which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance