10.6.1 The Travelling Salesman Problem

The Travelling Salesman Problem (TSP) involves finding the shortest possible route that visits every vertex in a graph exactly once and returns to the starting vertex. It is a fundamental optimisation problem with many practical applications, such as logistics, manufacturing, and delivery systems.

Types of Travelling Salesman Problems

Classical TSP

The graph is complete, meaning there is a direct route between every pair of vertices.
The objective is to find a Hamiltonian cycle with the minimum total weight (distance or cost).
The weights satisfy the triangle inequality, which states:

\text{Weight of } (A \to C) \leq \text{Weight of } (A \to B) + \text{Weight of } (B \to C)

This ensures that direct routes are never longer than indirect routes.

Practical TSP

The graph may not be complete, and some vertices may not have direct connections.
Missing edges are assigned a weight of infinity ( $\infty$ )

Algorithms for Solving TSP

Nearest Neighbour Algorithm

This heuristic provides a quick, though not always optimal, solution to the TSP. It generates an upper bound for the minimum route.

Steps:

Start at the initial vertex.
Move to the nearest unvisited vertex.
Repeat step 2 until all vertices are visited.
Return to the starting vertex.

Advantages:

Simple and fast.
Useful for generating an initial solution to improve upon.

Disadvantages:

May not give the optimal solution.
Heavily influenced by the starting vertex.

Improving the Solution

To refine the upper bound, shortcuts can be used:

Revisit the route generated by the nearest neighbour algorithm.
Replace segments of the route with shorter connections while ensuring a valid Hamiltonian cycle.

Worked Example

infoNote

Question Solve the TSP for the complete graph below using the nearest neighbour algorithm:

	A	B	C	D
A	∞	10	15	20
B	10	∞	35	25
C	15	35	∞	30
D	20	25	30	∞

Step 1: Nearest Neighbour Algorithm

Start at $A$
Nearest vertex to $A:B$ ( $A \to B =10$ )
Nearest unvisited vertex to $B:D$ ( $B \to D = 25$ )
Nearest unvisited vertex to $D:C$ ( $D \to C = 30$ )
Return to $A$ ( $C \to A = 15$ ) Route: $A \to B \to D \to C \to A$

Total Weight:

10 + 25 + 30 + 15 = :highlight[80]

Step 2: Improving the Upper Bound

Check for shortcuts that reduce the total weight. In this example, no better shortcut exists, so the upper bound remains 80.

Note Summary

infoNote

Common Mistakes

Incorrect Implementation of Nearest Neighbour Forgetting to revisit the starting vertex or failing to consider all unvisited vertices.
Misinterpreting the Triangle Inequality Applying shortcuts that violate the triangle inequality can result in invalid routes.
Missing Edge Cases Not accounting for infinite weights in practical TSP, which may lead to invalid or incomplete routes.
Overlooking Improvement Steps Failing to refine the upper bound after the initial solution.
Dependence on Starting Point Not attempting the nearest neighbour algorithm from different starting vertices to explore better solutions.

infoNote

Key Formulas/Theorems

Triangle Inequality:

\text{Weight of } (A \to C) \leq \text{Weight of } (A \to B) + \text{Weight of } (B \to C)

Nearest Neighbour Selection:

\text{Next Vertex} = \arg\min(\text{Weight from Current Vertex to Unvisited Vertices})

Total Route Weight:

\text{Total Weight} = \text{Sum of Weights in Hamiltonian Cycle}

The Travelling Salesman Problem Simplified Revision Notes for A-Level Edexcel Further Maths Decision Maths 1

10.6.1 The Travelling Salesman Problem

Types of Travelling Salesman Problems

Classical TSP

Practical TSP

Algorithms for Solving TSP

Nearest Neighbour Algorithm

Steps:

Advantages:

Disadvantages:

Improving the Solution

Worked Example

Note Summary

Common Mistakes

Key Formulas/Theorems

500K+ Students Use These Powerful Tools to Master The Travelling Salesman Problem For their A-Level Exams.

Other Revision Notes related to The Travelling Salesman Problem you should explore