Tabu Search

Much like threshold accepting and simulated annealing, in its basic form, tabu search is an s-metaheuristic, which implies that a current, feasible solution to a problem will be transformed into a new feasible solution to a problem through a move in a local neighborhood. And, as with other heuristic methods, a specific move can be selected from the neighborhood multiple times during a search for the optimal solution. One difference between tabu search and the other two methods is that the move through the local neighborhood is deterministic. The best move from the local neighborhood is selected, regardless of whether the value of the new solution is better or worse than the value of the previous solution. The caveat to this process is that, in general, the move cannot consist of one that was selected recently, in terms of iterations of the model. This restriction preventing the use of recently selected moves represents the taboo (or tabu) nature of the search process. In effect, a recently selected move is tabu. There is one minor relaxation of this rule: if a potential move is tabu yet will lead to a superior solution that has not yet been recognized, the tabu restriction is ignored and the move is allowed. A second main difference between tabu search and the other two methods mentioned above involves the termination rule. In general, tabu search is allowed to run for some pre-defined number of iterations of the model (although more sophisticated termination rules can be developed). Simulated annealing and threshold accepting, in general, are allowed to run as long as the key variable (temperature or threshold) remains above a minimum, pre-defined value. Ordinarily, tabu search requires more time to complete a search, as compared to threshold accepting and simulated annealing, because many different alternatives need to be assessed in the local neighborhood before one of them is selected.