Upper & Lower Bounds for the Travelling Salesman Problem (Edexcel A Level Further Maths: Decision Maths 1)

Why do I need to find an upper bound?

• There is no efficient algorithm to find the optimal solution for the travelling salesman problem
  • An upper and lower bound for the solution to the problem can be found
  • The optimal solution (the shortest route) will lie within these bounds
• The aim is to find the minimum value for the upper bound to reduce the size of interval between the upper and lower bounds

How do I find the upper bound?

• You can find an upper bound for the practical travelling salesman problem using the minimum spanning tree of a network
   
• STEP 1
  Find the minimum spanning tree for the network using either Prim's or Kruskal's algorithm
  • If you have the table of least distances - use Prim's algorithm
  • If you have the graph only - use Kruskal's algorithm
     
• STEP 2
  Double the weight of the minimum spanning tree
  
  • Each vertex can therefore definitely be visited and the starting vertex returned to
     
• STEP 3
  Reduce the weight of the upper bound by finding shortcuts
  
  • Use some of the edges that are not included in the minimum spanning tree to reduce the weight of the upper bound

Why do I need to find the lower bound?

• There is no efficient algorithm to find the optimal solution for the travelling salesman problem
  • An upper and lower bound for the solution to the problem can be found
  • The optimal solution (the shortest route) will lie within these bounds
• The aim is to find the maximum value for the lower bound to reduce the size of interval between the upper and lower bounds
• An optimal solution is found if
  • the lower bound gives a Hamiltonian cycle
  • the lower bound has the same value as the upper bound

How do I find the lower bound?

• You can find a lower bound for the classical travelling salesman problem using the minimum spanning tree of a network
  • To find a solution for the practical travelling salesman problem you need to apply the steps of the algorithm below to a table of least distances
     
• STEP 1
  Remove a vertex and all of its associated edges from the network
   
• STEP 2
  Find the minimum spanning tree for the remaining network and write down its total weight
  • This spanning tree is known as the residual minimum spanning tree (RMST)
     
• STEP 3
  Identify the two shortest individual edges that can connect the missing vertex to the residual minimum spanning tree
  Calculate the sum of the total weight of the residual minimal spanning tree and the two connecting edges
   
• STEP 4
  Repeat Steps 1 to 3 for each vertex in the network
   
• STEP 5
  When the network has been tested for each missing vertex, identify the maximum value
  • This maximum value is the greatest possible lower bound

• In many problems Steps 4 and 5 will not be required as a question will dictate which vertex to delete and there will be no need to do them all
• This method may be referred to as the deleted vertex method

What is the nearest neighbour algorithm?

• For a complete network with at least 3 vertices, performing the nearest neighbour algorithm will generate a low (but not necessarily least) weight Hamiltonian cycle
  • This low weight cycle can be considered the upper bound
• The best upper bound is the upper bound with the smallest value
• The nearest neighbour algorithm can only be used on a graph that is complete and satisfies the triangle inequality
  • If need be the table of least distances should be found first

What are the steps of the nearest neighbour algorithm?

• STEP 1
  Choose a starting vertex

• STEP 2
  Select the edge of least weight from the current vertex to an adjacent unvisited vertex
  • if there is more than one edge of least weight pick one at random
  • move to this vertex (column in matrix form)
  • if this is the final vertex to be visited go to Step 3
  • otherwise disregard (cross out in matrix form) any edges that go to vertices already visited and repeat Step 2

• STEP 3
  Add a final edge to return to the starting vertex

• STEP 4
  Find the weight of the resulting Hamiltonian cycle to produce an upper bound for the travelling salesman problem

• STEP 5
  Repeat Steps 1 to 4 starting with a different vertex in the network
  When the network has been tested for each vertex as the starting vertex, identify the minimum value
  This minimum value is the least possible lower bound

• In many problems Step 5 will not be required as a question will dictate which vertex to start at and there will be no requirement to repeat with all vertices as the starting vertex