Edexcel IAL - Decision Mathematics 1- 3.2 Travelling Salesman Problem- Study notes - New syllabus
Edexcel IAL – Decision Mathematics 1- 3.2 Travelling Salesman Problem -Study notes- New syllabus
Edexcel IAL – Decision Mathematics 1- 3.2 Travelling Salesman Problem -Study notes -Edexcel A level Maths- per latest Syllabus.
Key Concepts:
- 3.2 Travelling Salesman Problem
Travelling Salesman Problem (TSP)
The Travelling Salesman Problem (TSP) involves finding the shortest possible route that:
- visits every vertex exactly once
- returns to the starting vertex
The vertices usually represent cities and the edge weights represent distances or costs.
Two Versions of the Problem
There are two forms of the Travelling Salesman Problem in the syllabus:
- the practical Travelling Salesman problem
- the classical Travelling Salesman problem
Practical Travelling Salesman Problem
In the practical TSP, the network:
- may be incomplete
- may not satisfy the triangle inequality
Exact solutions are usually found by:
- trial and improvement
- nearest neighbour methods
The aim is to obtain a good (short) route, not necessarily the optimal one.
Classical Travelling Salesman Problem
In the classical TSP:
- the graph is complete
- the graph satisfies the triangle inequality
The triangle inequality means that for any three vertices A, B and C:
\( \mathrm{AB \leq AC + CB} \)
This condition allows certain shortcuts to be taken without increasing the route length.
Upper and Lower Bounds
When solving the classical TSP, the goal is to find:
- a lower bound for the shortest possible tour
- an upper bound for the shortest possible tour
The true shortest route lies between these two values.
Improving the Upper Bound Using Shortcuts
An initial tour may be found using a simple method such as the nearest neighbour algorithm.
This tour gives an upper bound for the TSP.
The upper bound can then be improved by:
- identifying crossings in the route
- replacing two edges by a shorter pair of edges (shortcut)
Because the triangle inequality holds, these shortcuts do not increase the total length.
Key Examination Points
- Understand the difference between practical and classical TSP
- Be able to explain and use the triangle inequality
- Know how shortcuts improve an upper bound
- Clear reasoning is more important than complex calculations
Example
A delivery driver must visit towns A, B, C and D and return to A. The distances (in km) are:
AB = 8, AC = 6, AD = 10, BC = 7, BD = 9, CD = 5
Use a sensible trial route to find a short tour and state its total length.
▶️ Answer / Explanation
Choose a reasonable route by inspection, for example:
A → C → D → B → A
Calculate its length:
AC + CD + DB + BA
\( \mathrm{6 + 5 + 9 + 8 = 28} \)
Conclusion:
A short practical tour has length \( \mathrm{28} \) km.
This may not be optimal, but it is a good solution for the practical TSP.
Example
Four cities form a complete graph satisfying the triangle inequality. The distances are:
AB = 4, AC = 6, AD = 5, BC = 3, BD = 7, CD = 4
Find a lower bound and an upper bound for the shortest travelling salesman tour.
▶️ Answer / Explanation
Lower bound
Take the two smallest edges from each vertex:
A: 4, 5 B: 3, 4 C: 3, 4 D: 4, 5
Sum = \( \mathrm{4+5+3+4+3+4+4+5 = 32} \)
Lower bound = \( \mathrm{32 / 2 = 16} \)
Upper bound
Try the route A → B → C → D → A
Length = \( \mathrm{4 + 3 + 4 + 5 = 16} \)
Conclusion:
Lower bound = \( \mathrm{16} \)
Upper bound = \( \mathrm{16} \)
Therefore, the shortest possible tour has length \( \mathrm{16} \).
Example
A classical TSP tour for cities A, B, C, D and E is:
A → B → C → D → E → A
The edges BC and DE cross. Explain how a shortcut can be used to improve the upper bound.
▶️ Answer / Explanation
Since the graph satisfies the triangle inequality, crossed edges can be replaced by shorter connections.
Replace edges:
BC and DE
with:
BD and CE
This removes the crossing and reduces the total distance.
Conclusion:
The new tour is shorter than the original one.
The upper bound is improved using shortcuts, without increasing the route length.