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

J4 ›› 2013, Vol. 35 ›› Issue (5): 149-153.

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

胡廉民1,2,张九华1,常永耘3,黄翰3

(1.乐山师范学院物理与电子工程学院,四川乐山 614000;2.华南理工大学计算机科学与工程学院,广东广州 510006;
3.华南理工大学软件学院,广东广州 510006)

收稿日期:2012-05-03 修回日期:2012-08-16 出版日期:2013-05-25 发布日期:2013-05-25
基金资助:
国家自然科学基金资助项目(61003066)；教育部博士点基金资助项目(20090172120035)

Genetic algorithm with variable neighborhood search
to solve nurse rostering problem

HU Lianmin1,2,ZHANG Jiuhua1,CHANG Yongyun3,HUANG Han3

(1.Department of Physics and Electrical Engineering,Leshan Teachers College,Leshan 614000;
2.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006;
3.School of Software Engineering,South China University of Technology,Guangzhou 510006,China)

Received:2012-05-03 Revised:2012-08-16 Online:2013-05-25 Published:2013-05-25

摘要/Abstract

摘要：

护士排班问题是一类多约束多陷阱问题，传统的计算方法和启发式算法往往很难找到其最优解。采用基于遗传算法GA和可变邻域搜索算法VNS的混合策略对护士排班问题进行了求解。其中，GA算法通过添加判断准则和控制策略来有效生成新的护士排班表，而VNS策略则实现初始化、约束条件下的杂交变异和解空间的分离等运算。最后，对20组基准护士排班问题进行了求解，并将求解结果与国际上近年提出的IP+VNS方法进行了比较，实验表明，在相同的计算时间内，GA+VNS算法的求解效果明显更优。

关键词: 护士排班问题；遗传算法；可变邻域搜索算法

Abstract:

Nurse rostering problem is one of multiconstrained problems with many traps. Therefore neither traditional approaches nor heuristic methods can find the optimal solution for the problem. This paper studied and solved the nurse rostering problem by applying a hybrid method that combines genetic algorithm (GA) and variable neighborhood search (VNS). In this method, GA generates a new nurse roster by adding judgment rules and control policies. VNS algorithm operates on the steps of initialization, crossover and mutation with constraints, and separation of solution space. Finally, the experiment results of 20 nurse rostering problems indicate that, within the same runtime, the method of GA+VNS outperforms the method of IP+VNS which is internationally known as the newest approach.

Key words: nurse rostering problem;genetic algorithm;variable neighborhood search

胡廉民1,2,张九华1,常永耘3,黄翰3. 求解护士排班问题的可变邻域搜索遗传算法[J]. J4, 2013, 35(5): 149-153.

HU Lianmin1,2,ZHANG Jiuhua1,CHANG Yongyun3,HUANG Han3. Genetic algorithm with variable neighborhood search
to solve nurse rostering problem [J]. J4, 2013, 35(5): 149-153.