Single Solution Metaheuristics

Metaheuristic approaches can be classified according to different criteria, one being the number of solutions that are evolved at each stage of the algorithm: one single solution or more than one. This chapter deals with metaheuristic algorithms that evolve one single solution; they are all enhancements of a basic local search procedure. Many different approaches have been presented, which could be included here. We choose six of them, namely Simulated Annealing, Tabu Search, GRASP, Iterated Local Search, Variable Neighborhood Search, and Ejection chains, as representative of the class and as the most widely used in the matheuristic literature. Matheuristic algorithms have in fact been used to complement each of them, along with others of the unreported ones. The techniques used to include mathematical components in the basic metaheuristic structure tend to be general and independent of the specific single solution metaheuristic they have been reported for.