Traveling Salesman Problem Tidbit (2/03/04)

Prepared by:

Joseph Malkevitch

Mathematics and Computing Department

York College (CUNY)

Jamaica, NY 11451

Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)

When you make a phone call from a public phone booth, what happens to the coins that you use to pay for the call? The answer is that periodically someone has to come to collect these coins and empty the coin box so that it does not fill up. When the coin box is full other people can not make calls and the company that owns the phone booth loses income. It would be very expensive to send out one person to collect the coins from one phone booth and then have this person return to his/her home base. What is done is that a group of phone booths that need their coins collected are grouped as needing servicing, and a person is sent to collect the coins. This requires that the person start at home base, plan a sequence of visits to the phone booths where after collecting the coins from one both the employee goes on to the next booth. After the coins are collected at all the booths in the group the employee heads back to home base. We can construct a mathematical model of this situation by assuming that we have available a table which shows the distance between every pair of phone booths (which is symmetric in the sense that the distance from site i to site j is the same as the distance between site j and site i.) We need to design a tour starting at home, visiting each site once and only once and which returns to home but traverses the minimum total distance.

A problem of this sort is known as the TSP, which stands for Traveling Salesman Problem. The problem gets is name from the classical problem of a salesman, who like the coin collector, must start from and return to a home location, visit each of a collection of cities once and only once, and complete the tour with a minimum cost. (Even here one can imagine a variety of complexities if one is not required to use one mode of transportation and one is free to use, say, car, rail and air.)

Abstractly we can think of the TSP as a complete graph with n vertices where each edge e of the graph is assigned a weight (where we assume the weights assigned to the edges obey the triangle inequality) which is thought of as the cost of moving between the vertices at the endpoints of e. What is being sought is a minimum cost Hamiltonian Circuit for the graph. How many Hamiltonian Circuits must be examined to find the one with minimum cost? The answer is that since starting a particular vertex we can visit any one of n-1 other vertices, and from there, any of n-2 other vertices, etc., the number of circuits is (n-1)! However, since any circuit could also be visited in the reverse cyclic order, we would have to examine (n-1)!/2 different circuits, a task of immense proportions for even modest choices of n. Remarkably, no satisfactory complexity result is known for a general TSP problem. In fact, the TSP was one of the earliest problems shown to be NP-complete. A problem is NP-complete if finding a polynomial time algorithm for any such problem would imply that all of the other NP-Complete problems had a polynomial time algorithm, while a proof that any algorithm to solve the problem required exponential time would show that this was true of all of the NP-Complete problems. It is widely thought that it is unlikely that these problems do indeed have polynomial time algorithms.

A variety of very important problems in operations research either are the TSP or are generalizations of the TSP.

a. Picking up school children to take them to school.

b. Picking up campers to go to day camp.

c. Delivery of meals on wheels to the elderly.

d. Group taxi service from an airport to peoples homes.

e. Placing of components in industrial processes

f. Planning a shopping spree.

g. Delivery of commodies to branches of a supermarket chain.

One issue that scholars have looked at is under what conditions on the weights on the edges some polynomial time algorithm for this problem can be found.

Variants:

1. The Euclidean TSP

The weights assigned to the edges arise from a set of points in Euclidean space. One special case of particular interest is when the weights arise from points in the Euclidean plane. It is known that in this case the mimimal cost tour can not cross itself and that its vertices follow the same order as the those of the convex hull of the points. The first of these observations follows from the fact that the triangle inequality holds for the distances between points in the Euclidean plane.

2. Assymetric TSP

The distance or cost from a to b is not the same as the cost of going from b to a.

3. Costs violate the triangle inequality

Usually distances obey the triangle inequality but for some TSP problems it is not natural to assume that the triangle inequality holds.

In light of the fact that the TSP is an NP-complete problem and its dramatic importance in a wide variety of applicable situations it is natural that a wide variety of heuristics have evolved for the attempting to find reasonably good TSP tours in a reasonable amount of time.

Here are some examples of these heuristics:

1. Nearest Neighbor

Pick any vertex

Move next to that neighboring vertex not already visited which has the smallest weight. Return home only when all other choices are exhausted.

2. Sorted edges

Sort the weights of the edges in increasing order. Add next that not already added to a tour which has smallest weight and which when combined with previously chosen edges forms a subcycle or creates a vertex of degree more than 2.

Since it is unlikely that anyone will ever find a polynomial time algorithm to solve the TSP people have looked into the question of poorly a particular heuristic algorithm can perform on an "average problem" and on a "worst case" problem. For nearest neighbor, it is possible to produce examples where the nearest neighbor tour is twice as the best tour possible. However, as poor as this sounds, the provably best heuristic for the TSP is only guaranteed to give a tour which is no worse than 1.5 times the length of the optimal tour. The approach of this heuristic is to find a minimum cost spanning tree for the points and use "shortcuts" in traversing this tree to construct a relatively cheap TSP-tour.

References:

Lawler, E., and J. Lenstra, A. Rinnooy Kan, D. Shmoys, The Traveling Salesman Problem, John Wiley and Sons, New York, 1985.

Malkevitch, J., et al., For All Practical Purposes, 6th edition (and all earlier editions), W. H. Freeman, New York, 2002.

Back to list of tidbits