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

Newlyweds, be careful what you wish for

2 hours ago

A statistical analysis of the gift "fulfillments" at several hundred online wedding gift registries suggests that wedding guests are caught between a rock and a hard place when it comes to buying an appropriate gift for the ...

Can new understanding avert tragedy?

5 hours ago

As a boy growing up in Syracuse, NY, Sol Hsiang ran an experiment for a school project testing whether plants grow better sprinkled with water vs orange juice. Today, 20 years later, he applies complex statistical ...

Crowd-sourcing Britain's Bronze Age

5 hours ago

A new joint project by the British Museum and the UCL Institute of Archaeology is seeking online contributions from members of the public to enhance a major British Bronze Age archive and artefact collection.

Roman dig 'transforms understanding' of ancient port

6 hours ago

(Phys.org) —Researchers from the universities of Cambridge and Southampton have discovered a new section of the boundary wall of the ancient Roman port of Ostia, proving the city was much larger than previously ...

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.

More news stories

Newlyweds, be careful what you wish for

A statistical analysis of the gift "fulfillments" at several hundred online wedding gift registries suggests that wedding guests are caught between a rock and a hard place when it comes to buying an appropriate gift for the ...

Can new understanding avert tragedy?

As a boy growing up in Syracuse, NY, Sol Hsiang ran an experiment for a school project testing whether plants grow better sprinkled with water vs orange juice. Today, 20 years later, he applies complex statistical ...

Crowd-sourcing Britain's Bronze Age

A new joint project by the British Museum and the UCL Institute of Archaeology is seeking online contributions from members of the public to enhance a major British Bronze Age archive and artefact collection.

Roman dig 'transforms understanding' of ancient port

(Phys.org) —Researchers from the universities of Cambridge and Southampton have discovered a new section of the boundary wall of the ancient Roman port of Ostia, proving the city was much larger than previously ...

Tiny power plants hold promise for nuclear energy

Small underground nuclear power plants that could be cheaper to build than their behemoth counterparts may herald the future for an energy industry under intense scrutiny since the Fukushima disaster, the ...

Hand out money with my mobile? I think I'm ready

A service is soon to launch in the UK that will enable us to transfer money to other people using just their name and mobile number. Paym is being hailed as a revolution in banking because you can pay peopl ...