Discussion "Travelling Salesman" Fastest Route Solver

[Makeshift]

Hi guys,


I wasn't sure if this had been done before, a quick search only yielded people saying how difficult it was, so I thought I'd knock up a quick script to solve the "Travelling Salesman" problem.


Simply, you enter a list of systems into the script, and it will calculate the fastest route (in lightyears) from your initial starting point and going through all the stops.


It's pretty quick and dirty, and unfortunately the larger file which includes ALL systems in the universe has a tendency of crashing Chrome due to its size. I'll work on some sort of batch processing. (Note that Microsoft Edge seems to handle it quite well - I just threw the 600mb json file at it plus 50 random systems and it did it in less than 30 seconds! (<<Picture link))


This was thrown together to give me a hand with Sothis runs so I didn't accidentally go the slightly more inefficient route.


https://github.com/Makeshift/EDSalesmanSolver

Future plans for this, if demand allows it, is to put the data into a database to speed up system lookup so I can host it properly on my website, general UI improvements and other fun things. I understand this might be quite niche, but it could be handy for explorers and especially traders.

Cheers guys!

 

[ethelred]

This looks great, how do I point it to systems_populated.json?

I click in the box and that takes me to my file libraries, I have saved systems_populated.json as a file but what next?

thanks in advance

 

[Makeshift]

This looks great, how do I point it to systems_populated.json?

I click in the box and that takes me to my file libraries, I have saved systems_populated.json as a file but what next?

thanks in advance

1) Download the json file to somewhere memorable like your desktop
2) Open up the index.html file you downloaded
3) Click the input to open the selection box, navigate to your desktop and double click on the json file.
4) It might take a few seconds to load, but the index.html page should change to show two input boxes and the rest of the settings

If it doesn't work, what browser are you using?

 

[CMDRApex]

Didn't work in edge for me until I replaced the ** operator with Math.pow, I also added .trim the the split input to allow for lists of systems that have extra whitespace around the commas.

Then I got a route (I tested with Mahon control systems, all 100+), but I'm not convinced that it is optimal.

Still a useful tool, thanks for sharing!

 

[Makeshift]

Didn't work in edge for me until I replaced the ** operator with Math.pow, I also added .trim the the split input to allow for lists of systems that have extra whitespace around the commas.

Then I got a route (I tested with Mahon control systems, all 100+), but I'm not convinced that it is optimal.

Still a useful tool, thanks for sharing!

That's interesting - It worked fine with Edge for me by default, can I ask what version your edge is? And good idea using trim, I forgot that was a function!

Technically speaking it likely isn't optimal - It literally calculates the nearest system to the previous one, so technically it could be up to 30% out from the most optimal (I think? Am I mathing right there?). To get it more precise I'd need the persons jump range, and the calculations would be a LOT more intensive, but I might look into it for fun.

Thanks for the test and suggestions though! I appreciate it

 

[CMDRApex]

Edge version 25.10586.0.0
EdgeHTML version 13.10586

Travelling Salesman is a very well researched area of computer science, might be worth seeing if you can find any useful literature.

 

[Toumal]

Two things:

1) Read up on A* and Dijkstra.
2) Use estimates for the node distance (avoid squareroot and other expensive operations) to speed up the whole thing even more.


This way you can improve your code's performance by at least an order of magnitude.

And as CMDRApex said, pathfinding is a well researched subject and I strongly suggest reading the available literature before inventing anything yourself


EDIT: I learned this the hard way, when I wrote the pathfinding for the Tribes 1 bot "Spoonbot". It took seconds to calculate a path, until someone showed me the error of my ways and introduced me to various algorithms. Needless to say, navigating a waypoint mesh of several hundred points turned into an affair of a few milliseconds.

 

[CMDRApex]

I made some tweaks.

The biggest jump came from sanitising the JSON so that it only contains name and coordinates, which makes me think the biggest obstacle to performance was cache misses on a large dataset rather than expensive ops in the main loop.

I even made a pull request [big grin]