Abstract: Variable neighborhood search algorithm is effective for the nurse rostering, and the perturbation method used in it has significant effect on its performance. In order to improve the satisfaction of nurses in the nurse rostering problem, an Improved Variable Neighborhood Search (IVNS) algorithm was proposed. The algorithm used three neighborhood structures, when using any neighborhood could not improve the current solution further, a method for perturbing the current optimal solution was designed: firstly, two days in the rostering period were randomly selected, then a group of nurses were selected and their shifts in these two days were exchanged under the restriction of hard constraints. Comparison experiments with a Hybrid Variable Neighborhood Search (HVNS) algorithm were carried out on the benchmarks provided by the first international nurse rostering competition in 2010, and the results in the Sprint-early, Medium-early and Long-early instance groups show that, the optimal value of the IVNS algorithm is not inferior to HVNS at least, and its average value is superior to HVNS; the maximum variance of IVNS algorithm is 0.72, which means the fluctuation range is small, and the solution performance is stable. The IVNS disturbance program makes small disturbance to the existing project, and the current local optimal value can effectively jump out, enhancing the optimization ability of variable neighborhood search algorithm. Compared with HVNS algorithm, its performance is better.

Key words: combinatorial optimization, meta-heuristic algorithm, variable neighborhood search, nurse rostering, perturbation method

摘要： 变邻域搜索算法是求解护士排班问题的一个有效算法，其扰动方法对算法性能有显著影响。为提高护士排班问题中护士的满意度，提出一个改进的变邻域搜索(IVNS)算法。该算法使用了三种邻域结构，而且当使用任意的邻域都不能进一步改进当前解时，设计了一个对当前最优解进行扰动的方法，即在排班期间内随机地选择两天，在不违反硬性约束的条件下选出一组值班护士并交换他们在这两天中的班次。在2010年举行的第一次全球护士排班大赛提供的一组公共测试集上与一个混合变邻域搜索(HVNS)算法进行了比较，在Sprint-early、Medium-early和Long-early组算例上的结果表明，IVNS算法的最优值至少不劣于HVNS，而平均值均优于HVNS;IVNS算法的最大方差为0.72，波动范围小，求解性能稳定。IVNS的扰动方案对现有方案的扰动较小，能有效跳出当前局部最优，增强变邻域搜索算法的优化能力，与HVNS算法相比，其求解性能更优。

关键词: 组合优化, 元启发式算法, 变邻域搜索, 护士排班, 扰动方法