# Traveling salesman problem with ORtools & CPython for Points and Curves

Hi,

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

To use you’ll have to install Python, OR tools and GH_CPython

tsp.gh (20.8 KB)

8 Likes

Nice work, Konrad. If you’re interested you can check out my implementation using IronPython only and a genetic algorithm here:

1 Like

quick note: converting to integer OR-tools runs about twice as fast, this was for 1200 cities

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.

Hey Tjankus,

welcome to forums first of all, most of the time this is a very open and friendly place on the internet, a lot of knowledgeable people and awesome developers.

Your work on TSP seems very interesting!
I think for many applications handling huge number of points is a big plus and taking a hit in absolute efficiency is mostly not a problem. Currently I am working with design students and an industrial robot. Right now we testing “painting” with the robot, so naturally the question comes up, what is the best route between all brushstrokes

I would like to help you with your question but I think I am not the right guy, since I am not that technical after all. Maybe open up another thread and ask for specific help - probably this is more fruitful

btw: I found this a while ago, they seem to have an efficient algorithm as well

Well your right, coming to the same route proves nothing no matter how many nodes. But coming to a longer route would prove it’s not working

edit: Maybe I misread your post; give me 1500 cities and we’ll go from there

give me an hour.

EDIT: cannot reply anymore today, so here it is:

I’ll see what I can do with your coordinates. Here’s one of mine

1500 on a 800x800 grid (originally posted as 400x400, my mistake).

1500nodes_original.txt (181.6 KB) 1500nodes.txt (201.5 KB)

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.

Here it is. (0,0) must be left top here:

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.

cities: cities.txt (18.8 KB)
route: route.txt (7.7 KB)
route length: 3645.23739

1 Like

@tjankus could you send me the data in a different form, it’s not so easy to get it (php? json? ) into grasshopper - or its just me. Either way csv or just a plain text file with the coordinates would be helpful. thanks

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

1500nodes.txt (8.5 KB)

PS. the nodes I used, were just randomly generated, nothing of interest I believe. I’ll keep yours for a benchmark.

This is a weird discussion! What are you guys up to? Is this a competition? Speed or distance?

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)

There’s also a python wrapper around it but it might have some issues running on windows:
GitHub - jvkersch/pyconcorde: Python wrapper around the Concorde TSP solver

2 Likes

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…

1 Like

Oops, didn’t notice the 3rd post, my bad.

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.

1 Like

I recently had another go at this. Here is a comparison between 4 different options:

ORtools gives the best result (100% reference) but I tested other tools as well: In this example bubalus and fennec seem to use the same algorithm, achieving 84%

Spiralizing the shape seems to be a good way, too. `Offset-curves` has its difficulties with non-convex shapes and the route is not as efficient (77%); A refined version uses clipper so non-convex is not a problem and the route is pretty good (87% !)

As a comparison just sorting by XYZ gives 20% or in other words takes 5 times as long.

Maybe we get a nice plugin-less version with high efficiency someday… @tjankus

tsp.gh (164.0 KB)

1 Like

Nice, I’ll take a look at this when I have the time, thank you!

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

Here is a good article about different heuristic algorithms for this problem: 11 Animated Algorithms for the Traveling Salesman Problem

Haven’t implemented any of these algorithms for my Megarachne | Food4Rhino yet, but it looks doable.

1 Like

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

1 Like