@inproceedings{36ffcac7f14d4585a3e718564b058f8c,
title = "A Tabu Search with a Double Neighborhood Strategy",
abstract = "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.",
keywords = "Double neighborhood, Neighborhood search, Tabu Search",
author = "Paula Amaral and Ana Mendes and Espinosa, {J. Miguel}",
note = "Funding Information: This work is funded by national funds through the FCT - Funda{\c c}{\~a}o para a Ci{\^e}ncia e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications). Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 22nd International Conference on Computational Science and Its Applications , ICCSA 2022 ; Conference date: 04-07-2022 Through 07-07-2022",
year = "2022",
month = aug,
doi = "10.1007/978-3-031-10562-3_16",
language = "English",
isbn = "978-3-031-10561-6",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "219--230",
editor = "Osvaldo Gervasi and Beniamino Murgante and Sanjay Misra and Rocha, {Ana Maria} and Chiara Garau",
booktitle = "Computational Science and Its Applications – ICCSA 2022 Workshops",
address = "Netherlands",
}