I have 3000 systems in a 700ly radius, I want to plot roughly the best route.

[CMDR CaptainScrotium]

3000 systems in a 700 ly radius and I want to find the route with roughly the fewest jumps.

Is there a tool which can roughly solve this very large travelling salesmen problem?

Multi-Waypoint-Planner - Elite Dangerous — CMDRs ToolBox

Plot your route through multiple way-points and let our algorithm find the fastest route for you

cmdrs-toolbox.com

^This tool simply cannot handle such a large number of systems, is there an offline downloadable tool for doing this or a method for calculating the best route?

Thank you.

 

[forbiddenlake]

EDTS in nearest-neighbour solve mode.

Best used if EDSM already has the coordinates of all the systems you want to visit. But still possible to use if you get the coordinates yourself and insert them in to the database.

 

[goemon]

spansh tourist router can also import textfiles with system names ... personally never tested with 700 systems though.

 

[varonica]

3,000 systems is 3,000 factorial, the number of possible routes is 3,000 x 2,999 x 2998 ......etc, which comes out to many times more than the number of atoms in the universe, there will be approximation and algorithms that can give you a rough ides, but generally if you get closer than 50% efficiency that's considered a good number. You are better off breaking it down into a large number of smaller areas with say 100 systems in each then doing each section by itself, that would be managable.

 

[FullMetalDad]

So because I have a spreadsheet with >10k systems in the bubble (~500 LY diameter) w/ coordinates laying around, and no life, and who doesn't like a good traveling salesman problem, I tested this out.

(3000 systems in Bubble axes in LY - shrink factor just fits a convex hull to the points to see roughly the shape)

Excel can do a TSP with about 200 "cities" using it's built-in Evolutionary solver (genetic algorithm) and no special programing (no VBA). You'd have to chunk up the 3000 systems, which can be done pretty easily with k-means clustering (this can also be done in Excel). However, it's easier to do in Python or Matlab. I ran the full 3000 systems in Matlab using a genetic algorithm for the m-TSP ("m" salesmen or separate routes). Hueristic/genetic algorithms can really only handle <1000 cities reasonably well. However, for 3000 systems I got the travel distance from a "nominal" (i.e., completely random) 533,882 LY to a "best" single tour of 71,508.2 LY before failing to converge (max iterations) - roughly the distance form Sol to Beagle Point - took couple hours. I also ran it with a max of 10 routes and it only reached 97,631 LY travel distance, again failing to converge on iterations (and not counting travel from one tour to the next) - took couple hours. I think it would be better to divide the problem into say 10 k-means clustered regions and run the TSP on those individually (as suggested above).

(10 K-means clusters with centroids)

I did this for 10 k-means clusters for 10 individual routes totaling 54604.1 LY, again not including travel between routes - maybe half an hour. Note that as the clusters happen to meet close to the center and the classic TSP problem has the route finish where the salesman started, one could choose a point in the center that was close to all of the routes and start at the closest system along each route (as they are individual loops) and end up close to the next route.

(1 of 10 routes calculated)

I just was curious in the scope of such an endeavor: 55 kLY is still a haul but better than 530 kLY. FWIW

Edit: Multiple Depot Multiple Traveling Salesmen Problem solved by Genetic Algorithm Matlab subroutine used (for completeness)

 

[Darrack]

So because I have a spreadsheet with >10k systems in the bubble (~500 LY diameter) w/ coordinates laying around, and no life, and who doesn't like a good traveling salesman problem, I tested this out.
View attachment 319652
(3000 systems in Bubble axes in LY - shrink factor just fits a convex hull to the points to see roughly the shape)

Excel can do a TSP with about 200 "cities" using it's built-in Evolutionary solver (genetic algorithm) and no special programing (no VBA). You'd have to chunk up the 3000 systems, which can be done pretty easily with k-means clustering (this can also be done in Excel). However, it's easier to do in Python or Matlab. I ran the full 3000 systems in Matlab using a genetic algorithm for the m-TSP ("m" salesmen or separate routes). Hueristic/genetic algorithms can really only handle <1000 cities reasonably well. However, for 3000 systems I got the travel distance from a "nominal" (i.e., completely random) 533,882 LY to a "best" single tour of 71,508.2 LY before failing to converge (max iterations) - roughly the distance form Sol to Beagle Point - took couple hours. I also ran it with a max of 10 routes and it only reached 97,631 LY travel distance, again failing to converge on iterations (and not counting travel from one tour to the next) - took couple hours. I think it would be better to divide the problem into say 10 k-means clustered regions and run the TSP on those individually (as suggested above).
View attachment 319653
(10 K-means clusters with centroids)

