Revisiting a Traveling Salesman

The Traveling Salesman Problem, affectionately known as TSP, lies at the heart of many problems, including optimizing the deliveries of trucks, scheduling tour stops, and laying out wires. TSP yields very nicely to heuristics, but it also admits some beautiful theory.

A certain salesman, we’ll call him Bob, starts at a certain city C and wants to visit a certain set of other cities by car at least once and then return to C. (Factoid: What is the preferred profile of salespeople from pharmaceutical companies who call on doctors? Answer: Former cheerleaders.) Travel times and costs may vary, but we will assume that the costs are positive, symmetric, and that the triangle inequality holds. Symmetry means that going from X to Y costs the same as going from Y to X. The triangle inequality means that going from X to Y to Z cannot be cheaper than going directly from X to Z (it could be the same price, but not cheaper).

The question is whether Bob can visit all his cities for a certain price or less. As you can see, if someone proposes a solution, you can verify that it meets the price budget easily, but finding a solution below a certain price can be hard - it may require exploring all possible paths.

Many people hear this problem and think: “Why can’t a greedy approach work? That is, from each city, I’ll just go to the next nearest one.”

How bad can this get? That is, can you find a set of points where the greedy approach fails to find the minimum length route for the traveling salesman (assuming for the moment that cost is proportional to length)? Figure 2-13 lays out the visual for the problem.

Figure 2-13: The salesman starts at C and ends at C. Each time he goes to the closest unvisited city. How well will Bob do?

Using the greedy heuristic, if you start at point C, you will go down, right, up, right, down, right, up, right, down and then all the way back to C, as illustrated in Figure 2-14. In fact however, the best route would be to go directly right from C until the upper right hand point, then down, left and back to C, as in Figure 2-15.

Figure 2-14: What happens when Bob visits the nearest previously unvisited city first?

Figure 2-15: A better route for Bob.

When greed doesn’t work, heuristics might help, but first there is the question of how bad greed could be. Concretely, can you find a situation, again assuming that cost is proportional to length, when the greedy “go to the next nearest city” strategy could be more than twice as costly as optimal?

I’m not going to answer this right away, because I want to present you with a strategy that is surely no more than twice as costly as optimal, is also greedy, and can easily be improved by heuristics. It also applies to every set of cities.

As you may already know, a spanning tree is a graph without cycles that connects all vertices (cities in our case). The cost of a spanning tree is the sum of the costs of its edges (remember that we assume that the cost to go from A to B is the same as the cost to go from B to A - symmetry). A minimum cost spanning tree is a spanning tree having the property that no other spanning tree has lower cost. To construct a minimum spanning tree starting at city C, we use the following algorithm:

 Call an edge "useful" if it connects a vertex in a tree to a vertex outside the tree.  initialize the tree T to contain the city C and no edges  until there are no more cities to include     Add edge E to the edges of T if E is useful         and for every other useful edge E'         the cost of E' is greater than or equal to the cost of E     Add the node of E not already in T to the nodes of T  end until

Given the nodes in Figure 2-16, Figure 2-17 shows a minimum spanning tree (again where cost is proportional to distance).

Figure 2-16: A set of cities. Assume that cost is proportional to distance. The goal is to construct a minimum spanning tree.

Figure 2-17: The minimum spanning tree in this case. Note that we do not need to know which is the starting city.

Now, here comes the key insight. The lowest cost route that a traveling salesman uses to visit all the cities is a spanning tree (though not necessarily a minimum cost one) if one ignores the final edge that brings the salesman back to his own city. The reason is that the route will touch all cities exactly once, because the triangle inequality makes it unprofitable to revisit a city. Because the route is a spanning tree (plus an extra edge), it must be at least as costly as the minimum spanning tree.

The consequence of this observation is that the cost of the minimum spanning tree provides a lower bound on the possible cost of the optimum traveling salesman route, even if we never find that optimal route.

We are not done, however. Every route is a spanning tree, but most minimum spanning trees are not routes. Fortunately, we can create a route from any minimum spanning tree that will never cost more than twice as much as the optimal route, as illustrated in Figure 2-18.

Figure 2-18: Take the minimum spanning tree and then go up and down each edge of the tree. That gives a route no matter which city one starts from. It’s true that this route revisits cities, so can be improved. Already, though, its cost is no more than twice that of the optimal one.

Suppose we start at the center point and go right, then up, then down, down, then up, then left back to the center. We continue similarly on the left. The point is that every edge will be traversed twice. By symmetry, this means that the route costs twice as much as the minimum spanning tree. Because the minimum spanning tree is less expensive than the (unknown) optimal route, this route is less expensive than twice the cost of the optimal route.

Many improvements are now possible. Some are illustrated in Figure 2-19 where the returns to the center are done via diagonal lines. Beyond such heuristics, there are some guarantees. A very clever algorithm by N. Christofides showed that one could combine minimal matchings with spanning trees to obtain a route that is no more than 3/2 as expensive as the optimal one.

Figure 2-19: Some simple heuristic improvements to the minimum spanning tree-based route that will either leave the cost the same or reduce it (assuming the triangle inequality holds).

As clever as these approaches are, however, they don’t necessarily extend to other problems, because they depend strongly on symmetry and the triangle inequality. Or do they?

1. Can you find a case where, if symmetry and the triangle inequality do not hold, even the factor of two guarantee may not either? If not, can you prove that the spanning tree will always guarantee a cost that is no more than twice the optimal?

Solution to Revisiting a Traveling Salesman

1. Can you find a case where, if symmetry and the triangle inequality do not hold, even the factor of two guarantee may not either? If not, can you prove that the spanning tree will always guarantee a cost that is no more than twice the optimal?

When symmetry and the triangle inequality fail to hold, the spanning tree heuristic can be quite bad (see Figure 2-20).

Figure 2-20: All unmarked edges have a cost of 5. The marked edge Z to C has a cost of 60 (violating symmetry and the triangle inequality). The marked edge Z to Y has a cost of 6, as does the edge from Y to Z.

Suppose that all edges have a cost of 5 except the three indicated. Then a spanning tree rooted at C will include the edges in Figure 2-21, because that is the least expensive tree starting from C in its construction phase. This gives a total cost of 85. By contrast, Figure 2-22 shows a tour that costs only 21.

Figure 2-21: The spanning tree starting at C contains the directed edges C to Z, C to X, and C to Y. Back edges play no role. Unfortunately, the travel route using that tree must traverse the back edge having cost 60. Altogether we get a cost of 85.

Figure 2-22: A much cheaper route moves clockwise through the nodes and has a cost of only 21.