The Traveling Santa Problem

I've participated in the "Traveling Santa Problem"-contest over at Kaggle, and the goal of that contest was closely connected to the Traveling Salesman Problem (TSP). The idea behind the TSP is to help a salesman to find the shortest route through a number of cities, and the salesman can only visit each city once. You can use the solutions to the TSP in real-life as well, often connected to different logistics-areas, but also when manufacturing circuit boards.

This is a plot showing the 150,000 different cities (or chimneys in this case):

The easiest way to find a solution is to begin at one random point, and then find the closest point to that random point with the help of Euclidean distance. This is the plot when using that method, using only 5000 chimneys:

As you can see in the plot above, the method using the least distance will miss some points, and in the end, Santa will have to travel back to chimneys very close to chimneys that he has already visited. To solve this problem, you can use an Hilbert curve combined with the least distance method. An Hilbert curve will "snake" its way through all the chimneys, and at each Hilbert-point you can calculate the shortest path through that box. The plot will then look like this using all of the 150,000 chimneys:

It took about 30 minutes to generate this path and the distance traveled was 7,646,647. A random solution would generate a distance of 1,290,678,097. I then tried a Simulated Annealing algorithm to improve the path without much success. The problem is that we have 150,000 chimneys and it takes too long time to generate a better solution.

If you are interested in the Python-code used, you can find it here: github