Approximations are often good enough, and even annealing tended to give you a better answer if you were willing to wait. Exhaustive search is NP. But part of TS

Approximations are often good enough, and even annealing tended to give you a better answer if you were willing to wait. Exhaustive search is NP. But part of TSP is that once you have a good answer, you can backtrack on a larger number of bad ones. So there is value to doing both. And for some geometries, Djikstra and friends give you bounds on what the shortest path can be, within a factor of two, so you can start to carve out the problem space even before you’ve found a decent one.