travelling salesman

[ghyman]

I have written a routine for optimizing a 'bunch' of hole locations (tested up to 200)... that is, finding the shortest path to connect them in a 'loop' (start point and end point are close together), or linearly (start point and end point are wherever makes the shortest path).

Currently on a 500MHz Pentium, it takes about 2 minutes for the routine to run 200 holes.

My routine is based on the 'cutting plane method' of solving the 'travelling salesman problem', detailed at http://www.tsp.gatech.edu/

I am wanting to incorporate this routine into a part-program editor I am working on, and am curious to know if anyone knows if the cutting-plane method is the fastest... accuracy is 49% of the desired solution for me, speed is 51%.

Actually, this is not something I had originally intended on writing as a functional routine... it was more of a "gee, I wonder if I can do this?" project. So I am asking more for a "want to know" than a "need to know" reason.

Thanks!

[Neil_J]

Did you ever get it to work? I am working on modifiying a ULP script for my circuit board program to optimize the order of drilled holes....

I'd definately be interested in seeing the source if it's available.


-Neil

[Ken_Shea]

You guys spend too much time on optimizing code, do as Microsoft does, just depend on faster CPU's

[Neil_J]

You guys spend too much time on optimizing code, do as Microsoft does, just depend on faster CPU's

The holes need to be optimized because of my mill's feedrate, not my CPU... When you are cutting thousands of holes, yes, every bit of optimization helps!!

[ViperTX]

1000 holes at a 1 millisecond improvement equates to a 1 sec improvement in cycle time....heck it takes you longer then that to load the stock for drilling....that is where you should be optimizing.

[Neil_J]

Originally Posted by ViperTX 1000 holes at a 1 millisecond improvement equates to a 1 sec improvement in cycle time....heck it takes you longer then that to load the stock for drilling....that is where you should be optimizing.

The ULP script I use to drill holes, will drill a hole or two, go to the other side of the board, drill a hole or two, etc.... These moves take ~10 sec. or so on a medium-size board (which I could cut down to <1sec, for 1000 holes that would be just over 2 hours saved, for one run of boards..

[ghyman]

yes, i do have it working.

I haven't really beautified the code, though, it's still in it's trial-and-error phase (lots of commented-out lines that didn't work, notes to myself to try this, that, or the other...) Give me a day or so to make it look a little less "sloppy", and I'll post what I have.

I will, of course, ask for credit if you ever do use it for anything other than personal use. it is the result of a LOT of time spent on my part. I don't mind sharing... we can all learn from one another, but I also like to be recognized for my efforts. fair enough?

[ghyman]

OK... here's what I've got.

It ain't pretty, but it works as well as I can get it (note the first post... "is this the best way...?)

Load it and run it, and here's a description of what happens:

1. create 250 points with random x/y coordinates. (this still needs updated to read in a text file of actual points)
2. starting with point 1, find the nearest point. Make that point 2. Then find the nearest point to point 2. Make that point 3. etc, etc.
3. Step 2 only gets 75% of the way there, so now it gets tricky...
4. Pick a continuous segment of 1/2 the points. Try a> flipping the segment or b> moving the segment.
5. If the trial in step 4 makes a shorter total length, then make that change permanent.
6. decrease the segment length, and repeat from step 4.

Always going for a shorter path does not automatically yield the shortest path in the long run. There's a function called "tryback" that will encourage the program to try short-term losses in progress in the hopes of long-term success.

I do not claim that this is 100% accurate as far as always finding the absolute shortest path. In fact, I would saythat it will find the shortest path only 20% of the time. But the other 80% of the time will still be very close.

As I said... this is ugly code, and I have not "finished" it... no input or output routines, lots of tried, failed, and commented-out code... ugly.

I will beautify it, complete it, and modify it if anyone has suggestions for improvement.

In the meantime, play with it and see what you think. Feedback is appreciated.