Abstract
Variable neighborhood descent (VND) is a local search-based heuristic which performs a deterministic exploration of a fixed set of neighborhood structures. Its success is based on the simple fact that different neighborhood structures usually have different local minimum. Thus, the local optima trap problem may be eventually solved by deterministic change of neighborhoods. VND can be used as a local search routine, and, therefore, it could be used within other metaheuristics. In this chapter we discuss typical problems that arise when designing VND: 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 considering the traveling salesman problem.
Abraham Duarte
Full Professor
Abraham Duarte is Full Professor in the Computer Science Department at the Rey Juan Carlos University (Madrid, Spain). He has done extensive research in the interface between computer science, artificial intelligence, and operations research to develop solution methods based on Computational Intelligence (metaheuristics) for practical problems in operations-management areas such as logistics and supply chains, telecommunications, decision-making under uncertainty and optimization of simulated systems.
Jesús Sánchez-Oro
Associate Professor
Associate Professor at the Computer Science Department, being one of the senior researchers of the Group for Research on Algorithms For Optimization GRAFO.