变邻域搜索算法综述  

Review of Variable Neighborhood Search Algorithm

作　　者：董红宇[1,2] 黄敏[1,2] 王兴伟[1] 郑秉霖[2] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004 [2]教育部流程工业综合自动化重点实验室(东北大学),辽宁沈阳110004

出　　处：《控制工程》2009年第S2期1-5,13,共6页Control Engineering of China

基　　金：国家自然科学基金资助项目(70671020;70431003;70721001;60673159);新世纪优秀人才支持计划基金资助项目(NCET-05-0295;NCET-05-0289);高等学校博士学科点专项科研基金资助项目(20070145017;20060145012);国家高技术研究发展计划基金资助项目(2006AA01Z214)

摘　　要：变邻域搜索算法(Variable Neighborhood Search,VNS)作为一种新的元启发式算法,已初步成功地用于解决优化问题,尤其是对于大规模组合优化问题效果良好。对VNS的扩展研究层出不穷,并将其成功地应用到旅行商问题、车辆路径问题、调度、图着色等问题中。简述了经典的元启发式算法,并依次论述了优化问题,VNS算法起源,VNS算法原理,VNS算法分析,扩展的VNS分析,VNS在初始解构造、邻域结构构造、局部搜索和停止准则几个方面的改进方法,针对不同版本的VNS归纳了其在各种优化问题应用情况。基于对改进的VNS的分类,从算法自身研究角度和实际应用角度提出了未来研究方向。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.

关 键 词：变邻域搜索算法 精确启发式算法 元启发式算法 精确算法 组合优化 连续优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]