🔒 Locked

Traveling Santa Problem

Started by cowcow Dec 4, 2018 at 4:47 PM 6 replies 3.5k views

Original Post

Dec 4, 2018 at 4:47 PM

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?

frob

Dec 4, 2018 at 5:56 PM

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.

cowcow

Dec 4, 2018 at 5:58 PM

V-opt eh? Thanks for the advice.

IADaveMark

Dec 6, 2018 at 3:20 AM

One of the most interesting and successful solutions for the NP-Hard Traveling Salesman Problem was done via swarm theory. Basically spawning 1000 "ants" at the start point and having them select their next destination randomly from among those that they haven't visited yet. As each ant reaches the end, they report back along the path they took and adjust the weights of those connections pro or con. They they respawn and do it over again. The result is that as the weights for the paths gradually change, they end up biasing the paths towards the optimal one. They were able to solve a 16 node problem in great time which, using normal methods was a complete bitch to do.

The method you are using by dividing things up geographically is similar to doing a coarse graph and using hierarchical A*.

cowcow

Dec 6, 2018 at 3:06 PM

Yeah, that's very cool!

cowcow

Dec 11, 2018 at 1:41 PM

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...

cowcow

Dec 11, 2018 at 2:48 PM

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

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.