Simulated annealing is used heavily in chip design automation (EDA). I first used it when writing a toy placement tool while taking a course on the subject.
I love the beauty of the analogy to annealing a metal in metallurgy, and how surprisingly well it translates into software. The fact that the result is non-deterministic, but always useful, makes me smile.
The probability of accepting an inferior tour is a function of how much longer the candidate is compared to the current tour, and the temperature of the annealing process.
Shouldn't the distance of the "nearest" neighbor be a function of temperature, rather than (or at least in addition to) the probability of acceptance? Isn't that how simulated annealing can escape a local minimum far from better or global maxima? Intuitively that is how the real annealing process works.
One of the fundamental premises of simulated annealing is this "looking backwards" approach. It's for the sake of the sanity of the implementor. How do you modify scalar values that determine a random process in such a way that the outcome does not exceed some error condition? You can't (in general), that's why you turned to annealing in the first place. You were unable to control error bounds. Instead, you make a completely random guess and only accept it if it's within the current "acceptable" range. This is easy to implement and gives suprisigly good results.
Slide 5 of this deck shows some of the problems in chip-design, most of which have been heavily optimized by simulated annealing. http://www.ispd.cc/slides/ISPD12Slides/ISPD12_3_2.pdf
I love the beauty of the analogy to annealing a metal in metallurgy, and how surprisingly well it translates into software. The fact that the result is non-deterministic, but always useful, makes me smile.