As we all prepare to profit from Santa Claus’ annual globe-trotting jaunt, I’d like to take a moment to acknowledge not just how physically astonishing it is to visit a couple billion homes in one night, but how mathematically astonishing it is to know the order in which to visit.
Not that the physical details are anything to sneeze at, of course.
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. You’re welcome.)
But more recently I realized that in order to complete the trip, Santa would have to solve not just the traveling salesman problem, one of the most famous of all mathematical problems, but the harder problem of vehicle routing with time windows.
“That’s a whole ‘nother level of complexity,” admitted Wheeler Ruml, professor of computer science at UNH, when I presented him with this holiday-themed math idea.
You may have heard of the traveling salesman problem. It goes roughly 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 traveling salesman problem is known, has been the subject of much analysis over the years because it has many practical applications, not just in planning trips but 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, any salesman can figure out the best, or optimal, route: It’s obviously better, for example, to go from Concord to Manchester to Nashua than from Concord to Nashua 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 in, or always cover the closest places first? How in the world can you figure it out – and is there even such a thing as an optimal route, or are there multiple variations which 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 naughty-or-nice-ness, the pattern of darkness as it moves around the globe, wind and weather, and who knows what else.
“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 salesman 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 to the TSP; 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, Ruml added, there’s another wrinkle to consider, 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 before heading out tonight, Santa will feed a couple billion GPS coordinates through approximation algorithms, and his Binary Logarithmic Internet-Tracked Zoomorphic Electronic Numbercruncher (BLITZEN) will print out a route that is good enough even if not perfect.
This idea dismayed me, like discovering that Santa’s belly only shakes 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 Donald Knuth, one of the greatest of computer scientists, Ruml said that 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 as structure,” he said.
And you know what? He’s right.
Even if Santa hasn’t actually solved TSP and 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.
Merry Christmas.
Return to the Concord Monitor