Tabu Search

The foundational mechanism that prohibits reversing recent moves for a specified number of iterations, known as the tabu tenure. This short-term memory structure prevents the search from immediately returning to previously visited solutions, forcing the algorithm to climb out of local optima. The tenure can be static (fixed length) or dynamic (randomly varied within a range) to introduce adaptive diversification.

A set of conditions that allow the algorithm to override a tabu classification and accept a prohibited move. The most common is the best-solution aspiration criterion, which permits a tabu move if it leads to a solution better than the best one found so far. This prevents the memory structure from blocking genuinely superior solutions and adds strategic flexibility to the search.

Beyond short-term recency, Tabu Search employs long-term memory to track the frequency of moves or visited solution attributes over the entire search history. This information drives diversification strategies that penalize frequently used attributes, steering the search toward unexplored regions of the solution space. It complements intensification by ensuring broad coverage of the search landscape.

A strategic component that focuses the search on regions near high-quality, elite solutions found during the search. By storing and revisiting attributes of historically good solutions, the algorithm intensifies the search in promising neighborhoods. This can involve returning to a previous best solution and exploring its vicinity more thoroughly or fixing certain solution components that appear consistently in elite candidates.

To avoid evaluating every possible neighbor in large problem instances, Tabu Search often uses candidate list strategies to restrict the neighborhood to a subset of promising moves. This can involve examining only the most impactful moves, using elite candidate lists derived from problem-specific knowledge, or applying successive filtering. This dramatically reduces computational effort per iteration while preserving solution quality.

An advanced intensification technique that explores trajectories connecting elite solutions. Given a starting solution and a guiding target solution, path relinking generates intermediate solutions by progressively introducing attributes from the target into the starting solution. This creates new candidate solutions along the path that often represent superior combinations of elite attributes, effectively bridging gaps between high-quality regions.

A probabilistic metaheuristic that escapes local optima by accepting worse solutions with a decreasing probability, mimicking the cooling of metal. Unlike tabu search's deterministic memory-based approach, simulated annealing relies on a stochastic acceptance criterion (the Metropolis criterion) controlled by a temperature parameter. While tabu search explicitly prohibits revisiting recent solutions, simulated annealing probabilistically explores the landscape, making it effective for problems with rugged, noisy fitness surfaces where tabu's rigid memory might be too restrictive.

A population-based metaheuristic that evolves a set of candidate solutions through selection, crossover, and mutation operators. In contrast to tabu search, which intensifies the search around a single current solution, genetic algorithms maintain a diverse population to explore the solution space globally. The crossover mechanism allows genetic algorithms to recombine building blocks from different solutions, while tabu search relies on neighborhood structures and memory to guide a single trajectory. Hybrid approaches often use tabu search as a local improvement operator within a genetic algorithm framework.

An iterative metaheuristic that improves a solution by repeatedly destroying and repairing large portions of it. ALNS uses an adaptive layer to select the most effective destroy and repair heuristics based on their past performance. Tabu search can be integrated into ALNS as the underlying local search component, or the tabu concept can be applied to the adaptive selection mechanism itself. Both methods share the goal of escaping local optima, but ALNS does so through large-scale perturbation rather than step-by-step neighborhood exploration with memory.

An exact optimization approach that formulates problems with linear objectives and constraints, where some variables are restricted to integer values. Unlike tabu search, which is a heuristic that finds near-optimal solutions without optimality guarantees, MILP solvers like Gurobi use algorithms such as Branch and Bound to prove optimality. For large-scale vehicle routing problems, exact methods become computationally intractable, making tabu search a practical alternative. Hybrid strategies often use MILP to solve subproblems within a tabu search framework or use tabu search to generate initial solutions for MILP warm starts.

A declarative paradigm that models combinatorial problems by defining variables, domains, and constraints, then uses a solver to systematically prune the search space through constraint propagation. Tabu search and constraint programming are often combined: constraint programming handles complex feasibility constraints (like time windows and precedence), while tabu search optimizes the objective function. This hybrid approach leverages constraint programming's strength in feasibility reasoning and tabu search's strength in objective improvement, creating a powerful solver for highly constrained routing problems like the Dial-a-Ride Problem.

A learning-based approach where an agent learns to make sequential routing decisions by interacting with an environment and receiving reward signals. Unlike tabu search, which requires a hand-crafted neighborhood structure and objective function, reinforcement learning can learn policies directly from experience. However, tabu search excels at exploitation within a known model, while reinforcement learning is better suited for exploration in stochastic environments where the transition dynamics are unknown. Recent research explores using reinforcement learning to learn adaptive tabu tenure strategies or neighborhood selection policies.