
Tabu search
Local search employs the idea that a given solution S may be improved by a series of small changes. Those solutions obtained by modifying solution S are called neighbors of S. The local search algorithm starts with some initial solution and moves from neighbor to neighbor as long as it is possible to decrease the objective function value. The main problem with this strategy is how to escape from local minima that is, those points in which the search cannot find any further neighborhood solution that decreases the objective function value. Different strategies have been proposed to solve this problem. One of the most efficient of these strategies is tabu search. Tabu search allows the search to explore solutions that do not decrease the objective function value only in those cases where these solutions are not forbidden. This is usually obtained by keeping track of the last solutions in term of the action used to transform one solution to the next. When an action is performed it is considered tabu for the next T iterations, where T is the tabu status length. A solution is forbidden if it is obtained by applying a tabu action to the current solution. 
