Tabu Search

Abstract This article provides an introductory treatment to tabu search, which is one of the most popular metaheuristic methods for solving difficult combinatorial optimization problems. Tabu search is based on local search, but attempts to avoid early termination at local optima, as these might have objective function values that are far inferior to the globally optimal one. Tabu search employs a limited memory of attributes of recent moves to avoid move reversals and looping and to guide the search procedure into unexplored areas of the solution space, thus improving the likelihood of finding a near‐optimal solution. We present the basic tabu search approach, discuss common enhancements with respect to implementing this method, and provide a brief review of sample applications to which tabu search has been effectively applied.