The Traveling Salesman Problem

Every town once, and home

A salesman leaves home, visits every town on his list once, and returns home. The towns are the vertices of a network, and the weights are the distances, times or costs between them. The traveling salesman problem asks for the cheapest such round trip.

Compare the Chinese postman problem, which must cover every edge. Here every vertex must be visited, and most of the edges are never used.

Four towns, with every pair joined by a road of the weight shown.

A tour is a Hamiltonian cycle

A round trip that visits every vertex exactly once and returns to the start is a Hamiltonian cycle. In the traveling salesman problem it is called a tour, and its cost is the total of its four edges.

A-B-C-D-A costs 5 + 6 + 4 + 7 = 22. A-B-D-C-A costs 5 + 8 + 4 + 9 = 26. A-C-B-D-A costs 9 + 6 + 8 + 7 = 30. The same towns, in a different order, cost different amounts, so the whole problem is choosing the order.

A tour is the same tour whichever town it starts from and whichever way round it runs: B-C-D-A-B and A-D-C-B-A are both A-B-C-D-A. So these three are all the tours on four towns, and the cheapest is 22.

The tour A-B-C-D-A, in gold, costs 5 + 6 + 4 + 7 = 22, the cheapest of the three.

The tour A-C-B-D-A uses both diagonals and costs 9 + 6 + 8 + 7 = 30, the most expensive of the three.

Why listing every tour fails

Count the tours when every pair of n towns is joined. Fix the starting town; the other n − 1 towns can follow in (n − 1)! orders. Each tour is then counted twice, once in each direction, so there are $\frac{\left(n-1\right)!}{2}$(n − 1)!/2 tours.

Four towns give $\frac{3!}{2}=3$3!/2 = 3 tours, and five towns give $\frac{4!}{2}=12$4!/2 = 12. Ten towns give $\frac{9!}{2}=362$9!/2 = 362,880 ÷ 2 = 181,440, and the count goes on growing faster than any power of n. No method is known that finds the cheapest tour quickly for every large network. So in practice the cheapest tour is trapped between bounds: a tour already found is an upper bound, and a cost that no tour can go below is a lower bound.

The classical and the practical problem

A real map usually has missing roads. In the network below there is no road from A to C.

The classical problem asks for a Hamiltonian cycle on the network exactly as given: every vertex exactly once. Without AC, A-B-C-D-A is the only one left, at 22, because each of the other two needs the road AC.

The practical problem lets the salesman pass through a town again on the way to another; each town must be visited at least once. To solve it, replace the network by a table of shortest distances between every pair. From A to C the shortest route is 11, through B (5 + 6) or equally through D (7 + 4). Every other pair already has a direct road that is shortest: B to D is 8, against 6 + 4 = 10 through C.

The classical problem is then solved on the complete table. Its tours cost 22, 5 + 8 + 4 + 11 = 28 and 11 + 6 + 8 + 7 = 32. A tour that uses the entry AC = 11 is driven as A-B-C or A-D-C on the roads.

There is no road from A to C. The gold route A-B-C, 5 + 6 = 11, is one of the two shortest ways between them.

The table of shortest distances. The entry for A and C is 11, the length of a route, not of a single road.

The usual mistakes

Leaving out the edge back to the start. A-B-C-D is 5 + 6 + 4 = 15, but the salesman has to come home, and the tour is 22.

Counting each tour twice. Four towns can be ordered after a fixed start in 3! = 6 ways, but each tour appears once in each direction, so there are 3.

Putting a road’s own weight in the table when a shorter route exists. The table holds the shortest distance, which can pass through other towns.

Covering every road instead of every town. That is the Chinese postman problem.

A vet on country roads

In the application below, a vet drives from her base to four farms on roads that do not join every pair. The table of shortest distances is completed first, and a tour found on it is then written back as a drive along the roads.