Skip to main content
main-content

Tipp

Weitere Kapitel dieses Buchs durch Wischen aufrufen

2018 | OriginalPaper | Buchkapitel

12. Variable Neighborhood Descent

verfasst von: Abraham Duarte, Jesús Sánchez-Oro, Nenad Mladenović, Raca Todosijević

Erschienen in: Handbook of Heuristics

Verlag: Springer International Publishing

share
TEILEN

Abstract

Local search heuristic that explores several neighborhood structures in a deterministic way is called variable neighborhood descent (VND). Its success is based on the simple fact that different neighborhood structures do not usually have the same local minimum. Thus, the local optima trap problem may be resolved by deterministic change of neighborhoods. VND may be seen as a local search routine and therefore could be used within other metaheuristics. In this chapter, we discuss typical problems that arise in developing VND heuristic: what neighborhood structures could be used, what would be their order, what rule of their change during the search would be used, etc. Comparative analysis of usual sequential VND variants is performed in solving traveling salesman problem.
Literatur
2.
Zurück zum Zitat Carrasco R, Pham A, Gallego M, Gortázar F, Martí R, Duarte A (2015) Tabu search for the maxmean dispersion problem. Knowl-Based Syst 85:256–264 CrossRef Carrasco R, Pham A, Gallego M, Gortázar F, Martí R, Duarte A (2015) Tabu search for the maxmean dispersion problem. Knowl-Based Syst 85:256–264 CrossRef
3.
Zurück zum Zitat Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1997) Combinatorial optimization. Wiley, Chichester CrossRef Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1997) Combinatorial optimization. Wiley, Chichester CrossRef
4.
5.
Zurück zum Zitat Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evolut Comput 1(1):53–66 CrossRef Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evolut Comput 1(1):53–66 CrossRef
6.
Zurück zum Zitat Duarte A, Escudero LF, Martí R, Mladenović N, Pantrigo JJ, Sánchez Oro J (2012) Variable neighborhood search for the vertex separation problem. Comput Oper Res 39(12):3247–3255 MathSciNetCrossRef Duarte A, Escudero LF, Martí R, Mladenović N, Pantrigo JJ, Sánchez Oro J (2012) Variable neighborhood search for the vertex separation problem. Comput Oper Res 39(12):3247–3255 MathSciNetCrossRef
7.
Zurück zum Zitat Duarte A, Martí R (2007) Tabu search and GRASP for the maximum diversity problem. Eur J Oper Res 178(1):71–84 MathSciNetCrossRef Duarte A, Martí R (2007) Tabu search and GRASP for the maximum diversity problem. Eur J Oper Res 178(1):71–84 MathSciNetCrossRef
8.
Zurück zum Zitat Duarte A, Sánchez A, Fernández F, Cabido R (2005) A low-level hybridization between memetic algorithm and VNS for the max-cut problem. In: ACM genetic and evolutionary computation conference, New York CrossRef Duarte A, Sánchez A, Fernández F, Cabido R (2005) A low-level hybridization between memetic algorithm and VNS for the max-cut problem. In: ACM genetic and evolutionary computation conference, New York CrossRef
10.
11.
Zurück zum Zitat Gallego M, Laguna M, Martí R, Duarte A (2013) Tabu search with strategic oscillation for the maximally diverse grouping problem. J Oper Res Soc 64(5):724–734 CrossRef Gallego M, Laguna M, Martí R, Duarte A (2013) Tabu search with strategic oscillation for the maximally diverse grouping problem. J Oper Res Soc 64(5):724–734 CrossRef
12.
Zurück zum Zitat Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York MATH Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York MATH
13.
Zurück zum Zitat Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549 MathSciNetCrossRef Glover F (1986) Future paths for integer programming and links to artificial intelligence. Comput Oper Res 13(5):533–549 MathSciNetCrossRef
14.
Zurück zum Zitat Glover F (1998) A template for scatter search and path relinking. In: Selected papers from the third European conference on artificial evolution, AE’97. Springer, London, pp 3–54 Glover F (1998) A template for scatter search and path relinking. In: Selected papers from the third European conference on artificial evolution, AE’97. Springer, London, pp 3–54
15.
Zurück zum Zitat Hansen P, Mladenović N (1999) An introduction to variable neighborhood search. In: Meta-Heuristics. Springer, Boston, pp 433–458 Hansen P, Mladenović N (1999) An introduction to variable neighborhood search. In: Meta-Heuristics. Springer, Boston, pp 433–458
16.
Zurück zum Zitat Hansen P, Mladenović N (2003) Variable neighborhood search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic Publisher, New York, pp 145–184 CrossRef Hansen P, Mladenović N (2003) Variable neighborhood search. In: Glover F, Kochenberger G (eds) Handbook of metaheuristics. Kluwer Academic Publisher, New York, pp 145–184 CrossRef
17.
Zurück zum Zitat Hansen P, Mladenović N (2006) First vs. best improvement: an empirical study. Discret Appl Math 154(5):802–817 MathSciNetCrossRef Hansen P, Mladenović N (2006) First vs. best improvement: an empirical study. Discret Appl Math 154(5):802–817 MathSciNetCrossRef
19.
Zurück zum Zitat Holland JH (1992) Adaptation in natural and artificial systems. MIT Press, Cambridge, MA Holland JH (1992) Adaptation in natural and artificial systems. MIT Press, Cambridge, MA
20.
Zurück zum Zitat Hoos H, Süttzle T (2004) Stochastic local search: foundations & applications. Morgan Kaufmann Publishers Inc., San Francisco Hoos H, Süttzle T (2004) Stochastic local search: foundations & applications. Morgan Kaufmann Publishers Inc., San Francisco
21.
Zurück zum Zitat Ilić A, Urošević D, Brimberg J, Mladenović N (2010) A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. Eur J Oper Res 206(2):289–300 MathSciNetCrossRef Ilić A, Urošević D, Brimberg J, Mladenović N (2010) A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem. Eur J Oper Res 206(2):289–300 MathSciNetCrossRef
22.
Zurück zum Zitat Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. The IBM research symposia series. Springer, New York, pp 85–103 CrossRef Karp RM (1972) Reducibility among combinatorial problems. In: Complexity of computer computations. The IBM research symposia series. Springer, New York, pp 85–103 CrossRef
23.
Zurück zum Zitat Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. Kluwer Academic Publishers, Norwell CrossRef Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. Kluwer Academic Publishers, Norwell CrossRef
24.
Zurück zum Zitat Laguna M, Gortázar F, Gallego M, Duarte A, Martí R (2014) A black-box scatter search for optimization problems with integer variables. J Glob Optim 58(3):497–516 MathSciNetCrossRef Laguna M, Gortázar F, Gallego M, Duarte A, Martí R (2014) A black-box scatter search for optimization problems with integer variables. J Glob Optim 58(3):497–516 MathSciNetCrossRef
25.
Zurück zum Zitat Love RF, Morris JG, Wesolowski GO (1988) Facilities location: models and methods. Elsevier Science Publishing Co., New York MATH Love RF, Morris JG, Wesolowski GO (1988) Facilities location: models and methods. Elsevier Science Publishing Co., New York MATH
26.
Zurück zum Zitat Lü Z, Hao JK, Glover F (2011) Neighborhood analysis: a case study on curriculum-based course timetabling. J Heuristics 17(2):97–118 CrossRef Lü Z, Hao JK, Glover F (2011) Neighborhood analysis: a case study on curriculum-based course timetabling. J Heuristics 17(2):97–118 CrossRef
27.
Zurück zum Zitat Makedon FS, Papadimitriou CH, Sudborough IH (1985) Topological bandwidth. SIAM J Algebr Discret Methods 6(3):418–444 MathSciNetCrossRef Makedon FS, Papadimitriou CH, Sudborough IH (1985) Topological bandwidth. SIAM J Algebr Discret Methods 6(3):418–444 MathSciNetCrossRef
28.
Zurück zum Zitat Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., New York MATH Martello S, Toth P (1990) Knapsack problems: algorithms and computer implementations. John Wiley & Sons, Inc., New York MATH
29.
Zurück zum Zitat Martí R, Duarte A, Laguna M (2009) Advanced scatter search for the max-cut problem. INFORMS J Comput 21(1):26–38 MathSciNetCrossRef Martí R, Duarte A, Laguna M (2009) Advanced scatter search for the max-cut problem. INFORMS J Comput 21(1):26–38 MathSciNetCrossRef
30.
Zurück zum Zitat Martí R, Reinelt G, Duarte A (2012) A benchmark library and a comparison of heuristic methods for the linear ordering problem. Comput Optim Appl 51(3):1297–1317 MathSciNetCrossRef Martí R, Reinelt G, Duarte A (2012) A benchmark library and a comparison of heuristic methods for the linear ordering problem. Comput Optim Appl 51(3):1297–1317 MathSciNetCrossRef
33.
Zurück zum Zitat Moscato P (1993) An introduction to population approaches for optimization and hierarchical objective functions: a discussion on the role of tabu search. Ann Oper Res 41(1–4):85–121 CrossRef Moscato P (1993) An introduction to population approaches for optimization and hierarchical objective functions: a discussion on the role of tabu search. Ann Oper Res 41(1–4):85–121 CrossRef
34.
Zurück zum Zitat Pantrigo JJ, Martí R, Duarte A, Pardo EG (2012) Scatter search for the cutwidth minimization problem. Ann Oper Res 199(1):285–304 MathSciNetCrossRef Pantrigo JJ, Martí R, Duarte A, Pardo EG (2012) Scatter search for the cutwidth minimization problem. Ann Oper Res 199(1):285–304 MathSciNetCrossRef
35.
Zurück zum Zitat Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237–244 CrossRef Papadimitriou CH (1977) The Euclidean travelling salesman problem is NP-complete. Theor Comput Sci 4(3):237–244 CrossRef
36.
Zurück zum Zitat Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Dover, Mineola MATH Papadimitriou CH, Steiglitz K (1998) Combinatorial optimization: algorithms and complexity. Dover, Mineola MATH
37.
Zurück zum Zitat Pardo EG, Mladenović N, Pantrigo JJ, Duarte A (2013) Variable formulation search for the cutwidth minimization problem. Appl Soft Comput 13(5):2242–2252 CrossRef Pardo EG, Mladenović N, Pantrigo JJ, Duarte A (2013) Variable formulation search for the cutwidth minimization problem. Appl Soft Comput 13(5):2242–2252 CrossRef
38.
Zurück zum Zitat Peiró J, Corberán A, Martí R (2014) GRASP for the uncapacitated r-allocation p-hub median problem. Comput Oper Res 43:50–60 MathSciNetCrossRef Peiró J, Corberán A, Martí R (2014) GRASP for the uncapacitated r-allocation p-hub median problem. Comput Oper Res 43:50–60 MathSciNetCrossRef
39.
Zurück zum Zitat Ruiz R, Stützle T (2006) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049 CrossRef Ruiz R, Stützle T (2006) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. Eur J Oper Res 177:2033–2049 CrossRef
41.
Zurück zum Zitat Sánchez Oro J, Pantrigo JJ, Duarte A (2014) Combining intensification and diversification strategies in VNS. An application to the vertex separation problem. Comput Oper Res 52, Part B(0):209–219. Recent advances in variable neighborhood search Sánchez Oro J, Pantrigo JJ, Duarte A (2014) Combining intensification and diversification strategies in VNS. An application to the vertex separation problem. Comput Oper Res 52, Part B(0):209–219. Recent advances in variable neighborhood search
42.
Zurück zum Zitat Talbi EG (2009) Metaheuristics: from design to implementation. Wiley, Hoboken CrossRef Talbi EG (2009) Metaheuristics: from design to implementation. Wiley, Hoboken CrossRef
44.
Zurück zum Zitat Wu Q, Hao JK, Glover F (2012) Multi-neighborhood tabu search for the maximum weight clique problem. Ann Oper Res 196(1):611–634 MathSciNetCrossRef Wu Q, Hao JK, Glover F (2012) Multi-neighborhood tabu search for the maximum weight clique problem. Ann Oper Res 196(1):611–634 MathSciNetCrossRef
Metadaten
Titel
Variable Neighborhood Descent
verfasst von
Abraham Duarte
Jesús Sánchez-Oro
Nenad Mladenović
Raca Todosijević
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-07124-4_9

Premium Partner