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!