I’ve been messing around with ORtools and GH_CPython and wanted to share two TSP solver implementations:
First one is the standard tsp problem, so it finds the shortest route between all the points. Performance is good: Calculating a route between 1000 points route takes 26s, given that there are 2×10^2564 possible routes, I’ll take it.
Second one is a tool to sort & flip curves to find the shortest route between them. This could be very useful if you want to engrave/ CNC /drawing Robot something and don’t care about reversing some curves. But it is a bit hacky since all I did was to set the distance function for the curves to 0 and multiplied the rest by some large number to force the algorithm to use the curves in the route planning.
Probably there is much room for improvement, ORTools are quite rich but I didn’t look too deep into it. There are options to set different algorithms, time limits, etc… So If you do, please share
You guys are doing it wrong This is an example of 1500 nodes solved in PHP on my home PC I need to do some more verifications before claiming anything, but it looks like it can be solved in n^2, instead of n!. A pain to validate though.
I should fix some issues (eg. point uniqueness - I believe some points might be duplicate and end up being visited twice here). Anyway this is what the currently very rough script does in under a second on my old PC
Also, sorry about “you’re doing it wrong”, had to be a joke letting me crash your party. Which it obviously didn’t sound like. Sorry about that.
The point is I think I had an epiphany on how to solve TSP. Made a quick 30 liner in PHP, seems to do the job as intended.
I got interested in the problem after a millenia prize was announced by Clay Mathematics Institute, back in 2000, yet I’m no scientist. I do deliver leaflets in UK at the moment, have some web technologies background, and just interested in approaching things differently.
So the way I see it, I can share my insights, but you’d have to listen first. And then help me fine tune it. Maybe write a scholar article to initiate a prize claim, or such.
I have no idea how your culture works, don’t judge me for that, please.
sorry about any childish bugs if there are any. Distances you can add to get the total distance around. I would be amazed if you can do better. Or devastated. Bring it on
E2A: Tried your nodes, which seem to be on a 101x101 (don’t think it matters though. Or does it), got a distance of 3868.4323637324. Not too bad for a first try, I’d say Consider it doesn’t take any real computing power.
Have to improve obv. Thank you for that though, got a benchmark at last. Also not sure if I imported your coords correctly, will have to wait for tomorrow though, getting really late here.
I got a bit drunk that night, sorry Here’s my solution to your 1500 nodes, in CSV (x,y\n), takes under a second on dual core given your input to provide a distance of 3868.43236
I would appreciate if you can confirm my results are correct (the points are all the same and the distance is correctly calculated). I’m just using some hand written script, can never be sure
Hi there. So I took a look at or-tools and changed some stuff around. Changed the standard algorithm the OP used to a more advanced one called guided local search (recommended by google for this kind of stuff). It shouldn’t get stuck as often in a local minima. I also added a search time limit (in seconds, default 1) to the python component, 30 seems to do a very good job.
Another thing I did was scaling the distance matrix (also recommended by google) seeing as or-tools only works with integers and rounding by 0.5 when the values are small produces a very big rounding error. Simply multiplied everything by 1000 so 0.5 becomes negligible.
Here’s the file, it also works for points in a 3D space apparently. I haven’t changed anything for the part that works with curves but I will take a look at it as it will definitely come in handy at work. tsp.gh (24.5 KB)
Thanks to the original poster for the file, I couldn’t have done it myself as I’m a beginner in python (or programming in general). Would you be interested in taking a look at a more advanced TSP solver that produces exact solutions and maybe see if you can port that to grasshopper? It is written in C: Concorde Home (uwaterloo.ca)
thank you for sharing! Good work changing the algorithm and especially the addition of the time limit – nice. btw, I did a similar trick by multiplying by a large number since ORtools works better/only with integers (post3)
Like you I only have beginner programming skills and since ORtools did the TSP in reasonable time I didn’t want to invest in learning C and and integrating concorde. TSP comes up so often that is almost strange that there isn’t a component or plugin by now.
On a side note: Can I ask how the curve sorting will come in handy? Just out of interest…
Concorde gives you the exact solution and is blazingly fast, someday I might try to convert it but it’s going to be a long road ahead.
I work with a CNC router, and apart from closed curves (which I easily sort by sorting the starting/end points) I also have open curves which obviously start and end at different points so if I take that into consideration the sorting is more accurate. Optimising is my obsesion at work.
Have you tried graph theory plugins available already? Dachuan’s LeafVein (LeafVein | Food4Rhino) has 2 different algorithms to solve traveling salesman, as I remember default one was pretty fast and was O(n^2).
Thanks , will do some further test with the plugins you’ve mentioned and some different point distributions. Currently leafvein seems to be unavailable in the package-manager though
Just checked these both algorithms that are provided in LeafVein, and here are the results for your set of points:
BUT it is worth to mention, that one set of points is not enough for doing benchmarks for heurstic algorithms, cause they highly depend on an input, so for other sets of points (for other types of graphs) different algorithms will came up with better results
TSP (Dynamic, Heuristic, Genetic, 2-Opt or … er … that Bulgarian freaky thingy) is a challenging problem. The best results with few points? (say up to 1000) the 2-Opt way (not very fast mind, but who cares?). The best with 1Z points? Call NASA
See ~1300 rnd pts VS 2-Opt TSP (seed start route done via classic iterative proximity and Point3dList etc etc),
This is an example of 1500 nodes solved in PHP on my home PC 
btw, I did a similar trick by multiplying by a large number since ORtools works better/only with integers (
