Fondements et applications des méthodes de recherche avec tabous

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 succesfully 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.