As we all know, Santa Claus has to visit every (good) little girl and boy all in one night. Fortunately, due to the time zones, he has about 24 hours to do so. Now the earth is about 25,000 miles around, so he could zip around the earth in that distance (as an aside, I just traveled from the US east to Singapore, then returned in a westerly direction, which is not quite 25,000 miles but is close), but that wouldn’t let him visit very much. How much farther does he have to travel to see everyone?
Bill Cook and his coauthors at Georgia Tech have a traveling salesman tour instance that consists of 1,904,711populated sites. Finding good TSP tours of this is definitely a non-trivial task, but people have been working at it:
The best reported tour for the World TSP was found by by Keld Helsgaun using a variant of his LKH heuristic algorithm. His tour of length 7,515,947,511 was found on November 27, 2008. Previous best known tours were of length 7,517,285,610 also by Helsgaun (September 16, 2003) and of length 7,518,425,642 by Hung Dinh Nguyen, Ikuo Yoshihara, Kunihito Yamamori, and Moritoshi Yasunaga (June 2, 2003), using a combination of iterated Lin-Kernighan and a parallel hybrid genetic algorithm.
The distances given are in meters, so the best tour is now at 4,670,193.27 miles. This tour is not (necessarily) optimal, so perhaps Santa knows a better tour of these points, but the lower bound is currently 7,512,218,268 meters (or 4,667,876.02 miles), so he can’t improve much. I was surprised that Santa had to do the equivalent of going around the world at least 187 times or so, but that’s what it takes to visit all those points. Santa’s tour is further restricted since he has to worry about time zones: it wouldn’t do for him to arrive at a town before the kids are asleep.
So those nine (or ten, if you count Olive, the Other Reindeer) reindeers move along at about 195,000 miles/hour (at least: you might want to add time for the dropping off of presents, eating cookies, drinking milk, and so on). They really move!
Since the 2 million-odd locations include Antarctic research bases, large industrial installations (such as oil-fields), maybe military installations, and possibly even juvenile-free retirement communities, 195,000 mph may be an over-estimate.
Anyway, given the sled’s large cross-section (recall that drag rises the square of the velocity) and non-streamlined design, it is doubtful that a serial approach accounts for Santa’s stunningly efficient fulfillment system.
There is growing unanimity in the supply chain community that Santa’s R&D shop has combined parallelism with advances in AI (agent-based systems), biotechnology (cloning), and metallurgy (likely exploiting a publicly unavailable USDOD-developed titanium alloy, further blurring the line between Church and State).
All that we know for sure is that when the case is published in HBR, the role of OR will be elided and credit will be given to Predictive Analytics.
Poor Santa! No wonder he needs the rest of the year to relax.
Best wishes for 2009 to you and your family!
The computing challenges are of similar scale, too: http://www.hpcwire.com/features/Santas-HPC-Woes-36399314.html.