A Tabu Search with a Double Neighborhood Strategy

Tabu Search (TS) is a well known and very successful method heuristic approach for hard optimization problems, linear or nonlinear. It is known to produce very good solutions, optimal or close to optimal for some hard combinatorial optimization problems. The drawback is that we have in general no optimality certificate, but this is the price to be paid for problems where the exact methods are too costly in terms of time and computational memory. One of the drawbacks of TS is that the strategies must be studied and refined for every instance. Many proposals exist to enhance the efficiency of this method heuristic. TS is particularly fragile in cases where there are many local optima of the problem. TS may be slow in the process of escaping a region of attraction of a local optima. If the strategy for evaluating the solutions in the neighborhood takes time to move away from the local optimum then it may compromise the search efficiency. In this paper we propose a double neighborhood strategy with opposite optimization directions (minimization and maximization). While one search for the best solution in the neighborhood the second search for the worse, and two parallel process develop switching from the minimization to maximization and vice-versa, when in consecutive iterations there is no improvement in solution. With this proposal, it is intended that the research can escape the attraction zone of a local optimum, more quickly allowing the research space to be better explored. We present an application to a Knapsack problem.