Optimization Algorithms

6 Tabu search

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