Principles and applications of tabu search methods

Among the new general heuristics developed over recent years in the field of combinatorial optimization, the tabu search method (TS) due to Glover has been found to be very promising having been successfully applied to several difficult problems. TS is in fact a metaheuristic which combines a local search procedure with a number of rules and mechanisms that enable it to overcome the obstacle of local optimality while preventing it from cycling. In this paper, we present a description of the principles underlying the TS method and of its various elements. A review of the main applications of TS to date is also provided.