I think you mean that there are (cities-1)! total routes. Only the shortest one(s) are solutions.
Factorial grows faster than exponential.
This is my point, which I apparently failed at communicating.
Oops, I just failed at reading.
As the person below answered, there are less naive ways of doing it. Check out: http://www.tsp.gatech.edu/index.html if you are interested.
Is it just me or does the traveling salesman problem have (cities-1)! solutions? thus it is not exponential? and is in fact far more annoying?