Tabu search is a metaheuristic (see Section 7.2.2.3) that aims to overcome the problem of a local search (LS) procedure (e.g. a greedy heuristic) becoming trapped at a local optimum. As such it is a general purpose extension to LS procedures that operates by permitting non-improving moves whenever a local optimum is encountered. It achieves this by recording the recent history of searches in a tabu list (a sort of short-term memory) and ensuring that future moves do not search this part of the search space, at least not for a specified number of iterations. This greatly reduces the likelihood of changing a solution configuration in a manner that will simply cycle back to the current solution. See Glover and Laguna (1997) for a full discussion of the method and variants.

Tabu search methods are thus defined by the search space, the pattern of local moves (the neighbourhood structure), and the use of search memory:

·         The search space, S, is simply the space (or set for purely combinatorial problems) of all possible solutions to a given problem. Note that this may be very large, or for some problems (e.g. those involving a mixture of discrete and continuous variables to be optimised) innumerably large. The search space can include infeasible as well as feasible solutions, and in some cases permitting the search to extend into infeasible regions is essential (e.g. examining possible solutions for which constraints have been relaxed)

·         The neighbourhood structure determines the set of moves, or transformations, of the current search space S effected by a single iteration of the process. Hence the neighbourhood, N, is a (typically small) subset of the search space: NÌS. A simple example of such transformations is the set of interchange heuristics, where one or more elements from the current solution are interchanged with one or more elements from other parts of the current solution and/or elements that are currently outside the components of the current solution

·         Search memory, in particular short-term search memory, is the characteristic that distinguishes tabu search from most other methods. A typical example would be the retention of a list of recent moves, whose reversal is tabu for a number of iterations (also known as the tabu tenure). With a network routing problem, in which customer A has just been moved from route 1 to route 2, one would prevent reversal of this interchange for a short period, in order to avoid the procedure cycling without improvement. The risk with this approach is that sometimes such moves are attractive and effective, and the process can be improved by relaxing strict tabus. The typical relaxation permitted (known as applying aspiration criteria) is to allow a tabu move if it results in a solution with an objective value that is an improvement on the best known value to date

Despite these protections, tabu search may still under-perform, either in terms of efficiency or quality of result. Various techniques have been devised to improve its performance, many of which are problem-specific in their design. These include: probabilistic selection of samples from the space N, in order to reduce the processing overhead and introduce randomness that again reduces the risk of encountering cycles; intensification, in which a number of components of the current solution (e.g. entire routes or assignments) are held fixed whilst other elements are allowed to continue being modified; and diversification, whereby components of the current solution that have appeared frequently or continuously since the start of the iteration process are systematically removed from the solution in order to give unused or rarely used components the chance of generating an overall improvement; surrogate objective functions can also improve performance (though not directly quality) of a solution by reducing the overhead that is sometimes present in computing the value of the objective function. If the surrogate function is highly correlated with the objective function and is very simple to compute, it can enable many more operations to be conducted within a given time period, hence expanding the range of solutions examined; such hybridisation is becoming an increasingly common practice, whereby techniques like tabu search are hybridised with other solution approaches such as genetic algorithms.