algorithmtraveling-salesmannp-hard

Have you used a traveling salesman algorithm to solve a problem?


I studied TSP in college in the context of NP Completeness. I have never actually had a situation where it would apply to a practical problem. A little bit of research shows that it has been used to pick the cheapest path to move a drill around, that is making holes in circuit boards. That is pretty much all I could find.

Are you using it? What other practical applications does the TSA have?


Solution

  • As with others in this thread I built a solution to an NP complete problem in college (it was a side project for a friend) - a scheduling program. At the time that I agreed to work on his problem I did not know what NP complete was. I later realized I had come up with some fairly good heuristics for solving the problem - but of course the real trick was knowing when to tell the user that there was no solution and they had over-constrained the problem.

    It was a great way to bring together my eventual theoretical classes and the real world.

    Again, heuristics and "close enough" are generally fine for real world uses where near-optimal solutions are preferred because of the cost of finding and implementing the ideal solution.