Fighting with computers

Computers are not always friendly.

Friday, May 11, 2007

New life to the Traveling Salesman Problem


I learned about this problem when I was a CS student: A salesman has to visit a set of cities and then returns home. The problem is to find the fastest/cheapest/shortest way of doing so. It is a NP-hard problem as the solution space is n! (for a n-city problem) that is impossible to be examined fully in a lifetime. It can be entertaining to do by hand, but there are many programs that may help you, like Concorde.
My interest for TSP was sparked as a possible solution to the optimization problem for the drawings made with my home-made painting machine. It is not a new problem but I was not aware of the best solution possible. I was lucky enough contacting Michael Trick who, right off the bat, gave me a nice and elegant solution.
I need to determine the right order for drawing a set of n lines but each line may be drawn in one direction or backwards. The solution to the problem needs to determine the drawing order of the lines plus the drawing direction for each one that makes the total drawing time minimum.
The solution Michael suggested was to use both endpoints of each line to create a TSP problem with 2*n cities and to use a negative cost for the edge connecting the two endpoints of each lines [and the Euclidean distance for the rest of edges]. It worked like a charm and I am really grateful for his help.
Other things I learned along this problem is that TSP problem has even been used to create an interesting form of art.

0 Comments:

Post a Comment

<< Home