By Manuel Laguna.
This tutorial focuses on the metaheuristics known as tabu search and scatter search. Tabu search has dramatically changed our ability to solve a host of problems in applied science, business, and engineering. The adaptive memory designs of tabu search have provided useful alternatives and supplements to the types of memory embodied in other metaheuristic approaches. We also explore the evolutionary approach called scatter search, which originated from strategies for creating composite decision rules and surrogate constraints. Numerous studies have demonstrated the practical advantages of this approach for solving a diverse array of optimization. Scatter search contrasts with other evolutionary procedures, such as genetic algorithms, by providing unifying principles for joining solutions based on generalized path constructions and by utilizing strategic designs where other approaches resort to randomization. Additional advantages are provided by intensification and diversification mechanisms that exploit adaptive memory, drawing on foundations that link scatter search to tabu search. We show connections between tabu search and scatter search by demonstrating how they can be applied to many optimization problems found in practice. This tutorial also discusses the search strategy called path relinking, relevant to both tabu and scatter search. Features added to both tabu and scatter search by extension of their basic philosophy are captured in the path relinking framework. From a spatial orientation, the process of generating linear combinations of a set of reference solutions (as typically done in scatter search) may be characterized as generating paths between and beyond these solutions, where solutions on such paths also serve as sources for generating additional paths. This leads to a broader conception of the meaning of creating combinations of solutions. By natural extension, such combinations may be conceived to arise by generating paths between and beyond selected solutions in the neighborhood space. Finally, we highlight key ideas and research issues associated with tabu search, scatter search, and path relinking that offer promise of yielding future advances.