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

摘要

本文研究了多阶段护士排班问题,该问题由第2届国际护士排班竞赛提出,在医疗优化领域具有重要的意义.针对多阶段护士排班问题,本文提出了一种带权禁忌搜索算法.该算法使用了3种互斥的简单邻域结构与一种复合邻域结构,并根据其适应性动态调整搜索各邻域的概率.同时,通过调整各护士的惩罚权重来实现搜索过程中集中性与疏散性的平衡.为了应对各个独立的阶段缺乏全局信息的问题,提出了一种对全局约束的近似评估策略.算法还针对自适应的邻域选择策略,以减少多种邻域的整体计算开销为目标设计了邻域评估的缓存策略,进一步提升了算法的执行效率.算法在竞赛使用的60个算例上的计算结果表明了算法的有效性,最终在第2届国际护士排班竞赛决赛中排名全球第4.此外,本文对算法中的关键要素进行了对比分析,表明了这些组成部分的方案选择和参数设置的合理性.