Help solve Santa's logistics troubles with a little maths

Dec 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: Woman's secret Santa turns out to be Bill Gates

Related Stories

Shrinking blob speeds traveling salesman on his way

Mar 26, 2013

(Phys.org) —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? ...

Recommended for you

US company sells out of Ebola toys

Oct 17, 2014

They might look tasteless, but satisfied customers dub them cute and adorable. Ebola-themed toys have proved such a hit that one US-based company has sold out.

New progress of the Neogene Suidae research

Oct 17, 2014

Dr. Hou Sukuan and Prof. Deng Tao from the Institute of Vertebrate Paleontology and Paleoanthropology(IVPP), Chinese Academy of Sciences reported a new species of Chleuastochoerus from the Linxia Basin, Gansu ...

Gypsies and travellers on the English Green Belt

Oct 17, 2014

The battle between Gypsies, Travellers and the settled community over how land can be used has moved to the Green Belt, observes Peter Kabachnik of the City University of New York.

Cadavers beat computers for learning anatomy

Oct 16, 2014

Despite the growing popularity of using computer simulation to help teach college anatomy, students learn much better through the traditional use of human cadavers, according to new research that has implications ...

User comments : 3

Adjust slider to filter visible comments by rank

Display comments: newest first

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