Review of Variable Neighborhood Search Algorithm

A new metaheuristic algorithm,the variable neighborhood search(VNS),has been successfully used to solve optimizaiton problem,especially for the largescale combinational optimization problem.Many versions of VNS have been proposed and adopted to solve the TSP,VRP,scheduling,graph coloring and so on.The brief description of optimizaiton problem and metaheuristics are firstly introduced,then,the origin of VNS,the priciple of VNS,the ananysis of VNS,extensions of of VNS are propoved respectively,and many common methods to improve the VNS are proposed from four aspects,the initial solution design,neighborhood design,local search and stopping conditions.The applications of improved VNS are also introduced.Based on the classification of VNS,the future research about VNS is proposed,including applications and improvements.