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?
I've never personally used it, but another application besides drilling circuit boards is if you want to go to a number of different places, say to sell vacuums. You could use a solution of the problem to decide the cheapest way to visit everywhere exactly once.
Knowing when a problem is NP-hard is useful to exclude solutions involving solving that problem. Whenever you see TSP (or any other NP-hard problem) rear its ugly head for problems of non-trivial size you know you are heading down the wrong path. Not only do you know it, but you know why, and can confidently tell your boss/teammate/anyone.
That being said http://en.wikipedia.org/wiki/CONCORDE reveals that:
Concorde has been applied to problems of gene mapping,[1] protein function prediction,[2] vehicle routing,[3] conversion of bitmap images to continuous line drawings,[4] scheduling ship movements for seismic surveys,[5] and in studying the scaling properties of combinatorial optimization problems.[6]
Yes I use it in Geocaching application for route planning.
It currently uses a straight line distance between points but should correctly ( when I get around to it ) use roads to calc the distances between points.
Many types of optimized ordering, such as car pool pickup, UPS package delivery, etc. wherever the node traversal requirements can be expressed in one dimension of effort, such as time or distance.
I was once given the task of writing a program to fill a rectangular area fairly uniformly with a "squiggle" - a curved line which doesn't self-intersect. My first attempt was to generate random points within the rectangle and try to find a tour of them (not necessarily the absolute shortest). Unfortunately this approach just didn't work very well and I abandoned it.
I did solve the problem in the end though:
My successful method was not related to the TSP but for the curious I will summarize it:
Start with a single line segment. Now loop: if a line is "too long", divide it in two. Move each point a bit at random, but make points repel each other. End the loop when little progress can be made. There are details but hopefully you get the idea.
Of course this produces an angular path (which would have been acceptable) but it is easy to turn the corners into smooth arcs.
And yes I did keep the code.
Wouldn't Google Maps (And every other Map based routing software) be using some kind of travelling salesman to solve driving directions?
I have not used TSP as far as I know but I have worked on a number of autonomous robots to traverse a maze. So I wonder if TSP could be applied to maze solving.
Most of the time you don't want to use an algorithm that solves the NP-Complete/Hard problem. You just want an algorithm that is "good enough". These are usually based on heuristics and give reasonable approximations.
I had one problem that was an instance of Independent-Set (NP-Complete), but I found a greedy algorithm that gave pretty good results in the vast majority of cases, and had an efficient run-time.
Few problems in real-life match the stuff you learn in math class. The problems are simplified and abstracted so that you can see the math and not get distracted by details. The best real-life example of large TSPs, as you mentioned, doesn't actually involve any traveling salesman: it involves scheduling machines that have jobs to perform with sequence-dependent setup times. That includes machines where an arm moves a tool around different sites, and also some painting applications (red->orange->yellow is easier than red->yellow->orange). There are also some applications in x-ray crystallography where you have to orient some sample of a crystal at several different angles.
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.
This company was based on an improved TSP algorithm.
They route cable TV installers and repairmen around NYC among other problems.
Because humans can typically solve TSP problems on par or better than most algorithms for maps with 20-60 nodes, it's not very common to have a computer solve the problem. When the cost is high enough, having the computer get a 1-2% improvement over a human can be worth the cost of performing the calculation. If the route does not change, then one can justify spending some time optimizing it. This is common in integrated circuit design.
Airline travel websites use a specialized version of the TSP problem when the show you a list of airlines and the prices for each route. The difference is instead of distance, they optimize for cost, and certainly there is no requirement to visit each city once! Say you want to fly from LGA to LAX. There's about 1/2 dozen direct routes, and an infinite number of other routes. It may suggest LGA->ORD->LAX or LGA->DWF->LAX. Humans, who can manually price routes can sometimes find lower fares than the ones searched by the travel sites. Typically, people don't want more than two connections, but there isn't an upper limit to the number of connections for a given flight.
I've used it to solve routes for my Travelling Salesman iPhone Game. What's interesting is people are very good at solving the shortest route, but not at solving the longest route. The longest and shortest routes have the same complexity, but people seem trained to be able to find shortest routes, often faster and better than what a computer can do.
On my first job we built a home care scheduling application.
We solved the TSP problem with some non linear time constraints and with an additional non linear cost function.
We used a non optimal solver to solve the problem.