Variable neighborhood search (VNS), proposed by Mladenović & Hansen in 1997, is a metaheuristic method for solving a set of combinatorial optimization and global optimization problems. It explores distant neighborhoods of the current incumbent solution, and moves from there to a new one if and only if an improvement was made. The local search method is applied repeatedly to get from solutions in the neighborhood to local optima. VNS was designed for approximating solutions of discrete and continuous optimization problems and according to these, it is aimed for solving linear program problems, integer program problems, mixed integer program problems, nonlinear program problems, etc.
Introduction VNS systematically changes the neighborhood in two phases: firstly, descent to find a local optimum and finally, a perturbation phase to get out of the corresponding valley. Applications are rapidly increasing in number and pertain to many fields: location theory, cluster analysis, scheduling, vehicle routing, network design, lot-sizing, artificial intelligence, engineering, pooling problems, biology, phylogeny, reliability, geometry, telecommunication design, etc. There are several books important for understanding VNS, such as: Handbook of Metaheuristics, 2010, Handbook of Metaheuristics, 2003 and Search methodologies, 2005. Earlier work that motivated this approach can be found in
Davidon, W.C. Fletcher, R., Powell, M.J.D. Mladenović, N. and Brimberg, J., Mladenović, N. Recent surveys on VNS methodology as well as numerous applications can be found in 4OR, 2008 and Annals of OR, 2010.
Definition of the problem Define one deterministic optimization problem with
where S, X, x, and f are the solution space, the feasible set, a feasible solution, and a real-valued objective function, respectively. If S is a finite but large set, a combinatorial optimization problem is defined. If S = R n {\displaystyle {S=R^{n}}} , there is continuous optimization model. A solution x ∗ ∈ X {\displaystyle {x^{*}\in X}} is optimal if
Exact algorithm for problem (1) is to be found an optimal solution x*, with the validation of its optimal structure, or if it is unrealizable, in procedure have to be shown that there is no achievable solution, i.e., X = ∅ {\displaystyle X=\varnothing } , or the solution is unbounded. CPU time has to be finite and short. For continuous optimization, it is reasonable to allow for some degree of tolerance, i.e., to stop when a feasible solution x ∗ {\displaystyle x^{*}} has been found such that
Some heuristics speedily accept an approximate solution, or optimal solution but one with no validation of its optimality. Some of them have an incorrect certificate, i.e., the solution x h {\displaystyle x_{h}} obtained satisfies
for some ε, though this is rarely small. Heuristics are faced with the problem of local optima as a result of avoiding boundless computing time. A local optimum x L {\displaystyle x_{L}} of problem is such that
where N ( x L ) {\displaystyle N(x_{L})} denotes a neighborhood of x L {\displaystyle x_{L}}
Description According to (Mladenović, 1995), VNS is a metaheuristic which systematically performs the procedure of neighborhood change, both in descent to local minima and in escape from the valleys which contain them. VNS is built upon the following perceptions:
A local minimum with respect to one neighborhood structure is not necessarily a local minimum for another neighborhood structure. A global minimum is a local minimum with respect to all possible neighborhood structures. For many problems, local minima with respect to one or several neighborhoods are relatively close to each other. Unlike many other metaheuristics, the basic schemes of VNS and its extensions are simple and require few, and sometimes no parameters. Therefore, in addition to providing very good solutions, often in simpler ways than other methods, VNS gives insight into the reasons for such a performance, which, in turn, can lead to more efficient and sophisticated implementations. There are several papers where it could be studied among recently mentioned, such as (Hansen and Mladenović 1999, 2001a, 2003, 2005; Moreno-Pérez et al.;)
Local search
… excerpt ends here. Continue reading the full article.
