变邻域搜索算法综述

作者：董红宇; 黄敏; 王兴伟; 郑秉霖

来源：控制工程, 2009, S2: 1-5+13.

DOI：10.14107/j.cnki.kzgc.2009.s2.023

• 变邻域搜索算法
• 精确启发式算法
• 元启发式算法
• 精确算法
• 组合优化
• 连续优化 variable neighborhood search
• mathheuristics
• metaheuristics
• exact methods
• combinationnal optimization
• continuous optimization

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

• 单位
  流程工业综合自动化国家重点实验室; 东北大学