The Travelling Santa Problem

Planning Santa’s annual trip is a hard nut to crack. He is faced with a pretty big logistical problem. He needs to work out the shortest route to take in a very tight timeframe, making sure that every child (those who have been good, of course) gets their presents before waking.

It’s just as well Santa is good at storing information, because he needs to know which houses to visit, their exact locations, and the distance and time between each one. With two billion children, this amounts to quintillions of pieces of data.

If Santa were visiting only four children, there would be 24 possible routes (4 choices for the first visit, times 3 choices for the second, times 2 choices for the third, times 1 choice for the final delivery). But now comes the really difficult part...

For Santa, the number of possible routes amounts to two billion multiplied by two billion minus one, multiplied by two billion minus two, and so on until we reach one. This number is so huge it’s hard to imagine. It exceeds the number of atoms in the universe. This doesn’t faze Santa though, even though he also needs to factor in different time zones around the world, the times when each child will wake, and any breaks to ensure the health and welfare of his reindeer.

Fanciful? Perhaps. But “the travelling salesman problem” is a real conundrum which, if addressed properly, can reduce transport distances and costs. It is a mathematical problem with real applications in vehicle scheduling software. Just replace Santa’s sleigh with a delivery vehicle, the reindeer with the drivers, the children with the customers and the waking times with promised delivery times. It is so computationally demanding that even the most sophisticated algorithms can only get close to the optimal route, but they can improve substantially on human judgement alone.

A related transportation problem is to identify the best hub from which deliveries are to be made. Although his exact whereabouts remain mysterious, we are led to believe Santa has a permanent base in the Arctic Circle. From a transport planning perspective, this is like locating a central UK depot in the Outer Hebrides. Santa could perhaps benefit from some advice on the Facility Location Problem. In its basic form, this problem is to locate the hub where its total distances from customers is minimised. It is usually assumed vehicles return to a central hub, but more challenging versions have emerged recently with the introduction of car-sharing schemes. These schemes rely on multiple hubs, with vehicles returning to different hubs from their origin.

For Santa, the challenge is to find routes that allow him to deliver all his presents on time. To advise him on the best (optimal) solution which achieves this aim would depend on his objective function. For us, the objective may be to minimise the total distance travelled or to minimise fuel emissions, which are not necessarily the same.

The common thread is one of optimisation. Optimisation problems lead to two challenges. The first is the technical challenge of identifying the optimal (or near-optimal) solution from the plethora of options available. The second is the challenge of deciding on the objective in the first place. This is a political and societal issue. Its resolution can be aided by sophisticated models, but ultimately lies beyond them.

Does Santa realise there are a wide variety of models to help him plan his logistical operations? I’m not sure, but I am confident that planners lacking Santa’s magical powers could benefit from adopting these models as their “little helpers”.

Professor John Boylan is the Director of the Centre for Marketing Analytics and Forecasting in LUMS.