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.