Tabu search uses a local or neighbourhood search procedure to iteratively move from a solution to a solution in the neighbourhood of , until some stopping criterion has been satisfied. To explore regions of the search space that would be left unexplored by the local search procedure and---by doing this---escape local optimality, tabu search modifies the neighbourhood structure of each solution as the search progresses. The solutions admitted to , the new neighbourhood, are determined through the use of special memory structures. The search now progresses by iteratively moving from a solution to a solution in .
Perhaps the most important type of short-term memory to determine the solutions in , also the one that gives its name to tabu search, is the use of a tabu list. In its simplest form, a tabu list contains the solutions that have been visited in the recent past (less than moves ago, where is the tabu tenure. Solutions in the tabu list are excluded from . Other tabu list structures prohibit solutions that have certain attributes (e.g. travelling salesman problem (TSP) solutions that include certain arcs) or prevent certain moves (e.g. an arc that was added to a TSP tour cannot be removed in the next moves). Selected attributes in solutions recently visited are labelled tabu-active. Solutions that contain tabu-active elements are tabu. This type of short-term memory is also called recency-based memory.