Simulated annealing is a metaheuristic devised by Kirkpatrick et al. (1983) and derives its name and approach from the behaviour of metals and glass as they are systematically heated and re-heated and then allowed to cool steadily. The objective, as with other metaheuristics, is to obtain a close approximation to the global optimum for a given problem. The original paper by Kirkpatrick et al. proved that the approach would converge to the global optimum, given enough time, which encouraged considerable investigation into this, and a range of other metaheuristics for solving particularly difficult combinatorial problems. Simulated annealing can be viewed as a form of managed random walk through the solution space, S, in which exploration of the neighbourhood space is determined by appeal to annealing behaviour, which in turn relates to the temperature of the process over time. The procedure is essentially as follows:

·         Define the initial configuration for the problem, e.g. a random solution set, S₀*, and an initial temperature variable, T, and evaluate the cost, C₀*, (e.g. the total distance or travel time) for this solution

·         Perturb S₀* to a new neighbouring state, S₁*, e.g. by moving a potential facility location by some random coordinate step or by an interchange process. Compute the cost of this new state, C₁* and subtract C₀*, to give the cost difference DC

·         If DC<0 then the new configuration has lower overall cost, so select the new configuration as the preferred current configuration. However, if the cost is higher, still retain the option of keeping the new configuration according to the so-called Metropolis criterion: if p<u where u is a uniform random number in the range [0,1]. If the criterion applies then the temperature variable, T is reduced by a factor, a say (e.g. a=0.9) and the process iterates from the previous step until some stopping criterion is reached (e.g. number of iterations, absolute or relative improvement of the objective function)

In a sense the temperate parameter controls the way in which the search space is traversed, initially in large steps and then, as the temperature reduces (the annealing schedule), in smaller and smaller steps until T=0 or another stopping criterion has been reached.

Simulated annealing is often a relatively slow technique, so modifications are often applied that are problem-specific and the result of analysis of the statistical behaviour of the model, with greatly improvement performance being possible. Such changes, however, may remove the guarantee of ultimate global optimisation. Significant advantages of simulated annealing include the simplicity of the basic algorithm, the low memory overhead of the procedure, and the range of optimisation problems (geospatial and other) to which the approach may be applied. In the geospatial arena the procedure has been successfully applied to a variety of problems, including optimum facility location (e.g. see Muttiah et al., 1996) and travelling salesman problems.