1. My TSR
  2. Revision help and tips
  3. Mathematics

Revision:The travelling salesman problem

A Hamiltonian cycle is a tour that contains every node precisely once. Therefore, the classic travelling salesman problem is to find the Hamiltonian cycle of minimum weight - i.e. the shortest route passing through each node once.

As the number of nodes increases the number of possible Hamiltonian cycles increases very rapidly. For n nodes the number of Hamiltonian cycles is .

The method of evaluating all Hamiltonian cycles therefore has exponential order. A 600MHz processor evaluating cycles for 20 nodes takes about 3 years. Testing each of these cycles to find the optimal solution is generally too time consuming to be feasible for most problems, so finding a reasonably good solution with the Nearest Neighbour algorithm suffices.

The Nearest Neighbour algorithm

  1. Choose any starting node
  2. Consider the arcs which join the previously chosen node to nodes not yet chosen. Choose the arc with minimum weight and add this node to the tour.
  3. Repeat 2 until all nodes have been added
  4. Add the arc which joins the last node to the first.

Disadvantages

  • The algorithm does not necessarily give the best solution - it chooses the best route at each node without considering future problems
  • It may lead to an incomplete tour.

The Lower Bound algorithm

This finds the lower weight limit of a Hamiltonian cycle. If the Nearest Neighbour algorithm gives an answer which is significantly higher than the lower bound, it suggests there is a better solution. If the NN algorithm gives an answer which equals the lower bound, the tour is optimum.

  1. Choose any node, X. Find the total of the 2 smallest weight arcs joined to X.
  2. Consider the network obtained by ignoring X and any arcs that join to X. Find the total weight of the minimum connector for this network.
  3. The sum of the two totals is the lower bound.

\mathrm{lower\ bound} \leq \mathrm{optimum\ solution} \leq \mathrm{nearest\ neighbour\ solution}

Tour Improvement

This algorithm attempts to improve the best solution found so far.

  • Let 1, 2, 3 ... n be the successive nodes of a Hamiltonian tour (NB n+1=1, n+2=2, n+3=3)
  • Let d(V,W) be the weight of the arcs between V and W
  1. Let i =1
  2. If d(i, i+2) + d(i+1, i+3) < d(i, i+1) + d(i+2, i+3) then swap i + 1 and i + 2. (I.e. for i=1, if the weight between node 1 and the node 3 plus the weight between node 2 and node 4 is less than the weight between node 1 and node 2 plus the weight between node 3 and node 4, swap the second and third nodes.)
  3. Replace i by i + 1
  4. If i \leq n then go to step 2. (I.e. repeat until i is greater than the number of nodes in the tour.)
Article by TSR User on Monday 24 September 2018