This is a busy time of year for Santa and he could probably use some help from elves with Operations Research experience. Probably the most well-known application of OR at the North Pole is modeling Santa’s route as a Traveling Salesman problem. After all, Santa must start at the North Pole, visit each and every home exactly once, and return to the North Pole at the end of the evening. Santa’s TSP is actually an application of the World TSP: a TSP problem featuring 1,904,711 cities around the world created as a large-scale test for TSP algorithms. Some discussion of Santa’s route and the World TSP include:

- How far does Santa travel? –
*Michael Trick’s Operations Research Blog* - Santa Claus – A Traveling Salesman Problem –
*A Random Forest*blog

But Santa’s OR needs go beyond routing his flight path. Long before he starts his journey around the world, he needs a mind-boggling amount of toys for all the good girls and boys. Of course he has elves to make all these toys, but there are a limited number of elves available for toy making. And there is also a limited amount of supplies to use to make the toys. Santa’s elves and their toy factory have a classic resource allocation or product mix problem on their hands. They need to decide how many of each toy to make and which toys each elf will be making.

First, the elves need to determine the popular toys this Christmas and the forecasted demand for each toy. They can do this with help from all the letters Santa has been receiving from children around the world. Once the elves have target toy levels, they need to consider the supplies required to build each toy and the total amount of supplies available. They should try to maximize the total number of toys built given the supply constraints while not exceeding the max forecasted level for a given toy.

At this point the elves know how many of each toy to make to meet their forecasted demand and best utilize their limited supplies. But which toys should each elf make? Jingle the Elf may be able to make dolls twice as fast as he can make robots. And maybe Jangle the Elf can make five toy trucks in the time it takes her to make one toy train. The elves can model this as an unrelated parallel machine scheduling problem. And since it might be faster to make the same toy over and over rather than switch back and forth between different toys, the toys can be modeled with sequence-dependent setup times.

Santa’s elves don’t have to stop there. They can use a nutrition problem to determine the optimal diet to feed the reindeer in preparation for their trip around the world. And how about a regression analysis to determine risk factors for children who are ultimately declared naughty? The elves could use this to improve their demand forecast, discounting the requests of potentially naughty children. With all the possible applications of OR at the North Pole, let’s hope Santa has a few operation researchers around.

*This blog post is a contribution to INFORMS’ monthly blog challenge. INFORMS will summarize the participating blogs at the end of the month.*

Does Santa fit all the toys in one big (five-dimensional?) sack, or does he use multiple sacks? Might be a bin packing problem in there. Also, since portions of that optimized reindeer diet are going to make their way through the reindeer and out the other end, you might want to include some, um, pit stops in the routing problem.

Good suggestions Paul. Maybe we’ll see a listing soon on INFORMS’ Job Placement Service for an OR position at the North Pole.