This revision note discusses more complex situations for the?travelling salesman problem?and you may wish to refer to the revision note?3.10.5 Travelling Salesman Problem.

In some real-life contexts a graph may not be?complete?nor satisfy the?triangle inequality, for example, when looking at a rail network, not every stop will be connected to every other stop and it may be quicker to travel from stop A to stop B via stop C rather than to travel from A to B directly. Thus, the problem is considered to be a?practical travelling salesman problem.

Finding the?table of least distances?(or weights) can convert a?practical travelling salesman problem?into a?classical travelling salesman problem?that can then be analysed.

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
• By finding the?table of least distances, a graph can be converted into a?complete?graph that satisfies the?triangle inequality
• STEP 1
  Fill in the information for vertices that are adjacent in the graph (at this stage check if the direct connections are actually the shortest route)
• STEP 2
  Complete the rest of the table by finding the shortest route that can be travelled between each pair of vertices that are not adjacent

As the number of vertices in a graph increases, so does the number of possible Hamiltonian cycles and it can become impractical to solve. The?nearest neighbour algorithm?can be used to find the?upper bound?for the?minimum?weight?Hamiltonian cycle.

What is the nearest neighbour algorithm?

• For a complete graph 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?so 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
  Follow 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)
• STEP 3
  Repeat STEP 2 until all vertices have been visited
• STEP 4
  Add the final edge to return to the starting vertex

The?deleted vertex algorithm?can be used to find the?lower bound?for the?minimum?weight?Hamiltonian cycle.

What is the deleted vertex algorithm?

• The deleted vertex algorithm can only be used on a graph that is?complete?and satisfies the?triangle inequality?so the?table of least distances?should be found first
• Deleting?different?vertices may give different results, the?best lower bound?is the lower bound with the?highest value
• If you have found a?cycle?the?same length?as the?lower bound?then you have found the?shortest route?for the travelling salesman problem
• If the?lower bound?and the?upper bound?are the?same weight?then you have found the?shortest route?for the travelling salesman problem

What are the steps of the deleted vertex algorithm?

• STEP 1
  Choose a vertex and delete it along with all edges that are connected to it
• STEP 2
  Find the minimum spanning tree for the remaining graph (see revision note?3.10.3 Minimum Spanning Trees)
• STEP 3
  Add the two shortest edges that were deleted from the original graph to the weight of the minimum spanning tree