I did this for 10 k-means clusters for 10 individual routes totaling 54604.1 LY, again not including travel between routes - maybe half an hour. Note that as the clusters happen to meet close to the center and the classic TSP problem has the route finish where the salesman started, one could choose a point in the center that was close to all of the routes and start at the closest system along each route (as they are individual loops) and end up close to the next route.
View attachment 319654
(1 of 10 routes calculated)

I just was curious in the scope of such an endeavor: 55 kLY is still a haul but better than 530 kLY. FWIW

I think NASA need you to fix rocket Number 3

O7

 

[MattG]

3000 systems in a 700 ly radius and I want to find the route with roughly the fewest jumps.

Is there a tool which can roughly solve this very large travelling salesmen problem?

Multi-Waypoint-Planner - Elite Dangerous — CMDRs ToolBox

Plot your route through multiple way-points and let our algorithm find the fastest route for you

cmdrs-toolbox.com

^This tool simply cannot handle such a large number of systems, is there an offline downloadable tool for doing this or a method for calculating the best route?

Thank you.

EDJP can give you a good approximation to "solving" TSPs.

If you've never used it before, you'll need to let it process your journals. Once it's done, hit "Make Route". Select the filename to output, and select the option "Import From Clipboard". You'll need to copy your 3000 systems onto clipboard in format name,x,y,z. They can be tab or comma delimited, so you can copy straight from Excel etc. Hit Process and it'll tell you how many systems it successfully imported - hopefully 3000.

Then, hit Optimize Route. Select the route file you just created and select the system you'll start from. You can optionally set an end system but it's not required. You can also set your ship jump range to slightly tweak the calculations - if you can jump 60 LY, then a jump of 59LY or 3 LY are still both 1 jump. If doing this, you'll need to set the Star Density too - for the bubble, "Fair" is probably best. Hit Optimize and it'll do it's thing. On my PC (which is over 10 years old now), it took ~4 mins to finish for 3000 sample systems.

After that, you could use EDJP to follow the route ("Follow Route"), and it'll automatically put next system in clipboard once you arrive at current waypoint. Otherwise, you'll need to proces the output JSON yourself - but it's a pretty trivial format.

 

[FullMetalDad]

EDJP can give you a good approximation to "solving" TSPs.

If you've never used it before, you'll need to let it process your journals. Once it's done, hit "Make Route". Select the filename to output, and select the option "Import From Clipboard". You'll need to copy your 3000 systems onto clipboard in format name,x,y,z. They can be tab or comma delimited, so you can copy straight from Excel etc. Hit Process and it'll tell you how many systems it successfully imported - hopefully 3000.

Then, hit Optimize Route. Select the route file you just created and select the system you'll start from. You can optionally set an end system but it's not required. You can also set your ship jump range to slightly tweak the calculations - if you can jump 60 LY, then a jump of 59LY or 3 LY are still both 1 jump. If doing this, you'll need to set the Star Density too - for the bubble, "Fair" is probably best. Hit Optimize and it'll do it's thing. On my PC (which is over 10 years old now), it took ~4 mins to finish for 3000 sample systems.

After that, you could use EDJP to follow the route ("Follow Route"), and it'll automatically put next system in clipboard once you arrive at current waypoint. Otherwise, you'll need to proces the output JSON yourself - but it's a pretty trivial format.

Nice app! For science, I tested EDJP against my 3000 systems: took maybe 5-10 min on my 10+ year old desktop (fast!). It said the optimized route was ~48kLy (I believe - I don't think it stored it). I calculated the route to be 61185.4 LY 47452.8 LY after I processed the JSON file. Not sure about the discrepancy as I uploaded the coordinates via the clipboard, but very Very fast, better than my genetic algorithm, and made for Elite Dangerous.

Edit: I found my error. Re-associating the ID numbers with system names from JSON I had some duplicates due to partial matches in the names (I checked this after running my algorithms to make sure all systems were visited, but didn't think about it till after I went to bed last night). The correct route calculation is 47452.8 LY, which is what EDJP reported and extremely efficient for a single TSP.