Authors: | Hansen, Pierre Mladenović, Nenad |
Title: | Variable neighborhood search: Principles and applications | Journal: | European Journal of Operational Research | Volume: | 130 | Issue: | 3 | First page: | 449 | Last page: | 467 | Issue Date: | 1-May-2001 | Rank: | M22 | ISSN: | 0377-2217 | DOI: | 10.1016/S0377-2217(00)00100-4 | Abstract: | Systematic change of neighborhood within a possibly randomized local search algorithm yields a simple and effective metaheuristic for combinatorial and global optimization, called variable neighborhood search (VNS). We present a basic scheme for this purpose, which can easily be implemented using any local search algorithm as a subroutine. Its effectiveness is illustrated by solving several classical combinatorial or global optimization problems. Moreover, several extensions are proposed for solving large problem instances: using VNS within the successive approximation method yields a two-level VNS, called variable neighborhood decomposition search (VNDS); modifying the basic scheme to explore easily valleys far from the incumbent solution yields an efficient skewed VNS (SVNS) heuristic. Finally, we show how to stabilize column generation algorithms with help of VNS and discuss various ways to use VNS in graph theory, i.e., to suggest, disprove or give hints on how to prove conjectures, an area where metaheuristics do not appear to have been applied before. |
Publisher: | Elsevier | Project: | ONR, Grant N00014-95-1-0917 NSERC, Grant OGPOO 39682 FCAR, Grant 32EQ 1048 |
Show full item record
SCOPUSTM
Citations
1,579
checked on Dec 20, 2024
Page view(s)
212
checked on Dec 21, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.