Chapter 6 Traveling Salesman Problems
Most phones and GPS units have the capability to allow you to input multiple locations and have the unit compute a path that visits all locations while minimizing your choice of time or distance. Does yours always find the best path? Ours don't. The unit most likely uses one of the algorithms in this chapter. The Traveling Salesman Problem (TSP) models a variety of different real world problems where we seek to minimize the time required to do something:
-
work orders,.
where vertices represent repair jobs and weights represent times required to re-tool for the next job;
-
jobs on a machine,.
where vertices represent tasks and weights represent times to reconfigure the machine for the next task;
-
circuit boards,.
where vertices represent holes to be drilled in the board and weights represent times to rotate the board into the new position.
Returning to your employment status... Having determined that the shortest mail route required nine-hour days, you've decided to look for a job as a traveling salesman. A health food supplier is looking for someone to make deliveries to five stores in the region. Figure 6.1 shows the five stores and the distances between them in miles. You will be paid for each trip that visits all five stores.
This looks good since you can travel at your own pace and won't have to worry about graph theory! Since you live near \(A\text{,}\) you decide on the loop,
which is
On second thought, you observe that you could travel the loop,
which is only
Your brain starts to hurt when you wonder, “What is the shortest route?” and “Just how many routes are there?” Back to graph theory and counting...
Problem 6.2.
List all the possible routes starting and ending at \(A\text{,}\) and hitting every other store exactly once. List the total distance traveled for each route. What is a \((\)the?\()\) shortest route? What is a \((\)the?\()\) longest route? Could there be a shorter route starting and ending somewhere else?
Let's rephrase this problem in the language of graph theory.
Definition 6.3.
A weighted graph is a graph in which each edge has been assigned a positive number called its weight.
Definition 6.4.
The weight of a circuit is the sum of the weights of its edges.
Definition 6.5.
A circuit which passes through every vertex exactly once is called a Hamilton circuit.
Definition 6.6.
A minimum weight Hamilton circuit is a Hamilton circuit that has the smallest possible weight of all Hamilton circuits.
In graph theory terms, the TSP is the problem of finding a minimum weight Hamilton circuit. Notice that there is an edge between every pair of stores in Figure 6.1. Such a graph is called complete.
Definition 6.7.
A complete graph is a graph in which every pair of distinct vertices is connected by an edge.
Problem 6.8.
How many Hamilton circuits are there in a complete graph on three vertices? On four vertices? On twelve vertices? On \(N\) vertices?
The TSP is more complex for non-complete graphs. As we have seen, a complete graph has many Hamilton circuits. In contrast, a non-complete graph may have no Hamilton circuit, and the problem of determining if a non-complete graph has a Hamilton circuit at all is a difficult one. Therefore we will consider complete graphs in this chapter except for the last problem of the chapter before the project section.
We will study three different algorithms for solving the TSP, each of which is not completely satisfactory for a different reason. The first method we study is the one you applied above.
Brute Force TSP Algorithm.
List all Hamilton circuits.
Compute the total weight of each circuit in the list.
Pick out a minimum weight circuit.
This algorithm finds all optimal solutions, since we check every possible solution. However, the time required to execute the algorithm grows rapidly as we add new vertices. Suppose we have a weighted graph with 12 vertices. To decide if this graph has an Euler path, and then to use Fleury's Algorithm to find that Euler Path, might take 10 minutes. The time required to solve the TSP with the Brute Force Algorithm for a similar sized graph is somewhat longer.
Problem 6.9.
Suppose you want to use the Brute Force Algorithm to solve the TSP for a graph with 12 vertices, that you can compute the weight of one Hamilton circuit in 10 minutes and that the fate of the world rests on your results. How long will it take you to check all of the different circuits?
This problem suggests that we consider other more practical algorithms. The next two algorithms are called greedy algorithms because at each step we do whatever is most advantageous to us at that moment, without planning ahead.
Nearest Neighbor Greedy Algorithm.
Choose any vertex as a starting point.
At each step, go to any one of the closest remaining vertices.
Once every vertex has been visited, return home.
Now, repeat this process starting at another vertex. Once you have created circuits using each vertex as a starting point, compare the weights of all the circuits and choose a circuit of minimum weight. }
Problem 6.10.
Apply the Nearest Neighbor Greedy Algorithm to the Health Food Store problem in Figure 6.1. You need to start by drawing 5 copies of the vertices of the graph, one for each starting place. Circle the starting vertex of each one, and then insert the edges that you use for your circuit numbering them as you add them. Write under each one the weight of the path you get. Finally, tell which path is the shortest. That is your solution to the TSP.
The Nearest Neighbor Greedy Algorithm is more time efficient than the Brute Force Algorithm. Our next algorithm, The Cheapest Link Greedy Algorithm, is even more time efficient.
Cheapest Link Greedy Algorithm.
Make a copy of the vertices of the original graph.
Repeat Step 3 until you have a Hamilton circuit.
-
Add a minimal weight edge from your original graph to your copy so that
if added to your copy, it will not create a degree three vertex, and,
if added to your copy, it will not close a circuit unless that circuit is a Hamilton circuit.
Problem 6.11.
Apply the Cheapest Link Greedy Algorithm to Figure 6.1. Draw the 5 vertices, then add the edges one at a time, numbering them as you go, until you have a circuit. What is the weight of this circuit?
Problem 6.13.
Use the Brute Force Algorithm to solve the TSP for Figure 6.12.
Problem 6.14.
Use the Nearest Neighbor Greedy Algorithm to solve the TSP for Figure 6.12.
Problem 6.15.
Use the Cheapest Link Greedy Algorithm to solve the TSP for Figure 6.12.
We have seen the NNGA give us minimal weight Hamilton circuits while the time efficiency of the CLGA can come at the cost of a slightly less than minimal weight circuit.
Problem 6.16.
In the previous two problems, the NNGA gives the minimal weight circuit found by the BFA and the CLGA gives the second to minimal weight circuit. Can you find an example in which the CLGA gives a minimal weight circuit but the NNGA does not?
Does the NNGA, like Fleury's Algorithm, always give us an optimal solution? The answer is “No”.
Problem 6.17.
Find an example of a weighted graph with four vertices in which neither of the Greedy Algorithms produce a correct answer to the TSP no matter which allowable choices are made. \((\)This proves mathematically that greed does not always pay!\()\)
Problem 6.19.
The weighed graph in Figure 6.18 is not complete.
Without using any of our algorithms, find a minimum weight Hamilton circuit.
Try to apply the greedy algorithms to this problem. What happens?
Since 1971, when it first gained public attention, considerable effort has gone into finding a good solution to the Traveling Salesman Problem, but no solution has been found that is quick, efficient, easy to apply (like Greedy algorithms) and guaranteed to work (like the Brute Force Algorithm). Considerable evidence suggests that no such solution exists at all.