Travelling salesperson routes and bounds

What you’ll learn

• Distinguish visiting vertices from traversing edges.
• Apply nearest neighbour and spanning-tree bounds.
• Use matching bounds to prove optimality.

Understand the idea

A travelling salesperson tour visits every vertex once and returns to its start. In the metric version, the complete network also satisfies the triangle inequality. A practical road network may first be replaced by a complete network of shortest travel distances; a resulting leg can pass through intermediate road vertices.

Nearest neighbour starts at a vertex and repeatedly moves to the closest unvisited vertex, returning at the end. It produces a feasible tour and hence an upper bound, but may not be optimal and can depend on the starting vertex. Doubling a minimum spanning tree also gives a closed walk; shortcuts do not increase length when the triangle inequality holds.

For a lower bound, delete one vertex, find a minimum spanning tree on the remaining vertices and add the two cheapest edges incident to the deleted vertex. Every tour must include a connector on the remaining vertices and two incident tour edges. Repeating with different deleted vertices can improve the bound; take the largest valid lower bound.

Key formulae

$$L_{\mathrm{lower}}\leq L_{\mathrm{opt}}\leq L_{\mathrm{tour}}$$

$$L_{\mathrm{lower}}=w(T_{V\setminus\{v\}})+w(e_1)+w(e_2)$$

$$L_{\mathrm{opt}}\leq2w(T)\quad\text{for a metric network}$$

Worked example

A complete undirected network on A, B, C, D has distances AB = 3, BC = 4, CD = 3, DA = 4, AC = 5, BD = 5. Use nearest neighbour from A and a lower bound deleting A to determine the optimum tour length.

1. Nearest neighbour chooses A–B (3), B–C (4), C–D (3), then D–A (4), giving an upper bound 14.
2. Deleting A leaves B, C, D. A minimum spanning tree uses CD = 3 and BC = 4, total 7.
3. The two cheapest edges from A are AB = 3 and AD = 4, giving lower bound 7 + 3 + 4 = 14.
4. The lower and upper bounds match, so the feasible tour is optimal.

Answer: The optimum tour length is 14.