Variable Neighborhood Search

Variable neighborhood search is a metaheuristic method for combinatorial and global optimization problems that works by systematically changing the neighborhood structure used to search around the current solution, rather than relying on a single fixed neighborhood the way a plain local search does. The algorithm alternates between a descent phase, in which an ordinary local search is run to find a local optimum within the current neighborhood, and a perturbation phase, in which the search jumps to a randomly chosen point in a different, typically larger neighborhood to escape that local optimum and explore a more distant region of the solution space; whenever this process finds an improved solution, the search resets around the new solution and the cycle of neighborhoods begins again. Nenad Mladenovic and Pierre Hansen proposed variable neighborhood search in 1997, and it has since been applied to problems including linear, integer, mixed integer and nonlinear programming, location theory, cluster analysis, scheduling, vehicle routing and network design.