Heuristics that commence with one solution to a problem (typically a combinatorial optimisation problem) and then systematically swap members of this initial or current solution with members that either form part of another element of this current solution or belong to the set “not a member” are called interchange heuristics. There are many examples of such heuristics. For example, the automatic zoning procedures (AZP) described in Section 4.2.11 are an example of such an interchange procedure, as is Jenk’s natural breaks method for classifying univariate data (see also, Figure 4‑21).

One of the best known interchange heuristics is the n-opt family applied to the standard form of the travelling salesman problem (TSP) with Euclidean distance metric. This is a simple improvement algorithm that applies to an existing symmetric tour of all the locations. The procedure simply takes two edges in the solution at random, say (i,j) and (k,l) and replaces them with (i,k) and (j,l) or (i,l) and (j,k). There are several improvements to this scheme which make a significant difference to its performance. These include checking that the revised tour contains no crossings, as this will never be the shortest configuration and only opting for interchanges to a candidate list of swaps that will yield the greatest benefit. 3-opt interchange is essentially the same as 2-opt but taking three edges at a time. This can be more effective and is essential for asymmetric problems, but at a higher computational cost.

In the field of location modelling, a common class of problems involves identifying potential facility locations and then allocating customers to those locations. The objective is generally to minimise the cost of providing services from p facilities to m customers. A series of algorithms have been developed to solve such problems. One of the best known in geospatial analysis is a vertex substitution algorithm due to Teitz and Bart (1968) — see further, Section 7.4.2. The solution process systematically evaluates marginal changes to a given set of facility locations, as follows:

·         An initial facility configuration is supplied to the algorithm (e.g. a random selection of p locations from a candidate set of n>p) — this provides the first "current solution"

·         The first candidate not in the current solution is substituted for each facility site in the current solution and the customers are re-allocated based on this new configuration of facilities. The substitution yielding the largest decrease in the objective function, if any, is selected for a swap

·         When all of the candidates not in the current solution have been substituted for all of the sites in the current solution, an iteration is complete and the process can then be repeated

The algorithm terminates when a single iteration does not result in a swap. At termination, the interchange heuristic generates facility configurations that meet all three necessary, but not sufficient, conditions for an optimum solution to the problem: all facilities are local medians (least travel cost/distance centres) for the demand points allocated to them; all demand points are allocated to their closest facility;
and finally, removing a facility from the solution and replacing it with a candidate site not in the solution always incurs a net increase or no change in the value of the objective function. Note that this solution will not in general be the global optimum, is not necessarily unique, nor is there any immediate way of identifying how good the solution found really is (i.e. how close it is to the global optimum). As with other heuristics, there are many possible variants and extensions of the core interchange procedure.