Chapter 5 - The travelling salesman problem

walk

finite sequence of edges such that the end verttex of one edge is the start vertex of the next

tour

walk that visits every vertex returning to its staaring vertex

classical travelling salesman roblem

each vertex must be visited exactly once before returning to the start

ractical travelling salesman roblem

each vertex must be vistied at least once before returnign to the start

triangle inequality

longest side of any triangle is less than or equal to the sum of the 2 shorter sides if it doesnt hold true relace the longest are in those triangles by the sum of the 2 smaller ones

mimimum spanning tress to find an upper bound

1. find the minimum spanning treee for the network

2. double this minimum connectorsso that completing the cycle is guarenteed

3. finally seek shortcuts

how us an inital upper bound found

doubling the weight of the minimum spanning tree

minimum spanning tree to fn lower bound for classical problem

• Remove each vertex in turn, together with its arcs.

• Find the residual minimum spanning tree (RMST) and its length.

• Add to the RMST the 'cost' of reconnecting the deleted vertex by the two shortest, distinct, arcs and note the totals.

• the greatest of these totals is used for the lower bound

• make the lower bound as high as possible to reduce the interval in which the optimal solution is containes

• you have found an optimal solution if the lower bound gives a hamiltonian cycle or the lower bound is the same value as the upper boun

nearest neighbour alogrith mto find upper bound

Select each vertex in turn as a starting point. Go to the nearest vertex which has not yet been visited. Repeat step 2 until all vertices have been visited and then return to the start vertex using the shortest route. Once all vertices have been used as the starting vertex, select the tour with the smallest length as the upper bound.