(After this column appeared in the Monitor, a reader pointed out an unspoken assumption: Who says Santa exists only in 3 dimensions? “Free yourself of the constraints imposed by a XYZ-based mindset and posit that Santa exists in 5 dimensions!” he wrote.)
As Santa Claus contemplates whether to invest in a self-driving sleigh startup valued at $17 billion via a SPAC, we’re going to look again at the computational wizardry behind Father Christmas’ globe-trotting jaunt.
I once calculated that Santa’s trip would use 5,000,000,000,000,000 joules of energy, roughly as much energy as contained in one-tenth the annual gasoline consumption of the entire U.S., and that he traveled so fast that the sleigh would have to be led by Rudolph the Red-Shift Reindeer. (Yes, that’s a great joke.)
Back in 2017 I realized the trip required Santa to solve not just the traveling seller problem, one of the most famous of all unsolved mathematical conundrums, but the harder problem of vehicle routing with time windows.
“That’s a whole ‘nother level of complexity,” said Wheeler Ruml, professor of computer science at UNH, when I presented him with this holiday-themed math idea at the time.
(Note: I double-checked with Ruml last week and there have been no mathematical or algorithmic breakthroughs to render this column out of date.)
You may have heard of the traveling seller problem – more commonly called the traveling salesman problem but let’s move with the times. It goes like this: For any given list of places, what is the best order to visit them in order to do the trip in the least time?
The TSP, as the problem is known, has been the subject of much analysis over the years because it has applications in setting almost any type of industrial process. What’s the best order to do things, and how can you be sure that there isn’t a better one? It has also been much studied because it’s interesting, said Ruml.
“One reason it’s such a fascinating family of problems is that even if you prove that certain variants are unsolvable optimally, there are all kinds of openings for creativity in finding practical methods that will do very well, or for studying other variants,” he said. “There’s always another problem.”
When TSP involves a few cities, anybody can figure out the optimal route: It’s obviously better, for example, to go from Concord to Manchester to Nashua than from Concord to Nashua and then back to Manchester.
But if you had to figure out the best route to visit every town in New Hampshire, you’d be stumped. Should you first go north or south? Do you skip towns on the way out and hit them on the way back or do you always cover the closest places first? And is there even such a thing as an optimal route, or are there multiple variations that are equally good?
Now imagine asking those questions to plan a visit to every home of every child who celebrates Christmas, with the further constraint that you have to factor in the pattern of darkness as it moves around the globe.
“Since he knows when we’ve gone to bed and wake up, and when the kids are in their deepest slumber, perhaps he needs to visit each one during that particular time window,” Ruml ruminated.
Those extra constraints turn the straightforward traveling seller problem into vehicle routing with time windows. If Santa has solved that, the world is his oyster. He could even get a prime speaking slot at the next meeting of the American Mathematical Association.
One thing is for certain: Santa hasn’t found a general solution; that is, a method that will always find the best route in any possible TSP scenario. Mathematicians have proven the general solution to be impossible, even for Father Christmas, although it is possible to find optimal routes for specific TSP problems such as the matrix on a near-sphere (i.e., locations all over the Earth).
But there’s another wrinkle to consider, Ruml told me, because mathematicians have also shown that in a reasonable amount of time – technically known as polynomial time – you can always find a good answer to a specific TSP problem even if you can’t find the best one.
“Finding a provably optimal solution to a problem of Santa’s size is beyond our capabilities. But there are families of algorithms called approximation algorithms that will let you get a solution guaranteed to be close to the optimal solution,” said Ruml. “Say, within 20 percent.”
Egad – maybe Santa is cheating! Maybe Santa will feed a couple billion GPS coordinates through approximation algorithms, and his Binary Logarithmic Internet-Tracked Zoomorphic Electronic Numbercruncher (BLITZEN) will print a route that is very, very good even if not perfect.
This idea dismayed me, like discovering that Santa’s belly shakes only like a teaspoon full of jelly, but Ruml said I was overlooking the beauty of a good algorithmic approach.
“People think that computer optimization is somehow a dry field, but in fact there’s enormous creativity and intuition that goes into designing an effective algorithm for some of these complex problems,” he told me.
With a nod to the legendary computer scientist Donald Knuth, Ruml said there is “an aesthetic to algorithms, like composing poetry.”
“Like in a poem, every line contributes to the overall meaning. If even one element were omitted, you would not have as beautiful a structure,” he said.
And you know what? He’s right.
Even if Santa hasn’t actually solved vehicle routing but is using algorithmic approximations, that’s OK. He’s still spreading joy and happiness throughout the world in a miraculous way.
That’s optimal enough for me.