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

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.

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.

http://code.google.com/p/gpsturbo/