How do we route Santa?

Some things seem very simple, supposing I ask you to visit 10 friends in the shortest possible distance.

This is quite an easy problem for us to solve simply by looking at a map. But in how many different orders can you arrange the 10 visits?
The number of possible ways in which we can visit our 10 friends is calculated as ... = (10x9x8x7x5x4x3x2x1)/2*10.
So there are 181,440 different orders we can visit our friends in!

Santa on a PC

For a simple problem such as visiting 10 friends we can easily solve the problem by looking at a map and using some common sense.

Q: What if Santa has to visit 50 houses?...

A: There would be 3041409320171337804361260816606476884437764156896051200000000000 possible routes that he can take....! If we have to visit more than a few houses it becomes impossible to check all of the possible routes, even using a computer would take a very long time.

Q: How can we solve a complex problem like this quickly?...

A: We can solve this problem using a simple computer program known as an Evolutionary Algorithm.

It works like this..

1) Create a group of routes each visiting all of the houses in a random order
2) Work out the length of each route
3) Pick random pairs of some of the shortest routes in our group
4) From each pair of routes, create a new route containing some of the route from each of the pair (the new routes must still visit all of the houses)
5) Make a random change (such as swapping the order of two houses) to each of the new routes
6) Measure the length of the new routes
7) Add each of the new routes back into the main group, replacing a longer route
8) Go back to step 2

After running this program for a while, we should find that our routes are getting shorter and shorter. There's no guarantee that our programme will find the shortest route, but after a short time, it should find a good short route, the longer we run the program the shorter the routes should become, if we run the program for long enough it should find the shortest route

We have an Evolutionary Algorithm running on the GrotoServer, which is constantly trying to evolve shorter routes. It runs constantly, so the route will evolve over time.

About the author

Dr Neil Urquhart is a lecturer at Edinburgh Napier University, School of Computing (SOC) where he teaches software engineering and leads the BSc Computing Science course.

He is a researcher in the Institute for Informatics and Digital Innovation where his research interests include the application of Evolutionary Algorithms and other techniques to the optimisation of scheduling and routing problems. He has a special interest in the challenges involving the optimisation of real-world problems.