# Why take the Traveller Challenge?

This challenge encourages you and your family to think about the **mathematical idea of optimisation**. Optimisation exists in many decisions that we make.

By trying to find the shortest route someone could take on their travels you will discover the complexity involved in optimisation processes.

# Connections to real life

Optimisation exists in may decisions that we make. From planning and logistics to even drilling holes in a circuit board, the concept of optimisation can be applied. It is integral to computer science.

With self-driving cars possibly appearing on our roads in the future, computers onboard these cars will use optimisation strategies to find the most efficient travel routes to take.

# 1. Setting the scene

This challenge is based on *‘the travelling salesman problem’* – a mathematics and computer science problem, which asks what is the quickest route a traveling salesman might follow when he has a number of towns to visit on a given day.

Did you know that there are over 180,000 possible combinations of ways to visit 10 different cities? The formula to calculate this is: (number of cities – 1) 1/2

For ten cities that’s (9 x 8 x 7 x 6 x 5 x 4 x 3 x 2)/2 = 181,440

To find out how many possible combinations there are for 16 places type 15!/2 into Google. Can you say that number in words?

# Links to the curriculum

# Maths words

**optimisation **– finding the best solution for any given situation.

**approximation **– finding a result that is close to the answer.

Find more maths words in the Glossary.

# 2. The Challenge

Find the shortest route a traveller could take.

**Split into teams**. You may like to work by yourself or pair up with another person.**Print a copy of this worksheet**for each team member. If you don’t have access to a printer you can draw your own copy.**Moving from point A, visit every red dot and return to Point A.****Count your total travel distance.**Each two dots you travel between counts as 1.**Try more combinations.**See if you can get your total distance as low as possible.- After 10 minutes, see which team has the
**smallest total travel time.** **Discuss**how you worked through the problem.

# Coach Chloe’s advice

Hi, I’m Coach Chloe. If you are stuck, I have some questions and suggestions that might help.

There are more than 180,000 solutions to this question so you are going to need to use a method of guess and check might be useful. After you have a route you like, try making small changes to slowly improve your answer.

You could make a list each route you try like this A-K-L-N-M-H-I-G-J-E-B-D-C-F-A.

You could also make a table of the combinations you try like this:

Route | Distance |

A-G-E-C-B-F-D-I-H-K-L-M-N-J-A | 74 |

A-K-L-N-M-H-I-G-J-E-B-D-C-F-A | 60 |

# 3. Keep going

**Find the best place to place a hardware store.**

**Split into teams**. You might like to change teams at this point.**Print a copy of this sheet for each team**. If you don’t have access to a printer you can draw your own copy.- Decide where the best place for a hardware store might be to
**minimise travel distance.** - Count your
**total travel distance**for a person in each location to travel one way to the hardware store. Each two dots you travel between counts as 1. **Try more combinations.**See if you can get your total distance as low as possible.- After 10 minutes, see which team has the
**smallest total travel time.** **Discuss**how you worked through the problem.