Variable neighborhood search (VNS), proposed by Mladenović, Hansen, 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.
Contents
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
- Davidson, 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
A solution
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.,
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
Heuristics are faced with the problem of local optima as a result of avoiding boundless computing time. A local optimum
where
Description
According to (Mladenovic, 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 neighbourhood structure is not necessarily a local minimum for another neighbourhood 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´c 1999, 2001a, 2003, 2005; Moreno-Pérez et al.;)
Local search
A local search heuristic is performed through choosing an initial solution x, discovering a direction of descent from x, within a neighbourhood N(x), and proceeding to the minimum of f(x) within N(x) in the same direction. If there is no direction of descent, the heuristic stops; otherwise, it is iterated. Usually the highest direction of descent, also related to as best improvement, is used. This set of rules is summarized in Algorithm 1, where we assume that an initial solution x is given. The output consists of a local minimum, also denoted by x, and its value. Observe that a neighbourhood structure N(x) is defined for all x ∈ X. At each step, the neighbourhood N(x) of x is explored completely. As this may be timeconsuming, an alternative is to use the first descent heuristic. Vectors
Algorithm 1: Best improvement (highest descent) heuristic
Function BestImprovement(x) 1: repeat 2: x' ← x 3: x←argmin_{f (y)}, y∈N(x) 4: until ( f (x) ≥ f (x')) 5: return xAlgorithm 2: First improvement (first descent) heuristic
Function FirstImprovement(x) 1: repeat 2: x' ← x; i←0 3: repeat 4: i←i+1 5: x←argmin{ f (x), f (x^i)}, x^i ∈ N(x) 6: until ( f (x) < f (x^i) or i = |N(x)|) 7: until ( f (x) ≥ f (x')) 8: return xLet one denote
One will also use the notation
In order to solve problem by using several neighbourhoods, facts 1–3 can be used in three different ways: (i) deterministic; (ii) stochastic; (iii) both deterministic and stochastic. We first give in Algorithm 3 the steps of the neighbourhood change function which will be used later. Function NeighbourhoodChange() compares the new value f(x') with the incumbent value f(x) obtained in the neighbourhood k (line 1). If an improvement is obtained, k is returned to its initial value and the new incumbent updated (line 2). Otherwise, the next neighbourhood is considered (line 3).
Algorithm 3: – Neighborhood change
Function NeighborhoodChange (x, x', k) 1: if f (x') < f(x) then 2: x ← x' // Make a move 3: k ← 1 // Initial neighborhood 4: else 5: k ← k+1 // Next neighborhoodWhen VNS does not render good solution, there are several steps which could be helped in process, such as comparing first and best improvement strategies in local search, reducing neighborhood, intensifying shaking, adopting VND, adopting FSS, and experimenting with parameter settings.
The Basic VNS (BVNS) method (Mladenovic and Hansen 1997) combines deterministic and stochastic changes of neighbourhood. Its steps are given in Algorithm 4. Often successive neighbourhoods
Algorithm 4: Basic VNS
Function VNS (x, kmax, tmax ); 1: repeat 2: k ← 1; 3: repeat 4: x' ←Shake(x, k) /* Shaking */; 5: x'' ← FirstImprovement(x' ) /* Local search */; 6: x ←NeighbourhoodChange(x, x'', k) /* Change neighbourhood */; 7: until k = k_max ; 8: t ←CpuTime() 9: until t > t_max ;VNS variants
The basic VNS is a first improvement descent method with randomization. Without much additional effort, it can be transformed into a descent-ascent method: in NeighbourhoodChange() function, replace also x by x" with some probability, even if the solution is worse than the incumbent. It can also be changed into a best improvement method: make a move to the best neighbourhood k* among all k_max of them. Another variant of the basic VNS can be to find a solution x' in the “Shaking” step as the best among b (a parameter) randomly generated solutions from the kth neighbourhood. There are two possible variants of this extension: (1) to perform only one local search from the best among b points; (2) to perform all b local searches and then choose the best. In paper (Fleszar and Hindi) could be found algorithm.
Extensions
Applications
Applications of VNS, or of varieties of VNS are very abundant and numerous. Some fields where it could be found collections of scientific papers:
Conclusion
VNS implies several features which are presented in Hansen and Mladenovic and some are presented here:
- Simplicity: VNS is simple, clear and universally applicable
- Precision: VNS is formulated in precise mathematical definitions
- Coherence: all actions of the heuristics for solving problems follow from the VNS principles
- Effectiveness: VNS supplies optimal or near-optimal solutions for all or at least most realistic instances
- Efficiency: VNS takes a moderate computing time to generate optimal or near-optimal solutions
- Robustness: the functioning of the VNS is coherent over a variety of instances
- User friendliness: VNS has no parameters, so it is easy for understanding, expressing and using
- Innovation: VNS is generating new types of application
- Generality: VNS is inducing to good results for a wide variety of problems
- Interactivity: VNS allows the user to incorporate his knowledge to improve the resolution process
- Multiplicity: VNS is able to produce a certain near-optimal solutions from which the user can choose;
Interest in VNS is growing quickly, evidenced by the increasing number of papers published each year on this topic (10 years ago, only a few; 5 years ago, about a dozen; and about 50 in 2007). Moreover, the 18th EURO mini-conference held in Tenerife in November 2005 was entirely devoted to VNS. It led to special issues of IMA Journal of Management Mathematics in 2007, European Journal of Operational Research (http://www.journals.elsevier.com/european-journal-of-operational-research/), and Journal of Heuristics (http://www.springer.com/mathematics/applications/journal/10732/) in 2008.