Tabu Search

Tabu search is a memory-based metaheuristic introduced by Glover (1986, 1989, 1990); a related idea was independently proposed by Hansen (1986). Its defining feature is explicit memory: while simulated annealing relies on randomness and genetic algorithms on a population, tabu search keeps a list of recently performed moves or visited solution attributes and forbids reversing them. Core components are: (1) a neighbourhood structure and move evaluation; at each iteration the search moves to the best non-tabu neighbour even if it worsens the objective (escape from local optima); (2) short-term memory (the tabu list) of length k, with k called the tabu tenure; (3) an aspiration criterion under which a tabu move is allowed if it improves the best-known solution; (4) intermediate-term memory for intensification — deepening the search around frequently visited high-quality solutions; (5) long-term memory for diversification — jumping toward unexplored regions. Variants include granular tabu search, reactive tabu search (Battiti and Tecchiolli 1994, which adjusts the tenure automatically), and adaptive memory programming. Tabu search is among the strongest metaheuristics for VRP, scheduling, sequencing, and assignment problems; Cordeau and Laporte's VRP work is an industry benchmark. Compared with simulated annealing, it is more deterministic and memory-intensive, with similar solution quality and lower parameter sensitivity. References: Glover and Laguna (1997), Gendreau and Potvin (2010).