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. :upside_down_face:
tsp3

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

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 :wink:

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


tsp.gh (20.8 KB)

5 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 :slight_smile: This is an example of 1500 nodes solved in PHP on my home PC :slight_smile: 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, :wink: 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 :slight_smile:

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

You did it, man! P = NP :exploding_head: :partying_face:
In all seriousness seems to be a smart way to do it,but can it be validated? Just implement a solver like concorde or or tools and run them on the same data, if gives the same route / or a route with (near) same length, you have something.

Or you could share your cities, I’ll could run it in Or tools and we’ll see if the route is the same.

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 :slight_smile:

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 :slight_smile: 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 :slight_smile: 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 :slight_smile:

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! :slight_smile: What are you guys up to? Is this a competition? Speed or distance?