# Help solve Santa's logistics troubles with a little maths

##### December 23, 2013 by Graham Kendall, The Conversation

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.

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.

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

#### Woman's secret Santa turns out to be Bill Gates

December 19, 2013

One woman's secret Santa this holiday season turned out to be one of the richest men in the world: Microsoft co-founder Bill Gates.

#### Santa being tracked by Microsoft and Google

December 4, 2013

The competition between Microsoft and Google is stretching to the North Pole as the Internet search rivals vie to be top Santa tracker this Christmas.

#### Shrinking blob speeds traveling salesman on his way

March 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? The most accurate ...

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

December 8, 2008

(PhysOrg.com) -- Don't believe in Santa Claus? Cutting-edge science explains how Santa is able to deliver toys to good girls and boys around the world in one night.

#### 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 ...

#### Want to track Santa? There's an app for that

December 1, 2011

(AP) -- Want to keep track of Santa this Christmas? There's an app for that.

## Recommended for you

#### Development of new techniques makes it possible to date Australian Aboriginal rock art

December 7, 2016

A new technique, developed at ANSTO's Centre for Accelerator Science, has made it possible to produce some of the first reliable radiocarbon dates for Australian rock art in a study just published online in The Journal of ...

#### Fossils of early tetrapods unearthed in Scotland

December 7, 2016

(Phys.org)—A team of researchers working at a dig site in Scotland has found tetrapod fossils dated to approximately 15 million years after the Devonian mass extinction—a time period experts in the field have referred ...

#### Asian countries dominate, science teaching criticised in survey

December 6, 2016

Asian countries dominated the top places in a key survey released Tuesday of high-school skills, but the report criticised science teaching in many countries.

#### Secrets of the paleo diet: Discovery reveals plant-based menu of prehistoric man

December 5, 2016

A tiny grape pip (scale 1mm), left on the ground some 780,000 years ago, is one of more than 9,000 remains of edible plants discovered in an old Stone Age site in Israel on the shoreline of Lake Hula in the northern Jordan ...

#### Mummified remains identified as Egyptian Queen Nefertari

December 5, 2016

A team of international archaeologists believe a pair of mummified legs on display in an Italian museum may belong to Egyptian Queen Nefertari - the favourite wife of the pharaoh Ramses II.

#### Geoscientists size-up early dinosaurs, find surprising variation

December 5, 2016

Look out your window, and you may see people of all ages and sizes roaming the street: a 6-foot-5-inch man walking beside a 4-foot-6-inch boy, for example, or a sprouting teen-ager who is much taller than a full-grown adult.

##### foolspoo
not rated yet Dec 23, 2013
=) cute
##### FainAvis
not rated yet Dec 23, 2013
But who cleans up the reindeer exhaust?