Traveling Salesman problem

[Jake Stern]

Does anyone have any experience with implementing a traveling salesmen solver in Labview, or interfacing with a publicly available .dll? I would like to optimize the path of a semiconductor test tool. When running tests that probe many devices all over the wafer, the default pattern that we currently use is far from the most efficient. It is unnecessary that THE optimal solution is found, but a heuristic that does better than simply going to the leftmost column that contains a device in the test, going top to bottom, then moving right to the next column, etc. would be nice.

Some tests have very few devices, and could even be solved brute-force. However, some tests involve 30, 50, or even up to 200 locations, and these could be estimated w
ith a decent heuristic.

[Joey Oravec]

"Jake Stern" wrote in message
news:506500000008000000ED750000-1042324653000@exchange.ni.com...
> Does anyone have any experience with implementing a traveling salesmen
> solver in Labview, or interfacing with a publicly available .dll? I
> would like to optimize the path of a semiconductor test tool. When
> running tests that probe many devices all over the wafer, the default
> pattern that we currently use is far from the most efficient. It is
> unnecessary that THE optimal solution is found, but a heuristic that
> does better than simply going to the leftmost column that contains a
> device in the test, going top to bottom, then moving right to the next
> column, etc. would be nice.
>
> Some tests have very few devices, and could even be solved
> brute-force. However, some tests involve 30, 50, or even up to 200
> locations, and these could be estimated with a decent heuristic.

I was faced with the same problem in a motion control program a while ago.
The TSP is in lots of books and easy-enough to implement. Like you said,
quick and easy is probably fine, so:

- I stored my X,Y coordinates as an array of clusters. Check the sort 1-d
array function, and you'll find that it sorts clusters first by comparing
first elements, then by second elements. It can't get any easier than
sorting left to right, top to bottom with a prewritten VI. Of course in the
worst-case-scenario your test could zigzag back and forth if your sort
doesn't formulate good equivalence classes but I have found this works
"plenty fine" for my movement cost.

- If simple sorting wont work, maybe you want to do nearest neighbor. Pick a
point (top left? maximal distance from center?) and determine your next best
point. Maybe look for the next point with minimum distance and hope you dont
have lots of zigzagging in the end for the final points. Or my favorite,
determine the point with minimal angle such that you're guaranteed to spiral
inward or outward. Usually gets you minimal results at the beginning and
some long distances to catch missed points at the end.

- So there's lots of options. If you're in doubt in the end, force an
election. Run two easy heuristics and determine which has a lower total cost
and use that one. Still might be easier than solving the real minimal
solution.

Clearly the heuristic is going to win in some cases and fail in others. In
this case since you said there are 50-200 points you almost may as well
solve the optimal sorting. But let me know how it goes!

-joey

[JensG69]

Kind of off-topic, but this thread is 15 (!) years old...