Travelling Salesman Problem (TSP) via Simulated Annealing A Motivating Example
The Travelling Salesman Problem (TSP) is a classic one where a "salesman" tries to minimize their length of travel (i.e., distance travelled) to a number of destinations (e.g., a plane flying along a flight route).
The TSP can be solved using a variety of techniques such as dynamic programming, simulated annealing (SA), or genetic algorithms.
In R, the optim package has a method called SANN that performs simulated annealing for a given problem of interest. The example within the documentation is the TSP using the eurodist dataset of major European cities.
Typically we want to run SA with a large number of iterations (iters) and a high temperature ($T$). The idea is that at high $T$, the search is purely random, exploring lots of solutions in the search space. Randomness decreases as $T$ is lowered and the search tends to exploit good solutions.
Running the example in R several times (since SA is stochastic), as well as increasing both iters and $T$, the maximal distance travelled changes a bit, but usually not by much. However, the actual permutation of visited cities does change quite substantially as it is almost always the case that a global optimum is never found (only a local one).
SA and its relatives are useful because they can find "good enough" solutions in very little time.
Question
If the actual permutation changes quite substantially, why is SA a "good" approach to employ at all? Suppose, in some crazy world, that airlines actually used SA to determine flight paths on a regular basis. Surely, because the permutation is often not a global solution, some other approach ought to be employed.
Clarification
"Good" stochastic algorithms should be well-behaved when run multiple times. This is certainly the case for real parameter optimization, but not for combinatorial problems like the TSP. Why is this the case?

The goal of SA is not to give you the global solution (in fact you can't even know if there is one "global solution" .. because in order to know it you should be able to calculate all the distance travalled for any possible permutations ... and the point is that this is not possible in a reasonable time - reasonnable regarding the human life duration at least !-), but to give you a rather good solution.
The fact that it doen't give allways the same solution is not an issue, because it is the core of the algorithm,and what makes it efficient. And,as far as I know, and as long as there is no quantic computers, amost all good algorithms for this kind of problem are stochastic (to be honnest, I don't know if there are competitive deterministc algorithms .. may be someone could tell us that ?).
