The travelling salesman problemEdexcel International A Level Maths: Revision notes

The travelling salesman problem (TSP) asks for a route of minimum length which visits every vertex in an undirected network. A walk that visits every vertex and returns to its starting vertex is called a tour. Examples are a delivery driver visiting customers, a sales representative visiting towns, or a drilling machine moving between holes. No quick method is known that always gives the best tour for a large network, so for exam networks we either list all the tours or find bounds on the best one (see the next topic).

In the classical TSP each vertex is visited exactly once (apart from the start, which is also the finish). A tour that does this is a cycle through all the vertices. The classical problem is normally set on a complete graph, one in which every pair of vertices is joined by an arc. If the network has $n$ vertices there are $\frac{(n-1)!}{2}$ different tours, counting a tour and its reverse as the same. For $n=4$ there are $3$, and for $n=5$ there are $12$, which is why only small networks can be solved by listing. If a vertex has only one arc, such as a vertex at the end of a dead-end road, no classical tour exists, since the tour would have to enter and leave by the same arc.

In the practical TSP a vertex may be revisited. This is needed when the network is not complete, for example when a vertex can only be reached through another vertex. A van delivering to shops along a one-road spur must go in and come out again. If the network is a tree, every arc must be travelled twice, so the shortest tour has length twice the total weight of the arcs. In general you list sensible tours, add up each total, and compare. If a vertex is joined only to $B$ by an arc of weight $w$, that arc adds $2w$ to the tour.

A complete network satisfies the triangle inequality if, for every triangle $ABC$ in it, the longest side is no longer than the sum of the other two: $AB\leq AC+CB,\quad\text{where }AB\text{ is a longest length}.$ This says that going directly between two vertices is never longer than going through a third vertex. Distances measured in straight lines satisfy it. If a network does not satisfy it, some direct arc is longer than a route through another vertex, so the practical and classical problems can have different answers. To show the inequality fails, find one triangle where the longest side is greater than the sum of the other two, such as $30>15+10$.

For a complete network with four vertices $W$, $X$, $Y$, $Z$ there are three tours starting at $W$:

• $W$-$X$-$Y$-$Z$-$W$
• $W$-$X$-$Z$-$Y$-$W$
• $W$-$Y$-$X$-$Z$-$W$ With $WX=20$, $WY=35$, $WZ=25$, $XY=15$, $XZ=30$, $YZ=10$ the lengths are $70$, $95$ and $105$. The shortest tour has length $70$. For five vertices list the $12$ tours systematically by fixing the start and listing orders of the other four vertices, then dropping reversals. Always show every tour you considered.

State whether the problem is classical (each vertex exactly once) or practical (vertices may be revisited). Give the route as a list of vertices, starting and ending at the same vertex, and show the length as a sum. To explain why no classical tour exists, name a vertex that is joined to only one other vertex. When a new arc is added, find any tour that uses it, write its length with the unknown, and compare with the previous best tour to form an inequality.