The Travelling Salesman Problem (Edexcel International AS 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 visits every vertex in the network and returns to the start vertex

    • A tour could visit a vertex more than once

    • A tour is a Hamiltonian cycle if it visits each vertex (other than the start vertex) exactly once 

• For the classical travelling salesman problem 

  • Each vertex is visited exactly once before returning to the start vertex

• For the practical travelling salesman problem

  • Each vertex must be visited at least once before returning to the start vertex

• There is no algorithm that will always provide an optimal solution

  • A lower and upper bound can be generated 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

  • Therefore 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?

• For smaller networks, values in the table of least distances can often be found by inspection

  • Using Dijkstra's algorithm will always find the shortest routes between pairs of vertices

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

• 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
  Complete the row for a particular vertex with the distance between that vertex and each adjacent vertex

  • 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 all remaining (non-adjacent) vertices
  Make sure the value used is 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
  Repeat STEP 2 to STEP 4 for each vertex until the table is complete