Tabu Search

The core mechanism that prevents cycling by forbidding moves that revert to recently visited solutions. A tabu list stores solution attributes (e.g., swapped edges, moved nodes) for a fixed number of iterations called the tabu tenure. Any move possessing an attribute on this list is classified as tabu and temporarily prohibited, forcing the search to explore new regions of the solution space.

• Tabu Tenure: The number of iterations an attribute remains forbidden
• Attribute-Based: Stores move characteristics, not full solutions, for memory efficiency
• Dynamic Tenure: Can be randomized within a range (e.g., 5-10 iterations) to add robustness

A mechanism that overrides the tabu status of a move when it leads to a solution better than the best-so-far global optimum. This prevents the algorithm from missing superior solutions simply because they are temporarily forbidden. The most common form is the global aspiration criterion: if a tabu move produces a solution with an objective value strictly better than any previously encountered, the tabu restriction is lifted and the move is accepted.

• Default Aspiration: Override if new solution > global best
• Search Diversification: Prevents memory from becoming overly restrictive
• Custom Criteria: Can be extended to include solution diversity or constraint satisfaction thresholds

Techniques that focus the search on promising regions of the solution space by returning to elite solutions and exploring their neighborhoods more thoroughly. Intensification often involves storing a set of high-quality, diverse solutions during the search and periodically restarting from them with modified parameters or focused neighborhood operators.

• Elite Set: Maintains a pool of the best solutions found
• Path Relinking: Generates new solutions by exploring trajectories between elite solutions
• Frequency-Based Memory: Uses long-term memory to identify common attributes in good solutions and bias the search toward them

Techniques that drive the search into unexplored regions of the solution space to avoid stagnation. Using long-term frequency memory, the algorithm penalizes moves or solution attributes that have been used frequently, encouraging exploration of less-visited areas. This is often implemented by adding a penalty term to the objective function based on the frequency count of move attributes.

• Frequency Penalty: Adds a cost proportional to how often an attribute has appeared
• Restart Mechanisms: Periodically reinitializes the search from a new random solution
• Strategic Oscillation: Alternates between feasible and infeasible regions to cross barriers in the search space

The set of solutions reachable from the current solution by applying a single, well-defined move operator. For routing problems, common operators include 2-opt (reversing a segment of a route), Or-opt (relocating a segment), and relocate (moving a single customer). The efficiency of Tabu Search depends heavily on the neighborhood's ability to connect the solution space while remaining computationally tractable to evaluate.

• 2-opt: Reverses a subsequence to remove edge crossings
• Relocate: Moves a node from one position to another
• Exchange: Swaps the positions of two nodes

A computational acceleration technique that restricts the neighborhood evaluation to a subset of promising moves rather than exhaustively examining all possibilities. For large-scale routing problems, evaluating every possible move is prohibitive. Candidate lists use heuristics to pre-filter moves, such as only considering swaps between nodes that are geographically nearby or have high potential for improvement.

• Nearest Neighbor: Only evaluate moves involving nodes within a distance threshold
• Elite Candidate: Maintain a list of historically successful move types
• Don't Look Bits: Skip nodes that did not improve the solution in the last iteration