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

Solving nurse rostering problem based on hybrid integer programming and evolutionary algorithm

作　　者：欧阳骥[1] 林伟佳[2] 卓晓燕[2] 秦勇[1] 黄翰[2] 

机构地区：[1]东莞理工学院计算机学院,广东东莞523808 [2]华南理工大学软件学院,广州510006

出　　处：《计算机应用研究》2015年第12期3660-3664,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(61370102);广东省自然科学基金资助项目(S2012010010613);珠江科技新星项目(2012J2200007);东莞市高等院校科研机构科技计划项目(2011108102015;2012108102035;2012108102007)

摘　　要：护士排班问题(nurse rostering problem,NRP)是多约束条件下的NP难优化问题,目前大多数算法难以在计算时间和求解质量之间达到较好的平衡。针对此难题,提出一种基于整数规划(integer programming,IP)与演化优化(evolutionary optimization algorithm,EA)混合的一种算法机制,分两步对护士排班问题进行求解。第一步采用IP算法求解简化后的NRP,得到一个高质量的初始解;第二步则在初始解的基础上采用演化算法进一步优化而得到更优的结果。实验结果表明,以中国式护士排班问题为例,对比IP+VNS(variable neighborhood search)和hybrid EA等四类主流算法,IP+EA混合算法能求得更高质量的解。因此,在此类NP难问题的求解上,IP+EA混合算法比其他四类算法具有更明显的优势和效果。NRP is a NP-hard optimization problem with multiple constraints. Many algorithms are difficult to make a balance between computational time and solution quality to solve NRP problems. For this problem, this paper proposed a hybrid algorithm framework of integer programming and evolutionary optimization to solve NRP problems following two steps. First, it used the integer programming to solve a brief NRP to produce high-quality initial solutions. Second, it optimized the initial solutions by evolutionary algorithm in advance to achieve an improvement. The experimental results of Chinese NRP indicate that the hybrid IP ＋ EA algorithm is able to obtain solutions of higher quality than IP ＋ VNS, hybrid EA and other two popular algorithms. Therefore, on solving this type of NP-hard problem, the hybrid IP ＋ EA algorithm is more efficient than the other four algorithms.

关 键 词：护士排班问题 混合算法 整数规划 演化算法 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]