I am trying to find a solution for the Kaggle Traveling Santa 2018 - Prime Paths contest (https://www.kaggle.com/c/traveling-santa-2018-prime-paths).

Once my code is complete, it will become public domain, for anyone to use in the contest. I'm not in it for the money.

I have tried several simple algorithms (including brute force), but they're not suitable for large numbers of cities (the Kaggle contest consists of ~200,000 cities). The next algorithm that I'm going to try will divide the cities up into countries, provinces, and counties. If I have 25 countries, 25 provinces per country, and 25 counties per province, then it works out to be roughly 13 or so cities per county. This way the maximum path segment is 25 vertices long. One can then just use one of the simpler algorithms (but not brute force), if they like, because the problem has been divided into simple chunks.

Does anyone have any experience with the Traveling Salesman Problem? Care to share the algorithm that you used?

TSP is well researched.

What you described with simplifying the mesh into small groups and solving those seems similar to the V-opt variations, where you solve the sub-problem of a cluster and then link the clusters. Not necessarily optimal, but often good enough and much faster than an NP-Complete brute force.

The few times I've needed to write solutions I went with greedy algorithms. They path is not ideal, but substantially easier to compute and generally good enough in the context of games.

V-opt eh? Thanks for the advice.

Yeah, that's very cool!

I have implemented countries and provinces, but I'm having a little bit of trouble with the municipalities: I have the municipal capitols working, but splitting the cities into municipalities seems to be problematic.

I am not certain that line 137 is correct (https://github.com/sjhalayka/hamiltonian_cycle_3/blob/3f765ad83e8e52634d4947272d72396ed5cd2bc9/hcycle.cpp#L137).

Same with line 238 (https://github.com/sjhalayka/hamiltonian_cycle_3/blob/3f765ad83e8e52634d4947272d72396ed5cd2bc9/hcycle.cpp#L238).

Can anyone please help? Once I have this final step done, I will be able to make a normalized database that I can use to recursively find a solution to the TSP, with GA perhaps. I'm not worried about fixing it right away, since I'm not in it for the money.

Not really sure why it's so difficult for me...

So I "solved" the problem by simply removing the municipality layer, and divide the cycle up into countries and provinces. Done.