变邻域搜索算法综述

董红宇^1,2，黄敏^1,2，王兴伟¹，郑秉霖²

1. 东北大学信息科学与工程学院2. 教育部流程工业综合自动化重点实验室(东北大学)

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

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