Mathematics: The Travelling Salesperson Algorithm

Find a cycle that goes through each vertex using the Nearest Neighbour Algorithm.

Find the lower bound by using the Lower Bound Algorithm.

The weight of the optimum route is: Lower bound ≤ Weight of optimum route ≤ Upper bound

Upper Bound Algorithm (Nearest Neighbour Algorithm)

Choose a starting vertex unless assigned one.

Choose the nearest unused vertex.

Continue until all vertices are visited and return to starting vertex.

Start at A

Total weight = 24

Start at B

Total weight = 20

Start at C

Total weight = 23

Start at D

Total weight = 20

Start at E

Total weight = 23

Lowest upper bound = 20

Lower Bound Algorithm

Choose a vertex unless assigned one.

Find the two lowest weight edges joined to that vertex and note them.

Delete that vertex and all the edges joined to it.

Find the minimum spanning tree for the rest of the network.

Add the minimum spanning trees value to the noted edges to get the total weight.

Delete A

Delete B

Delete C

Delete D

Delete E

Highest lower bound = 18

18 ≤ Weight of Optimum Route ≤ 20

Mathematics