The Travelling Salesman Problem (Edexcel A-Level Further Mathematics): Revision Notes

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:

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:

1. Start at the initial vertex.
2. Move to the nearest unvisited vertex.
3. Repeat step 2 until all vertices are visited.
4. 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

Note Summary