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.
This work is funded by national funds through the FCT - Fundação para a Ciëncia e a Tecnologia, I.P., under the scope of the project UIDB/00297/2020 (Center for Mathematics and Applications).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Instances of 0/1 knapsack problem. http://artemisa.unicauca.edu.co/~johnyortega/instances_01_KP/
Abdul-Rahman, S., Yung, V.C.: Comparison of optimization and tabu search approach for solving capital budgeting based on knapsack problem (2019)
Amaral, P., Pais, T.C.: Compromise ratio with weighting functions in a tabu search multi-criteria approach to examination timetabling. Comput. Oper. Res. 72, 160–174 (2016)
Assi, M., Haraty, R.A.: A survey of the knapsack problem. In: 2018 International Arab Conference on Information Technology (ACIT), pp. 1–6. IEEE (2018)
Cheeneebash, J., Nadal, C.: Using tabu search heuristics in solving the vehicle routing problem with time windows: application to a Mauritian firm. Univ. Maurit. Res. J. 16, 448–471 (2010)
Cho, M.: The knapsack problem and its applications to the cargo loading problem. Anal. Appl. Math 48, 48–63 (2019)
Cordeau, J.F., Laporte, G.: Tabu search heuristics for the vehicle routing problem, pp. 145–163. Springer, Boston (2005). https://doi.org/10.1007/0-387-23667-8_6
Gendreau, M.: An introduction to tabu search. In: Handbook of Metaheuristics, pp. 37–54. Springer, Cham (2003). https://doi.org/10.1007/0-306-48056-5_2
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)
Glover, F., Laguna, M.: Tabu Search. Kluwer Academic Publisher, Dordrecht (1997)
Hertz, A., Taillard, É., Werra, D.: A tutorial on tabu search (1992)
Hertz, A., de Werra, D.: The tabu search metaheuristic: how we used it. Ann. Math. Artif. Intell. 1, 111–121 (1990). https://doi.org/10.1007/BF01531073
Hvattum, L.M.: On the value of aspiration criteria in tabu search. Int. J. Appl. Metaheuristic Comput. (IJAMC) 7(4), 39–49 (2016)
Nonobe, K., Ibaraki, T.: A tabu search approach to the constraint satisfaction problem as a general problem solver. Eur. J. Oper. Res. 106(2), 599–623 (1998). https://doi.org/10.1016/S0377-2217(97)00294-4
Osman, I.: Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann. Oper. Res. 41, 421–451 (1993)
Pais, T.C., Amaral, P.: Managing the tabu list length using a fuzzy inference system: an application to examination timetabling. Ann. Oper. Res. 194, 341–363 (2012). https://doi.org/10.1007/s10479-011-0867-6
Pirim, H., Bayraktar, E., Eksioglu, B.: Tabu search: a comparative study. In: Jaziri, W. (ed.) Tabu Search, chap. 1. IntechOpen, Rijeka (2008). https://doi.org/10.5772/5637
Prajapati, V.K., Jain, M., Chouhan, L.: Tabu search algorithm (TSA): a comprehensive survey. In: 2020 3rd International Conference on Emerging Technologies in Computer Engineering: Machine Learning and Internet of Things (ICETCE), pp. 1–8. IEEE (2020)
Taillard, É., Badeau, P., Gendreau, M., Guertin, F., Potvin, J.: A tabu search heuristic for the vehicle routing problem with soft time windows. Transp. Sci. 31, 170–186 (1997)
Taillard, E.: Tabu search. In: Siarry, P. (ed.) Metaheuristics, pp. 51–76. Springer, Cham (2016)
Talbi, E.G.: Metaheuristics: From Design to Implementation. Wiley, Hoboken (2009)
Werra, D., Hertz, A.: Tabu search: a tutorial and an application to neural networks. OR Spektrum 11, 131–141 (1989)
Acknowledgement
We would like to thank the reviewers for their valuable comments and suggestions that helped to improve our manuscript.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Amaral, P., Mendes, A., Espinosa, J.M. (2022). A Tabu Search with a Double Neighborhood Strategy. In: Gervasi, O., Murgante, B., Misra, S., Rocha, A.M.A.C., Garau, C. (eds) Computational Science and Its Applications – ICCSA 2022 Workshops. ICCSA 2022. Lecture Notes in Computer Science, vol 13378. Springer, Cham. https://doi.org/10.1007/978-3-031-10562-3_16
Download citation
DOI: https://doi.org/10.1007/978-3-031-10562-3_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-10561-6
Online ISBN: 978-3-031-10562-3
eBook Packages: Computer ScienceComputer Science (R0)