Consider a traveling salesperson who must visit each of 20 cities before returning home. She knows the distance between each of the cities and wishes to minimize the total distance traveled while visiting all of the cities. In what order should she visit the cities?
Let there be n cities, numbered from 1 up to n. For each pair of
cities (i,j) let 
be the cost of going from city i to city
j or from city j to city i. Let's let 
be 1 if the
person travels between cities i and j (either from city i to
city j or from j to i). This problem is known as the
symmetric TSP. In the asymetric TSP, the cost to
travel in one direction may differ from the cost to travel in the
other, and the decision variables must distinguish between the two
directions. Clearly the asymetric problem is the more general.
The objective is to minimize 
. The constraints are harder to find. Consider the
following set:
These constraints say that every city must be visited. These constraints are not enough, however, since it is possible to have multiple cycles (subtours), rather than one big cycle (tour) through all the points. To handle this condition, we can use the following set of subtour elimination constraints:
This set states that, for any subset of cities S, the tour must
enter and exit that set. These, together with 
is
sufficient to formulate the traveling salesperson problem (TSP) as an
integer program.
Note however, that there are a tremendous number of constraints: for
our 20-city problem, that number is roughly 524,288. For a 300-city
problem, this would amount to
101851798816724304313422284420468908052573419683296
8125318070224677190649881668353091698688 constraints. Try putting
that into LINGO!
Despite the apparent complexity of this formulation, it lies at the heart of the most promising current approach to solving medium (100-1000 city) TSPs. We will see this again in the cutting plane section. Other forms of subtour elimination constraints are possible, but they suffer from the same explosive rate of growth in number. Subtour elimination constraints for the asymetric problem are equally difficult.
The traveling salesman problem has come up twice in my recent consulting. The first had to do with operating cellular telephone manufacturing robots. An American producer of cellular telephones had reached its production capacity with a lot of unsatisfied demand. The bottleneck in the production process were a set of automatic placement machines that placed components onto printed circuit boards. The manufacturer of the machines had a method for sequencing the placements in order to decrease production time. Was their method optimal? Could it be improved? Currently, the producer had 30 machines. Each new machine cost approximately $1 million. The problem of optimally operating the machines is a traveling salesman problem. It takes a certain time to move from one placement to the next. Minimizing the time requires finding the optimal route that visits all the placements.
The second example occured just last week (October 1995). I was approached by Bayer to look at one of their production facilities. In this chemical plant, there were a number of products that had to be produced on a number of machines. There are a number of delays when production changed from one product to the next. In particular, there are cleanup times to get the machine clean enough for the next product. Depending on the products involved, this change may be as little as a spray with a hose to as long as a three man crew with toothbrushes. Determining the optimal ordering is a traveling salesman problem.
