求解护士排班问题的变邻域搜索算法

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