ABSTRACT
Tabu or taboo search (TS) was proposed by Glover (1989, 1990) to solve the real-world combinatorial optimization problems, which include graph theory problems, and integer and mixed-integer problems. However, it had its roots in the late 1970s (Glover, 1977) when it was applied to integer programming problems. TS is a meta-heuristic which starts with an initial solution and then systematically searches the neighborhood for the most appropriate solution. Initially, it performs several moves on the current solution to generate a set of solutions in the neighborhood. Based on the tabu memory (which keeps track of the previously visited points by means of tabu list), it checks whether the newly generated solution is close to one of the solutions in the list. If it is in the tabu memory then the new solution is not allowable; otherwise, it is an allowable solution. TS then selects the best among all the allowable solutions as the next solution, and inserts it into the tabu memory (i.e., tabu list). The new solution replaces the best solution if it is found to be better. These steps are repeated until some termination criterion such as maximum number of iterations is satisfied.
