The Olympic torch tour
Imagine you had to plan the tour for the Olympic Torch. Is there an efficient way of choosing the shortest possible route?
Problem
If you are a teacher, click here for a version of the problem suitable for classroom use, together with supporting materials. Otherwise, read on...
In May 2012, the Olympic torch will arrive at Lands End for a 70 day tour of the UK, ending in London. The plan is to cover towns and villages so that 95% of Britons will be within 10 miles of the torch relay.
Imagine a mini-Olympic torch tour running between 4 cities in the UK, with the following constraints:
- The torch starts and finishes in London
- The torch should pass each city once and only once
- The following table lists the distance between each city
(in miles as measured by Google Maps)
| London | Cambridge | Bath | Coventry | |
| London | 0 | 50 | 96 | 86 |
| Cambridge | 50 | 0 | 120 | 70 |
| Bath | 96 | 120 | 0 | 80 |
| Coventry | 86 | 70 | 80 | 0 |
- What is the shortest route?
- How can you be sure it is the shortest?
- How many different routes are there?
| London | Cambridge | Bath | Coventry | Oxford | |
| London | 0 | 50 | 96 | 86 | 60 |
| Cambridge | 50 | 0 | 120 | 70 | 65 |
| Bath | 96 | 120 | 0 | 80 | 54 |
| Coventry | 86 | 70 | 80 | 0 | 46 |
| Oxford | 60 | 65 | 54 | 46 | 0 |
- What is the shortest route now?
- How many different possible routes did you need to consider?
Is there an efficient way to work out the number of different possible routes when there are 10 cities? 15 cities?...
Suppose a computer could calculate one million routes per second. How long would it take to find the optimal route for 10 cities? 15 cities? 20 cities?
The type of question we have explored above is a famous problem in computation complexity theory known as the Travelling Salesman Problem. Perhaps a better question for the torch tour is not to find the shortest or longest route, but to find the maximum number of cities the torch can visit whose route length is at most, say 2000 miles, or visit as many populated towns as possible. These are variants of the original problem known as the 'Orienteering Problem' and the 'Prize Collecting Travelling Salesman Problem'. It is an active area of research among mathematicians and has a wide range of applications.
Getting Started
You could try to list all the possible routes and calculate the distance the torch would need to travel for each.
Student Solutions
Niharika was the only one to send us a solution this time round:
The possible routes are:
1. London-Cambridge-Bath-Coventry-London
2. London-Cambridge-Coventry-Bath-London
3. London-Bath-Cambridge-Coventry-London
4. London-Bath-Coventry-Cambridge-London
5. London-Coventry-Bath-Cambridge-London
6. London-Coventry-Cambridge-Bath-London.
I worked out the distances for each route, and they came to:
1. 336 miles
2. 296 miles
3. 372 miles
4. 296 miles
5. 336 miles
6. 372 miles
The shortest routes are routes 2 and 4.
Now imagine that each city along our route is a box. We have five boxes to line up. The first and last box must be 'London', so there is only 1 way to fill those boxes. The second box can be filled in one of 3 ways. Once we've used that city up, the third box can be filled in 2 ways. Finally when we come to the fourth box there is only 1 way to fill it in. So there are 1*3*2*1*1 = 6 routes.
I guessed that, when extending to 5 cities, we should probably start with the shortest route for 4 cities and then add the extra city in. In this case, we should start with routes 2 and 4, and add Oxford in in all the different places, and see which distance is smallest. In each case, least distance is covered if we add in Oxford between Coventry and Bath. In this case there are 6 boxes and 1*4*3*2*1*1 = 24 routes.
When there are n cities, there are n+1 boxes, and so there are $1\times (n-1)\times (n-2)\times \dots \times 2 \times 1\times 1$ routes - just think of how many ways there are to fill in each box. But if you know the shortest routes for the case of n-1 cities, my guess is that you should be able to add the n-th city to those.
Great - thanks, Niharika!
Teachers' Resources
Why do this problem?
As well as encouraging students to work systematically, this problem introduces ideas from Decision Maths and Computer Science such as the Travelling Salesperson problem and the efficiency of algorithms.
Possible approach
Hand out this worksheet and encourage students to work on their own or in pairs on the first part of the problem with four cities. Bring the class together to discuss the sort of strategies they used to find a short route, and to discuss the checking that was necessary to be sure that their route was the shortest.
Once students are happy with the idea that a 'brute force' algorithm that checks every possibility is the ONLY way to be certain of finding the shortest route, set them the second challenge to find the shortest route when there are five cities.
"You need to be able to convince everyone that the route you find is the shortest. Think about how you could record your work to make sure you don't miss any possible routes."
While students are working, circulate and notice anyone who is using a particularly useful representation such as a systematic way of listing possible routes, or a tree-diagram approach. Bring the class together and invite those students to share their representations.
"Why does it take longer to check all the routes for five cities than four?"
"Is there a quick way to work out how many different possible routes there will be, for six cities?"
"How will the number of possible routes continue to grow?"
Finally, as students begin to get some appreciation of the way the number of routes grows as the number of cities increases, challenge them to work out the time taken to implement the brute force algorithm by computer.
Key questions
How can you represent the different routes in a way that makes sure you don't miss any?
If I add in an extra city, how does that affect the number of different possible routes?
Possible extension
There are rich opportunities for students to go and research topics in Decision Mathematics and Computer Science and to learn about the challenges involved in seeking solutions to problems using computers.