Coyote Blog

The Reference Frame has a video of a dog solving the traveling salesman problem.  I was doing some simulations years ago for a railroad company and actually had a traveling-salesman-like problem to solve with equipment routing.  The best approach I found was simulated annealing.  This algorithm starts out with a totally random solution, and then applies random swaps of route legs and then checks to see if the new route is better or worse than the old route.  So far, similar to any Monte Carlo approach.  But in this algorithm, the solution is allowed to jump to worse solutions, though the size of this jump is reduced over time as the algorithm is run.  This helps prevent the algorithm from getting stuck in local minima.

It is called simulated annealing because it is very parallel to the process of cooling and crystallization in a piece of steel.  When heated steel is plunged into water and cooled quickly, the molecules crystallize and are trapped in a higher energy state, whereas cooling the steel slowly lets the structure stabilize into a much lower energy state.  Metal that is quench cooled is harder but more brittle, metal that is annealed is softer and more ductile.  In the algorithm, the slow reduction in temperature is represented by the declining amount by which the algorithm can jump to a worse solution.