Bounds for the travelling salesman problemEdexcel International A Level Maths: Revision notes

For a large network there is no quick method that always finds the shortest tour for the travelling salesman problem. Instead we find an upper bound, the length of a tour that exists, so the shortest tour is no longer than it, and a lower bound, a value the shortest tour is no shorter than. The shortest tour then lies between them: $\text{lower bound}\leq\text{shortest tour}\leq\text{upper bound}.$ The smaller the gap, the better we know the answer. If the two bounds are equal, the tour found is optimal.

The bound methods need a complete network, where every pair of vertices is joined by an arc. If some pairs are not joined by a road, create an arc between them whose length is the shortest distance along the original network. Example: roads $AB=7$, $BC=5$, $CD=6$, $DE=4$, $BE=9$. Then $AC=12$ (via $B$), $AD=18$, $AE=16$ (via $B$), $BD=11$ (via $C$) and $CE=10$ (via $D$). The new arcs satisfy the triangle inequality, because each is a shortest distance. After finding a tour in the complete network, replace each new arc by the shortest path it stands for. The resulting route in the original network may revisit vertices, which is allowed in the practical problem.

The nearest neighbour algorithm builds a tour step by step.

1. Choose a starting vertex.
2. Move along the shortest arc to a vertex not yet visited.
3. Repeat until all vertices are visited, then return to the start. Example on a complete network with $PQ=14$, $PR=10$, $PS=17$, $PT=9$, $QR=11$, $QS=8$, $QT=15$, $RS=12$, $RT=13$, $ST=16$: from $P$ go to $T$ ($9$), then $R$ ($13$), then $Q$ ($11$), then $S$ ($8$), then back to $P$ ($17$). The tour has length $58$, so $58$ is an upper bound. Different starting vertices can give different tours. Start from each vertex in turn and take the smallest tour length as the best upper bound.

A walk that goes all the way round a minimum spanning tree, out along each arc and back, visits every vertex and returns to the start. It uses each arc twice, so its length is $2\times$ the weight of the tree. This gives an upper bound. Use shortcuts to improve it: whenever the walk would revisit a vertex, go straight to the next new vertex instead. In a complete network satisfying the triangle inequality a shortcut is never longer than the route it replaces. Example: a network has a minimum spanning tree that is the path $B$-$C$-$A$-$E$-$D$ with arcs $8$, $9$, $7$, $6$ (weight $30$), and $BD=11$. The walk gives $60$. Shortcutting from $D$ straight back to $B$ ($11$) gives the tour $B$-$C$-$A$-$E$-$D$-$B$ of length $8+9+7+6+11=41$. Shortcuts can also be used on a nearest neighbour tour: if replacing two arcs by one shorter arc still gives a tour, use it.

To find a lower bound:

1. Delete one vertex $X$, with all its arcs.
2. Find a minimum spanning tree of the remaining vertices.
3. Add the lengths of the two shortest arcs at $X$. This is a lower bound because every tour contains two arcs at $X$, each at least as long as the two shortest, and removing $X$ from a tour leaves a path joining the other vertices, which is at least as long as their minimum spanning tree. Example (the same network, with $BC=8$ and $BD=11$ the two shortest arcs at $B$): delete $B$, and the minimum spanning tree on $A$, $C$, $D$, $E$ has arcs $6$, $7$, $9$ and weight $22$, so the lower bound is $22+8+11=41$. Deleting a different vertex can give a different lower bound. Repeat for several vertices and take the largest, since it is the best lower bound.

Give the best bounds you have found, and state them as an inequality such as $41\leq\text{shortest tour}\leq41$. If the lower bound equals the upper bound, the tour is optimal. Otherwise the shortest tour lies in between. You can say how close the upper bound is, for example within $5$ of the lower bound. In the practical problem, convert the tour back to the original network by replacing each arc of the complete network with its shortest path. State the final route as a list of vertices, and check its length equals the upper bound.