VNS

Variable Neighborhood Search (VNS) is a metaheuristic for solving combinatorial and global optimization problems. It was introduced in the 1990s by Hansen and Mladenović as a flexible framework that enhances local search by systematically changing the neighborhood structures around a current solution. The central idea is that different neighborhoods provide complementary views of the search space, helping to escape local optima.

The method starts with an initial feasible solution and a predefined set of neighborhoods. At each step, a solution is perturbed using a randomly chosen operator from the current neighborhood (the shaking step) and then improved by a local search within that neighborhood. If the resulting solution improves the incumbent, it becomes the new incumbent and the search restarts with the first neighborhood. If not, the algorithm switches to the next neighborhood in the predefined sequence. The process repeats until a stopping criterion is met, such as a time limit or a maximum number of iterations.

VND, or Variable Neighborhood Descent, is a deterministic specialization of VNS where a sequence of neighborhoods is explored without the stochastic shaking between them. VNS generalizes this idea by incorporating diversification through shaking and by allowing a wider variety of neighborhood structures and local search procedures.

Applications of VNS span a range of combinatorial problems, including the travelling salesman problem, vehicle routing, scheduling, facility location, knapsack and cutting-stock problems, graph partitioning, and many engineering optimizations. Strengths of VNS include its conceptual simplicity, flexibility, and effectiveness across diverse problem classes. Its performance relies on the design of meaningful neighborhoods and appropriate stopping criteria, while computational cost can be driven by the number and complexity of local searches conducted.