Variable neighborhood search: Principles and applications

被引:1266
作者
Hansen, P
Mladenovic, N
机构
[1] Gerad, Montreal, PQ H3T 2A7, Canada
[2] Ecole Hautes Etud Commerciales, Montreal, PQ H3T 2A7, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
heuristic; metaheuristic; variable neighborhood search; VNS;
D O I
10.1016/S0377-2217(00)00100-4
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
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. (C) 2001 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:449 / 467
页数:19
相关论文
共 66 条
[1]  
Anderberg M. R., 1973, CLUSTER ANAL APPL, DOI DOI 10.1016/C2013-0-06161-0
[2]  
[Anonymous], 1995, OPT DAYS MONTR
[3]  
[Anonymous], 1997, Tabu Search
[4]   A NOTE ON SOLVING LARGE P-MEDIAN PROBLEMS [J].
BEASLEY, JE .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1985, 21 (02) :270-273
[5]  
Bentley J. L., 1992, ORSA Journal on Computing, V4, P387, DOI 10.1287/ijoc.4.4.387
[6]   A NEW ADAPTIVE MULTI-START TECHNIQUE FOR COMBINATORIAL GLOBAL OPTIMIZATIONS [J].
BOESE, KD ;
KAHNG, AB ;
MUDDU, S .
OPERATIONS RESEARCH LETTERS, 1994, 16 (02) :101-113
[7]  
Brimberg J., 1996, STUD LOCATIONAL ANAL, V10, P1
[8]  
BRIMBERG J, 2000, OPERATIONS RES, V48
[9]  
Brinkmann G, 1996, J GRAPH THEOR, V23, P139, DOI 10.1002/(SICI)1097-0118(199610)23:2<139::AID-JGT5>3.3.CO
[10]  
2-1