This is my first time writing and optimizing from scratch a Python script that solves a traveling salesman problem (TSP) for the Kaggle Santa 2018 competition.

And this solution brought me my 2nd Kaggle competition GOLD MEDAL! I’m very happy!

The reason why a custom Python solver must be used instead of commercial or open-source solvers such as Concorde, LKH… is that Kaggle inserted a really tricky constraint into the original TSP problem.

What they did is that instead of a traditional TSP problem where we need to find the shortest possible path through 200K cities, but with a constraint that every 10th step is 10% more lengthy unless coming from a prime CityId. (the start city is also appointed)

In a nutshell, “prime” CityId here means nothing but just random fixed cities among a forest of 200K cities. Just this simple constraint invalids all existing open-source or commercial solvers. What we can do best with those solvers is to generate the non-constraint path (indeed we did with LKH3), then further optimize that path with our custom optimizer.

Purple: every 10th cities in the path. Green: prime cities. Total 200K cities (points)



The best thing about this year’s Santa is that the optimal solution was never been found! For most of other Santa competitions on Kaggle, the problem scale is often not this big and not allowing competitors to get creative on their optimization solution, instead with just a race to the known optimal once 2 or 3 teams with the identical score surge on top of the leaderboard.

This year’s Santa was the best Santa (I wrote this line in 2025) that I have ever competed so far!

Please read my solution write-up and code below:

My Kaggle solution write-up
My Kaggle solution code
My full code

The visualization of path traveling