How does Santa deliver all the presents in one night?
07 December 2016
- Santa faces the travelling salesman problem every Christmas night
- Mathematicians have been trying to solve the problem since 1930
- Algorithms help sort millions of presents using demand management system
- In the warehouse Santa uses the shoelace problem to pick up all the toys
Over the last few years next-day delivery has become the norm, but one man has been excelling at it for decades – and I don’t mean just dropping off a handful of parcels around one city.
No, this man manages to deliver to millions of children all over the world in just one night, though according to scientists he could extend that night to 48 hours by following the Earth’s time zones.
How does Father Christmas do it?
Well, his band of elves not only spend all year manufacturing the toys but work out the algorithms that power the computers at the North Pole to sift through all the orders and work out the most efficient delivery route. Even having 48 hours and travelling at the speed of light still requires a finely-tuned set of algorithms to get to all 233 million Christian households and cover around 212 million miles.
First of all there is the delivery of all the toys, games and assorted presents that the elves have made to Santa’s grotto – these days a highly sophisticated automated distribution centre using warehouse robots.
With millions of toys to deliver, it would be chaos if they all arrived at once, so the elves have to go online and choose a slot as to when to deliver them.
Research by Arne Strauss, Associate Professor of Operational Research at Warwick Business School, has designed a dynamic demand management system that incentivises elves to choose the slots that are available.
“The problem is knowing where demand is going to occur,” said Dr Strauss. “Some time slots might be more popular than others, so algorithms can be designed and used on the website to set incentives in such a way that customers (elves) are steered towards selecting slots that are most efficient for Santa, so the deliveries are evenly spread and easier to manage.
“You can manage the whole process by using incentives, such as the size of the delivery charge for different time slots, rewards such as discounts or shopping points for unpopular slots. With each order this is being constantly updated in the background, so the prices or incentives for each slot can change any time.”
With so much to deliver, elves are constantly going back and forth with their goods. Whenever an elf visits the website it gains data about them, so it can start to predict the slots they want next time.
Dr Strauss added: “It has information on where each elf lives, what they deliver and how much, so it can predict when and how much they will be bringing and push them to the slot that would suit them and Santa. Also there will be a cut-off point when all the slots will be full for each day, and so that is constantly being taken into account and then shifted onto the next time horizon.”
To take all this information into account takes a lot of maths, but Dr Strauss has managed to boil down the next-day delivery algorithm as:
Once all the toys have been delivered to Santa’s warehouse then the complicated task of loading the sleigh and working out the quickest route around the world has to be done.
This is where Vladimir Deineko, Associate Professor of Operational Research, and his research on the travelling salesman problem (TSP) comes in. The TSP asks, given a list of cities, what is the shortest possible route that visits each one and returns back to the origin city? Finding an algorithm that solves this problem has kept the greatest minds in mathematics and computational science occupied for decades. It is an NP-hard problem - as they say in maths - a class of problems which are extremely difficult to solve.
Santa has an NP-hard problem in delivering millions of presents across the world in 48 hours.
“Can you imagine the scale of tasks to be solved for the mission to be accomplished successfully? I will single out only some of them,” said Dr Deineko.
“Let’s assume that all the toys are in one giant warehouse, rather than several. One sends a robot to pick up the items from the shelves. Time is not only money but hopes and dreams of millions of children; you have to do it as quick as possible. So, you need to find the fastest path to pick up all the items, remembering that the robots can have a maximum load, so they will have to do this more than once.”
In addition, there could be different rules for picking up items in warehouses. Santa’s warehouse has been divided into two different zones for boys and girls toys, so the robots’ tour has to go between the two. Santa trains the robots to be fair – one bag for a girl, one bag for a boy. So the robot jumps from one side of the warehouse to the other!
“This is known as the bipartite travelling salesman problem,” said Dr Deineko. “It is also known as the shoelace problem. My recent research results are related to a special case of this problem, to the case of very old shoes.
"Mathematically, Santa’s robot problem can be viewed as the shoelace problem: the girls and boys toys on the shelves represent the eyelets of shoes and the objective is to find an optimal shoe lacing strategy that minimizes the length of the shoelace, so optimising the routes for Santa’s robots."
Once the robots have loaded all the items onto Santa’s sleigh, the route has to calculated and programmed into the satellite navigation system. Now we have another TSP.
“The challenge here is that the science cannot for sure advise on the best possible way to solve a problem of this size” said Dr Deineko. “In other words, there is no perfect solution – you can make your operations more and more efficient, but there is no simple algorithm that will solve it, we only have sub-optimal algorithms, that will optimise the route as best we can but are not perfect.
“The TSP was first formulated in 1930 and has still not been solved - I’d like to ask Santa for a solution for my Christmas present!”
Arne Strauss teaches Pricing & Revenue Management and Text Analytics on the MSc Business Analytics, while Vladimir Deineko lectures on Operational Research Modelling on the MSc Business Analytics plus Mathematical Programming and Quantitative Analysing for Management on Warwick Business School's Undergraduate programme.