# How to calculate most efficient route passing through all the houses in the world?

I'm new to GIS.

I need some help in determining the best or most efficient route, using a flying sleigh, through all the houses in the world. One of my coworkers told me that this site would be the best place to ask, because I would find lots of helpful GIS experts.

I will need some guidance about what software to use, where to get the data, and how to process it. Since I had some extra expenses this month, I would prefer some Open Source solutions.

Thank you all!

PS: I'm in a bit of a hurry, as I need this for tomorrow!

• This is basically Travelling Salesman Problem which unless you're willing to use a heuristic has n! complexity so good luck finding any solution for that many n before the universe ends... Dec 23 '12 at 21:33
• Wait, since when do only Christian kids get Santa visits? Dec 24 '12 at 0:10
• Let us just assume that Mr. Claus has a list of housesholds to visit and keep it non-denominational. Thanks :) Dec 24 '12 at 2:41
• Is this route also constrained to start at the North pole? North geographic pole, or north magnetic pole? Dec 24 '12 at 8:49
• So. First step is to gather a dataset for all dwelling locations for the World. Anyone care to post a dropbox link?
– jakc
Dec 24 '12 at 14:11

Hang on surely Rudolph knows where to go. He's been doing it for years.

Often it is good to address the need that is stated rather than answering the question that was asked. I would like only to point out that there is a well-known parallel solution that neatly circumvents all the technical computing issues: Santa has helpers. These agents work asynchronously and independently to identify the houses that need visits and carry out the deliveries. No special GIS computation on Santa's part is needed.

It is wonderful that this technology scales, so that as the world's (Christian) population has expanded by several orders of magnitude over the millennia, Santa's ability to carry out his duties has never seriously been in doubt: the number of available helpers has grown in direct proportion to the number of houses that need visits.

There is a physical demonstration of the existence of these helpers. If, to assume the contrary, just one individual tried to deliver gifts to, say, one billion dwellings throughout the course of a calendar day (which spans 48 hours, accounting for time zones), they would have to visit almost 6000 dwellings per second. A lower bound for the mean distance between dwellings is afforded by the density of the world's larger cities, in which people may live only 10 meters or so apart. This would require an average speed of 6000 * 10 = 60,000 meters per second, far surpassing the sound barrier (creating sonic booms that are not heard on Christmas) and creating so much atmospheric friction that the sleigh would become a blazing fireball destroying everything in its proximity. Although this gives us a new understanding of the origin of the red glow in Rudolph's nose, it clearly demonstrates that only a parallel solution is even possible, QED.

This is something you can probably solve by using the Warshal's or Dijkstra's algorithm

Although the number of houses in the world is way too big it would take a long time to compute that, I think this is a good initial point. Now I don't have the time to explain them but i give you an initial point. I'll go out with my family now and maybe I'll go back to this question the next year.

• Thank you for the kind words. But: (1) How would either of those algorithms solve this traveling salesman problem? (2) Dijkstra's algorithm (to find shortest paths between two given points in a given network) is fast. Applying it to a dataset of all dwellings in the world, if it were suitably pruned to include edges only to several nearest neighbors of each dwelling, would not only be feasible, but reasonably quick--probably needing only seconds or minutes of computation. Dec 24 '12 at 17:43

Looks like Google figured it out for you already, Santa! In fact, you're supposed to be in Asia at the moment!