The Travelling Salesman Problem
A problem with real life applications
Graph Theory has applications to science, linguistics, sociology and computer science. It has direct applications to electronic circuitry and also to satellite navigation software used by vehicles in order to find the best route to reach a destination.
​
Constructing a graph diagram can be an excellent method of simplifying a complex problem and then using results from Graph Theory to attack it.
Sattelite navigation systems need to find the most efficient route
This approach is used to tackle the Travelling Salesman Problem (TSP). The TSP is an important and difficult problem which has many real world applications from efficient planning and logistics to the manufacture of microchips. It is an example of an optimisation problem.
​
Mathematicians have used results from graph theory to find the best solutions to the TSP even in very complex networks.
The Travelling Salesman Problem
Consider the ‘map’ which shows four cities (A,B,C,D) all joined by roads. The distance in kilometres between each city is shown in the diagram. (Notice that this is a complete graph, K4)
​
The Travelling Salesman starts and ends his journey at A. He must visit each city once and return to A. He must cover the minimum possible distance. Which route is best?
A → B → C → D → A 60 km
A → B → D → C → A 85 km
A → C → B → D → A 55 km
A → C → D → B → A 85 km
A → D → B → C → A 55 km
A → D → C → B → A 60 km
The shortest routes are ACBDA or ADBCA which are 55km long.
Each route is calculated twice - once in each direction.
​
This problem is fairly simple to analyse as there are 1 x 2 x 3 = 6 possible routes (and three of them are equivalent routes run in the reverse order).
If we introduce two new cities E and F, the situation looks much more complex and you will need to calculate 1 x 2 x 3 x 4 x 5 = 120 routes (60 if you ignore equivalent routes.
If you wish to find the best route for this problem, the answer is at the bottom of the page.
Now, if there were 11 cities (including the starting point A) then there would be:
​
10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
​
= 3,628,800 routes
Real life applications can have many more than 11 cities and also complications such as one-way streets, speed limits and alternative routes to the destination.
​
No wonder the Travelling Salesman problem is difficult to tackle!
The shortest route is ADEFCBA which has a distance of 85km.