基于整数规划与演化优化混合的护士排班问题求解算法

摘要

护士排班问题(nurse rostering problem,NRP)是多约束条件下的NP难优化问题,目前大多数算法难以在计算时间和求解质量之间达到较好的平衡.针对此难题,提出一种基于整数规划(integer programming,IP)与演化优化(evolutionary optimization algorithm,EA)混合的一种算法机制,分两步对护士排班问题进行求解.第一步采用IP算法求解简化后的NRP,得到一个高质量的初始解;第二步则在初始解的基础上采用演化算法进一步优化而得到更优的结果.实验结果表明,以中国式护士排班问题为例,对比IP+ VNS(variable neighborhoodsearch)和hybrid EA等四类主流算法,IP+ EA混合算法能求得更高质量的解.因此,在此类NP难问题的求解上,IP+ EA混合算法比其他四类算法具有更明显的优势和效果.