The Travelling Salesman Problem (Edexcel A Level Further Maths): Revision Note

The Classical & Practical Travelling Salesman Problem

What is the Travelling Salesman Problem?

• In the Travelling Salesman Problem, the objective is to find the tour of least weight in a given network

  • A tour is a walk that starts at one vertex and visits every other vertex in the network before returning to the start vertex

• The classical travelling salesman problem requires that each vertex is visited exactly once before returning to the start vertex

• The practical travelling salesman problem requires that each vertex must be visited at least once before returning to the start vertex

• There isn't an algorithm that will definitely provide an optimal solution to the travelling salesman problem

  • However the methods used will provide a lower and upper bound for the tour of least weight

  • If the lower and upper bound happen to be equal, an optimal solution has been found

What is a table of least distances?

• A table of least distances shows the shortest distance between any two vertices in a graph

  • In some cases, the direct route between two vertices may not be the shortest

• The table of least distances creates a complete network and so it will contain a Hamiltonian cycle

• The table of least distances turns a practical travelling salesman problem into a classical travelling salesman problem

How do I find the table of least distances?

• In practice, for smaller networks, the values in the table of least distances can usually be found by inspection of the network

  • The shortest route between two vertices may not be the most direct route 

  • A more robust method of finding the shortest routes between pairs of vertices would be to use Dijkstra's or Floyd's algorithm

    • An exam question will be clear if this is required but given time constraints this is uncommon

• Mathematically, a table of least distances is created by ensuring every entry satisfies the triangle inequality

  • the longest side of a triangle ≤ the sum of the lengths of the other two sides

  • ('Sides of the triangle' could be made from one or more edges in a network - there would be lots of them, even in small networks!)

• To construct a table of least distances follow the steps below

• STEP 1
  Put a line through each cell along the leading diagonal

  • there will be no loops!

• STEP 2
  Fill in the information for a particular vertex in the graph with the distance between that vertex and each vertex that is adjacent to it in the network (i.e. vertices that are directly connected to it)

• At this stage check (by inspection) if the direct connections are actually the shortest distances and change as necessary

• STEP 3
  Complete the rest of the connections between that particular vertex and the remaining (non-adjacent) vertices in the network by finding the shortest route that can be travelled between each pair

• STEP 4
  Copy the values in the completed row down the corresponding column

  • a complete network is undirected so the table of least distances will have symmetry

• STEP 5
  If the table is not complete, return to STEP 2 and continue with the another vertex, otherwise STOP