求解多阶段护士排班问题的带权禁忌搜索算法  

Weighted tabu search for multi-stage nurse rostering problem

作　　者：苏宙行 王卓[1] 吕志鹏[1] 

机构地区：[1]华中科技大学计算机科学与技术学院智慧计算与优化实验室,武汉430074

出　　处：《中国科学：信息科学》2016年第7期834-854,共21页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61370183;61100144);2013教育部新世纪优秀人才支持计划资助项目

摘　　要：本文研究了多阶段护士排班问题,该问题由第2届国际护士排班竞赛提出,在医疗优化领域具有重要的意义.针对多阶段护士排班问题,本文提出了一种带权禁忌搜索算法.该算法使用了3种互斥的简单邻域结构与一种复合邻域结构,并根据其适应性动态调整搜索各邻域的概率.同时,通过调整各护士的惩罚权重来实现搜索过程中集中性与疏散性的平衡.为了应对各个独立的阶段缺乏全局信息的问题,提出了一种对全局约束的近似评估策略.算法还针对自适应的邻域选择策略,以减少多种邻域的整体计算开销为目标设计了邻域评估的缓存策略,进一步提升了算法的执行效率.算法在竞赛使用的60个算例上的计算结果表明了算法的有效性,最终在第2届国际护士排班竞赛决赛中排名全球第4.此外,本文对算法中的关键要素进行了对比分析,表明了这些组成部分的方案选择和参数设置的合理性.This paper presents a study of the multi-stage nurse rostering problem, which was proposed in the Second International Nurse Rostering Competition. We propose a weighted tabu search algorithm for solving this rostering problem, which is a very important problem in healthcare optimization. The algorithm employs the following neighborhood structures： 3 structures that are exclusive to each other and 1 compound structure. The possibilities of selecting a neighborhood to search are tuned dynamically by the extent to which they are adaptive.Meanwhile, the balance between intensification and diversification during the search procedure is achieved by adjusting the weight of the penalty for each nurse. We address the problem caused by the lack of global information within each independent stage by proposing an approximate evaluation strategy for spanning constraints. The algorithm employs a cache for neighborhood move evaluation with the purpose of reducing the overall computational cost for the adaptive neighborhood selection strategy, which improves the efficiency of the algorithm further. The benchmark result of our algorithm on 60 instances from the competition shows good solving quality and ranks fourth in the final of the Second International Nurse Rostering Competition. Furthermore, we compare and analyze some key factors in the algorithm and demonstrate their rationality.

关 键 词：护士排班 禁忌搜索 时刻表规划 人员排班 元启发式 组合优化 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]