- Community Home
- :
- Discussion Forums
- :
- Most Active Software Boards
- :
- LabVIEW
- :
- Traveling Salesman problem

Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

Traveling Salesman problem

02-13-2003 11:47 AM

Options

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.

Re: Traveling Salesman problem

02-13-2003 01:06 PM

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

Re: Traveling Salesman problem

02-06-2018 04:37 PM

- Mark as New
- Bookmark
- Subscribe
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

Kudos are welcome...