Santa Claus’s Nested Traveling Salesman Problem

My children are eagerly watching Santa on the Norad Santa Tracker, which makes me feel good about the use of my tax dollars and Strategic Command’s ability to focus on the real threats to national security (now if they could just manage to hit the fat bastard and bring him down). But it also got me to thinking about Santa’s traveling salesman problem, and I realized that the poor old guy actually has a double-tsp, a nested tsp.

For those unfamiliar with it, the traveling salesman problem is one of the most difficult problems in computational mathematics. Every mathematical approach is far above my head, but fortunately the problem can be stated simply. Given some set of destinations to which one must travel, what is the route that will result in the shortest distance travelled? Basically it’s a logistics problem, and I spent some time in graduate school pondering it because for a few months one of my odd jobs was collecting money from newspaper boxes. I collected from approximately 100 boxs across the city of Eugene. While some possible routes were obviously inferior (hit one on the east side of town, one on the west, then back to the east, etc.), there were a sizable number of routes that weren’t obviously better or worse than each other (and while I can often remember to set my odometer, I can never remember to check it at the end).

Now imagine Santa’s problem. He must go to tens of thousands of municipalities around the world, and we can presume that efficiency matters, since he has to do it in one night (and I would assume an inefficient path would wear out the reindeer long before the night is over). But not only does he have to figure out the most efficient route among all these cities, but within each one of those tens of thousands of municipalities he faces a brand new traveling salesman problem, that in large cities will actually be larger than the initial one (Chicago, for example, has over 1 million households).

It would be comforting to think that Santa has simply managed to solve the problem over time–after all, he’s quite ancient. But his problem changes annually, not just because cities keep evolving, but because the naughty and nice list changes annually (I’m on it roughly once every 4 years).

There’s simply no way Santa can do it on his own, and I suspect this is where Norad’s Santa tracker came into being. As Christianity spread around the globe, Santa’s problem grew exponentially, and as cities grew in population it grew exponentially yet again. Finally overwhelmed, with his reindeer threatening to refuse to go out unless he managed to reduce their flight time, he turned to Norad’s supercomputers to help him solve the problem. The track we’re allowed to view online is just Norad’s computers keeping track of Santa, both to keep him on track, and so that they can go back and check the effectiveness of their brute force solution to his problems.

Remember that peace bonus we were promised from the end of the Cold War? There is it, and you can watch it live. Just be sure to go to be before he gets to your town.