The question is, "How fast does Santa have to go to visit all those homes?" We're not going to assume he has to go down chimneys or anything like that; he just has to get to all of the homes. But assuming that Santa is real, he is still subject to the laws of physics. No getting around those.
For small numbers of capitals, this problem is trivial. Consider three cities: Sacramento CA, Carson City NV, and Phoenix AZ. The air distances between these cities are S-C = 160 km, C-P = 930 km, and P-S = 1016 km (I got these figures from the City Distance Calculator at http://www.geobytes.com/citydistance.htm). The sales rep, in order to minimize the total travel distance, should avoid the long Phoenix-to-Sacramento leg, and visit the cities in the order Sacramento, Carson City, Phoenix (or the reverse).
Adding a fourth city does complicate matters somewhat. The cost of adding one city is three new distances. If we add, say, Boise ID, the new distances are S-B = 712 km, C-B = 580 km, and P-B = 1179 km. And instead of only three essentially different routes, there are now twelve: B-C-P-S, B-C-S-P, B-P-C-S, B-P-S-C, B-S-C-P, B-S-P-C, C-B-P-S, C-B-S-P, C-P-B-S, C-S-B-P, P-B-C-S, and P-C-B-S. (There are twelve other orders, for a total of 4! = 24, but the other twelve are the reverse of those already listed, and are the same for the purpose of total distance.) By exhaustive calculation, we find that the minimal path is B-S-C-P (or P-C-S-B), with a total length of 712+160+580 = 1452 km.
One thing that becomes quickly apparent about this problem is that you can't solve it just by picking the three shortest distances, because those three distances may not connect all of the cities, or do so in a path. Instead, in this case at least, we had to try all the different routes and pick the shortest overall route. In fact, the Travelling Salesman Problem is a so-called NP-hard problem; this ties it with a number of other problems whose solution times are all expected to increase exponentially with the size of the problem, barring some unexpected theoretical advance.
In the case of the Travelling Santa Problem, however, we are not interested in knowing how Santa knows what order to visit the homes, or even what order he actually visits the homes. We just need to know, to a rough order of magnitude, how far he must travel to visit every home.
Let us consider that the current population of the Earth is about seven billion. How many homes is that (if by home we mean any single living unit)? There are some homes with lots of people in them, living as a unit; on the other hand, there many homes with only one person in them. We probably would not be too far off if we assume an average of two people per home. That would mean 3.5 billion homes to visit.
Now, if these 3.5 billion homes were evenly distributed across the surface of the Earth, which has a surface area of about 510 million square kilometers, each home would have to itself an average of about 0.15 square kilometers, which means the mean home-to-home distance would be about 0.4 km, and Santa would have to travel about 3.5 billion times 0.4 km, or about 1.4 billion km. If we assume that Santa has to travel all that way in a single day (86,400 seconds), that means he must travel about 16,000 km/s, a little over a twentieth of the speed of light. So, very fast (about 35 million mph), but at least doable in principle.
In truth, it's a bit better than that. In the first place, most of the Earth's surface is water; only about 30 percent of it is land. Of that, the polar lands, especially around Antarctica, are not readily habitable in the usual way, so that perhaps only about 25 percent of the Earth's surface has any appreciable habitation. That cuts the total distance in half to about 700 million km, and the necessary speed to 8,000 km/s.
Even better, human homes are not evenly distributed across the 25 percent of the Earth's surface they cover, but are clumped together in towns, villages, and cities large and small. We might consider a clump to be any collection of homes that are within 100 meters of at least one other home. This means, among other things, that a single isolated home is considered to be a clump.
Of course, 100 meters is just the maximum cutoff distance between homes in a clump. The average distance would be rather smaller. In a major city like New York, for instance, the average distance is probably closer to 10 meters; in other areas, the average might be smaller than that. In that case, the total clump internal distance for 350 homes would be more like 3 or 4 km, for a total distance of 100 million km, with a required speed of about 1,200 km/s.
Finally, statistical studies show that if N clumps are randomly distributed over an area of about A = 130 million square kilometers (as we've assumed here), the unevenness caused by that random distribution creates some clumping in the clumps, so that the total clump-to-clump travel distance is given approximately by √(NA/2) = √(650 million million square kilometers) = 25 million km, lowering the total distance to 60 million km, and the speed to 700 km/s.
That's still about 1.6 million mph—fast enough to go around the Earth in a single minute—so perhaps Rudolph better get going.
