|MadSci Network: Computer Science|
It's hard to say without knowing the exact details. I have not specifically looked into others' research in this area. It is quite often the case that highly complex problems such as this one can be reduced in complexity by applying an assumption. These assumptions make the solution "impure", but when assumption like "the salesman is unlikely to travel from one side of the planet to the other in one go" are so "obviously" correct, that the solution is not tainted in any way. If this is too wooly, I suggest resubmitting, detailing the algorithm.
Try the links in the MadSci Library for more information on Computer Science.