Solving the Travelling Salesman Problem
How do I solve the travelling salesman problem?
- List all of the possible Hamiltonian cycles and find the cycle of least weight
- A complete graph with 3 vertices will have 2 possible Hamiltonian cycles, 4 vertices will have 6 possible cycles and a graph with 5 vertices will have 24 possible cycles
- There is no known algorithm that guarantees finding the shortest Hamiltonian cycle in a graph so this method is only suitable for small graphs
Examiner Tip
- To remember the difference between the travelling salesman problem and the Chinese postman problem, remember that the salesman is interested in selling at each destination (vertex) whereas the postman wants to walk along every road (edge) in order to deliver the letters
Worked example
The network below contains six vertices representing villages and the edges (roads) that connect them. The weighting of the edges represents the time, in minutes, that it takes to walk along a particular road between two villages.
The dashed lines indicate the edges that are to be repeated to convert the network into a complete network.
The lower bound for the time taken to walk a route that visits every vertex and returns to the start vertex is 53 minutes.
Starting from vertex A, find a route that shows that this is the optimal solution.
Because the network has 6 vertices there will be 120 possible different Hamiltonian cycles - this is too many to check!
However, you are told to start at vertex A and you are told to confirm that the route you have found is the optimal solution, this means that it should have the same weight as the lower bound for the problem.
Find a Hamiltonian cycle starting at vertex A.
AB (14)
BF (9)
EF (8)
CF (6)
CD (5)
AD (11)
Calculate the total weight of the cycle.
14 + 9 + 8 + 6 + 5 + 11 = 53
The route ABFECDA has the same weight (53 minutes) as the lower bound of the problem, therefore it is the optimal solution
