Santa's delivery problem
0th December
 |
It is widely recognised that Santa Claus covers a lot of territory on Christmas Eve. What is not so readily understood is the difficulties he faces in planning his route.
The phone book lists about 10,000 postcode localities across Australia. Should Santa start in the east and move generally west, to give him the maximum delivery time? Or should he deliver to the biggest cities first, to reduce the tonne-kilometre load factor for the poor reindeer? How can he avoid backtracking, so obviously a time-waster?
Dr Rob Womersley, a computational mathematician at UNSW, would not even try to calculate how many route options Santa could choose.
“Santa’s problem is well known to mathematicians, as the ‘travelling salesman problem’ and it is a real-life issue, with real-life applications”, Rob says. “For large numbers of towns it is practically impossible to calculate all possible routes, although a mathematician has derived a formula, called Stirling’s approximation, that allows us to get an idea of the size of the problem.”
Even by limiting Santa’s itinerary to a mere 50 cities, Rob said it would take the world’s fastest computer 3 seconds multiplied by ten to the power of 52, to calculate all possible routes.
As the age of the Universe in seconds is only about ten to the power of 17, Santa must have a very fine mind indeed to work out his optimum route around Australia, Rob said. Finding the perfect solution is impossible, so Santa should settle for a good route rather than the best.
For those who want to study the maths behind Santa’s problem, Stirling’s approximation can be found at www.mathworld.wolfram.com
The phone book lists about 10,000 postcode localities across Australia. Should Santa start in the east and move generally west, to give him the maximum delivery time? Or should he deliver to the biggest cities first, to reduce the tonne-kilometre load factor for the poor reindeer? How can he avoid backtracking, so obviously a time-waster?
Dr Rob Womersley, a computational mathematician at UNSW, would not even try to calculate how many route options Santa could choose.
“Santa’s problem is well known to mathematicians, as the ‘travelling salesman problem’ and it is a real-life issue, with real-life applications”, Rob says. “For large numbers of towns it is practically impossible to calculate all possible routes, although a mathematician has derived a formula, called Stirling’s approximation, that allows us to get an idea of the size of the problem.”
Even by limiting Santa’s itinerary to a mere 50 cities, Rob said it would take the world’s fastest computer 3 seconds multiplied by ten to the power of 52, to calculate all possible routes.
As the age of the Universe in seconds is only about ten to the power of 17, Santa must have a very fine mind indeed to work out his optimum route around Australia, Rob said. Finding the perfect solution is impossible, so Santa should settle for a good route rather than the best.
For those who want to study the maths behind Santa’s problem, Stirling’s approximation can be found at www.mathworld.wolfram.com
Share on Facebook Add to Del.icio.us Digg this story |