tabusearch

Tabu search is a metaheuristic optimization method that guides a local search procedure to explore beyond local optima. Developed by Fred Glover in the late 1980s, it uses a memory structure to avoid cycling back to recently visited solutions. At each iteration, the algorithm moves from the current solution to a best feasible neighbor that is not prohibited by the tabu list, or that meets an aspiration criterion that overrides tabu status. The tabu list records attributes of moves or solutions, and its tenure determines how long a move remains tabu.

The search relies on a defined neighborhood structure for the problem, with common moves including swapping elements, reinserting items, or exchanging segments in routing or sequencing problems. An aspiration criterion allows high-quality moves to be accepted even if they are tabu, preventing overly restrictive search.

Tabu search employs short-term memory to prevent cycles and to intensify the search around promising regions, while longer-term memory can guide diversification when progress stalls. Variants include reactive tabu search, which adapts parameters during the search, and parallel tabu search, which distributes the workload across multiple processors or landscapes.

Applications of tabu search span many combinatorial problems, such as scheduling, vehicle routing, job-shop sequencing, timetabling, and facility layout. Its strengths include conceptual simplicity, flexibility, and strong performance on a wide range of problems. Limitations involve the need for careful parameter tuning (such as tabu tenure and stopping rules) and sensitivity to the design of the neighborhood; performance depends on problem structure and implementation details.