This chapter covers
- Understanding local search
- Understanding how tabu search extends local search
- Solving constraint-satisfaction problems
- Solving continuous problems
- Solving routing problems
- Solving assembly line balancing problems
In the previous chapter, you were introduced to trajectory-based metaheuristics, and you learned about simulated annealing (SA) as an example of these metaheuristic algorithms. The actual first use of a metaheuristic is probably Fred Glover’s tabu search (TS) in 1986, although his seminal article on tabu search was published later, in 1997 [1]. The word “tabu” (also spelled “taboo”) originated from the Polynesian languages of the South Pacific. It is a term used to describe something that is prohibited, forbidden, or considered socially unacceptable within a particular culture or society. Tabu search is called “tabu” because it uses a memory structure to keep track of solutions that have been recently explored so it can avoid returning to them, especially in the early stage of the search, in order to avoid getting stuck in local optima.