The solution space for traveling salesman consists of the set of
all (*n*-1)! possible circular permutations of the vertices.
A candidate solution can thus be represented using an array
*S* of *n-1* vertices,
where defines the (*i*+1)st vertex on the tour starting from .
The cost function evaluating a candidate solution is equally straightforward,
for we can sum up the costs of the edges defined by *S*.

**Figure:** Improving a TSP tour by swapping a pair of edges

The most obvious transition mechanism would be to swap the current tour positions of a random pair of vertices and . This changes up to eight edges on the tour, deleting the edges currently adjacent to both and , and adding their replacements. Better would be to swap two edges on the tour with two others that replace it, as shown in Figure . Since only four edges change in the tour, the transitions can be performed and evaluated faster. Faster transitions mean that we can evaluate more positions in the given amount of time.

In practice, problem-specific heuristics for TSP outperform simulated annealing, but the simulated annealing solution works admirably, considering it uses very little knowledge about the problem.

Mon Jun 2 23:33:50 EDT 1997