Help solve Santa's logistics troubles with a little maths

December 23, 2013 by Graham Kendall, The Conversation
It’s a long way for one man and his reindeer to travel. Credit: Jpatokal

In just one night, Santa has to visit millions of homes to deliver presents. If he could travel at the speed of light, the task would be simple.

However, Einstein's formula, E=MC², tells us that anything with mass cannot travel faster than the speed of light. And as we all know, Santa has mass. That's before you even count all the presents that have to be transported along with his sleigh. Then add Rudolph and co and what you get is a lot of flying mass that makes Santa's chances of travelling faster than light pretty slim.

Luckily, there are other options available to Santa to help increase his chances of delivering all the presents on time. And they relate to what is known in maths as The Travelling Salesman Problem.

In this problem, a salesman has to plan a through a number of cities. He has to start and end at the same city and visit every other city in between just once, while minimising the distance he travels. If we replace the salesman with Santa and the cities with chimneys, then Santa's problem is a variant of the Travelling Salesman Problem.

Unfortunately, this isn't much consolation to Santa. The Travelling Salesman Problem is known to be NP-Complete. This means that there is no known efficient algorithm that always returns the optimal solution in a reasonable time.

Even Einstein couldn’t solve Santa’s woes.

In fact, most mathematicians and computer scientists believe that no such algorithm exists, although this is yet to be proved. Anyone who can prove that it does exist (or indeed that it doesn't) stands to win $1 million for solving one of the Millennium Problems and proving whether P=NP (or not).

Back to Santa. What can he do to plan his route? Although we do not know of an algorithm that is guaranteed to tell Santa the best route to take, there are algorithms that attempt to do this in reasonable time.

The Route Santa application, from Napier University, is one. The app shows an example of an algorithm solving the Travelling Santa Problem. Those hoping to receive gifts on the 25 December can contribute to the efficient running of Santa's rounds by uploading their address into an interactive map. The Route Santa software will then add that address to its list and work out the best route for Rudolph. The more hopeful recipients that sign up, the more efficient Santa's journey will be.

One type of the used for these type of problems are known as genetic algorithms because they are based on natural phenomena such as evolution, inheritance and selection.

Help solve Santa's logistics troubles with a little maths
It’s not even simple when he gets to his destination.

Santa's problem is your problem too

We tend to take it for granted that Santa will make his millions of deliveries on time every year but the Travelling Salesman Problem affects our daily lives, particularly now that so much of what we buy, from our food to our clothes and technology is delivered to our doors. If we can work out the best route for Santa, we can also contribute to thinking about how to make other delivery services more efficient for the other 11 months of the year.

Explore further: Science of Santa: Researcher Says St. Nick Can Deliver Presents in One Night

Related Stories

Researcher explains how Santa delivers presents in one night

December 7, 2011

Don’t believe in Santa Claus? Magic, you say? In fact, science and technology explain how Santa is able to deliver toys to good girls and boys around the world in one night, according to a North Carolina State University ...

Shrinking blob speeds traveling salesman on his way

March 26, 2013

( —What is the shortest route that a traveling salesman must take to visit a number of specified cities in a tour, stopping at each city once and only once before returning to the starting point? The most accurate ...

Recommended for you

Biologists trace how human innovation impacts tool evolution

November 24, 2015

Many animals exhibit learned behaviors, but humans are unique in their capacity to build on existing knowledge to make new innovations. Understanding the patterns of how new generations of tools emerged in prehistoric societies, ...

First Londoners were multi-ethnic mix: museum

November 23, 2015

A DNA analysis of four ancient Roman skeletons found in London shows the first inhabitants of the city were a multi-ethnic mix similar to contemporary Londoners, the Museum of London said on Monday.


Adjust slider to filter visible comments by rank

Display comments: newest first

not rated yet Dec 23, 2013
=) cute
not rated yet Dec 23, 2013
But who cleans up the reindeer exhaust?
not rated yet Dec 26, 2013
The obvious answer is quantum entanglement.

Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.