一种用于集成医疗排程竞赛 2024 的混合解决方案方法
论文原始标题：A hybrid solution approach for the Integrated Healthcare Timetabling Competition 2024
论文作者：Authors: Daniela Guericke, Rolf van der Hulst, Asal Karimpour, Ieke Schrader, Matthias Walter
原始摘要：We report about the algorithm, implementation and results submitted to the Integrated Healthcare Timetabling Competition 2024 by Team Twente, which scored third in the competition. Our approach combines mixed-integer programming, constraint programming and simulated annealing in a 3-phase solution approach based on decomposition into subproblems. Next to describing our approach and describing our design decisions, we share our insights and, for the first time, lower bounds on the optimal solution values for the benchmark instances. We finally highlight open problems for which we think that addressing them could improve our approach even further.
翻译标题：一种用于集成医疗排程竞赛 2024 的混合解决方案方法
翻译摘要：我们报告了 Team Twente 提交到 2024 年集成医疗排程竞赛的算法、实现和结果，该团队在比赛中获得第三名。我们的方法基于将问题分解为子问题，结合了混合整数规划、约束规划和模拟退火的三阶段解决方案。除了描述我们的方法和设计决策外，我们还分享了我们的见解，并首次给出了基准实例的最优解值下界。最后，我们强调了一些我们认为可以通过解决它们来进一步改进我们方法的开放问题。
智能问答：
Q1: 这篇论文试图解决什么问题？
论文针对的是“综合医疗时间表竞赛 2024（IHTC 2024）”所提出的集成式医院排程问题。该问题将四个原本独立但相互耦合的决策合并在一个规划周期内：
患者入院日选择（patient admission day）
患者住院期间的病房分配（room assignment）
手术当日的手术室分配（operating-theater assignment）
各班次护士与病房间的照护指派（nurse-to-room assignment）
目标是在满足硬约束（容量、性别同病房、手术医生与手术室可用性等）的前提下，最小化由软约束带来的加权成本，包括：延迟入院、未排入的择期患者、手术室开启数量、医生跨台、护士超负荷、照护连续性差、技能不匹配、病房年龄差异等。
由于问题规模庞大，论文提出一种三阶段混合分解算法，将整体问题拆成四个子问题，并依次用混合整数规划（MIP）、约束规划（CP）与模拟退火（SA）求解，同时在四线程并行框架中维护解池，以在 10 分钟竞赛时限内获得高质量可行解，并首次给出各算例的下界。
Q2: 有哪些相关研究？
论文本身未设独立“Related Work”章节，但引言与结论部分给出了可直接追溯的文献脉络，可归纳为以下四类：
医院资源集成规划综述
Hulshof 等 (2012) [6]：系统梳理了 2000–2012 年运筹学在医疗规划中的分类体系，指出“床位-手术室-医护人员”应联合优化而非割裂。
Rachuba-Reuter-Thielen (2024) [10]：最新综述，强调“integrated planning in hospitals”仍是开放研究方向，并呼吁用分解/混合方法应对复杂度。
医疗排程竞赛与基准测试
Ceschia 等 (2025) [2]：IHTC 2024 官方竞赛报告，首次把“admission + room + theater + nurse”四元决策合并为公开基准，本文即在该框架下展开。
分解-混合求解策略
Benders (1962) [1]：经典 Benders 分解，本文在 4.6 节尝试用其改进护士指派 MIP，但报告“收效甚微”，从而佐证了该子问题之难度。
模拟退火在护士排班：Delahaye-Chaimatanan-Mongeau (2019) [3] 的综述被直接引用，本文 4.4 节 SA 设计（温度公式、概率选择、delta 评价）即以此为模板。
医疗人力与病房分配专题
OECD & European Commission (2024) [7] 与 Zapata 等 (2023) [12]：从宏观政策层面论证“老龄化-医护短缺”背景，为“为何必须集成优化”提供外部动因。
WHO (2025) [11]：医院在体系层面的核心协调角色，支持“医院级统一排程”而非科室级局部优化。
综上，本文位于“医院集成排程”这一新兴分支的最新节点：以 IHTC 2024 竞赛基准为问题载体，继承并扩展了 Hulshof-Rachuba 等人提出的联合优化理念，同时采用 Benders-SA-CP 混合范式来应对四元决策耦合带来的计算壁垒。
Q3: 论文如何解决这个问题？
论文提出一种三阶段、四子问题、混合算法并行框架来求解 IHTC 2024 的集成医疗排程问题。核心思想是“先分解、再协调、后提升”，并充分利用 4 线程并行与解池机制，在 10 min 竞赛时限内不断累积与改进可行解。流程概览如下（所有数学模型均按论文章节编号，方便对照）：
1. 预处理（第 3.4 节）
对每位择期/可选患者 $p$ 计算可入院日集合 $D_{adm}^p subseteq D$，剔除：
早于 release day
晚于 deadline
主管医生当日可用手术时长不足：$K_{surg}^{u(p),d} < T_{surg}^p$
延迟成本已高于“直接推迟”成本的日期
2. 三阶段主流程（图 2）
阶段t目标t主导技术t线程分配t关键机制
Phase 1t为“患者-入院日”变量计算护理成本下界 $ omega_{care}^{p,d} $ tMIPt1 线程跑 Admission MIP（$ rho = 0 $）n3 线程并行跑 Care-cost MIP（4.5 节）t把后期护士软约束（技能+连续性）提前折现为 $ omega_{care}^{p,d} $，供 Phase 2 目标函数调用
Phase 2t迭代求解四个子问题，快速生成大量完整可行解tMIP + CP + SAt4 线程动态分工（见图 2）t① Admission MIP（4.1 节）n② Room-assignment CP（4.2 节）n③ Theater-assignment MIP（4.3 节）n④ Nurse-assignment SA（4.4 节）
Phase 3t对 Phase 2 最优 4 条解精确重优化护士指派tMIPt4 线程各跑一个 Nurse MIP（4.6 节）t固定入院日与房间，只重排护士，目标仍含技能、连续性、超负荷三项软罚
3. 四个子问题详解
4.1 Patient-Admission MIP（主线模型）
变量
$x_{p,d} in {0,1}$：患者 $p$ 是否第 $d$ 天入院
$z_{p,d} in {0,1}$：患者 $p$ 在第 $d$ 天是否住院（含后续停留）
$pi_p in {0,1}$：可选患者被推迟
$theta_{o,d} in {0,1}$：手术室 $o$ 第 $d$ 天是否开放
$epsilon_{d,s} geq 0$：护士班次 $s$ 当日超负荷下界
目标
$min sum_{p,d} (omega_{care}^{p,d} + omega_{delay}(d - d_{release}^p)x_{p,d} + omega_{unsched} sum_{p in P_{opt}} pi_p + omega_{wkld} sum_{d,s} epsilon_{d,s} + omega_{thea} sum_{o,d} theta_{o,d}$
硬约束
手术医生日容量：$sum_{p:u(p)=u} T_{surg}^p x_{p,d} leq K_{surg}^{u,d}$
手术室日容量：$sum_{o} K_{thea}^{o,d} theta_{o,d} geq sum_{p} T_{surg}^p x_{p,d}$
总床日上限（可缩减 $rho$）：$sum_{p} z_{p,d} leq sum_{r} K_{room}^r - rho$
护士负荷下界：$epsilon_{d,s} + sum_{n} K_{nurse}^{n,d,s} geq sum_{p} T_{pat}^{p,d,s}$
实现技巧
每找到一个可行 $x$ 即送入解池，并标记对应 $rho$；n若连续 6 个同 $rho$ 解都无法在 Room CP 中找到可行房派，则 $rho leftarrow rho + 1$ 重跑。
4.2 Patient-Room Assignment（CP 模型）
输入：已固定入院日 $d(p)$ 及住院区间 $D_{present}^p$
决策：$x_{p,r} in {0,1}$；辅助性别、年龄变量 $y_{r,d,g}$, $alpha_{r,d,a}$, $Delta_{r,d}$
目标：最小化每日病房年龄差总和 $sum_{r,d} Delta_{r,d}$
硬约束：单性别/日/房、房容量、年龄差定义
求解：Google OR-Tools CP，双线程并行搜索，收集多个可行房派解。
Q4: 论文做了哪些实验？
论文围绕 IHTC 2024 发布的全部算例，共进行了 “竞赛限时实验” 与 “延长时间实验” 两套对比测试，并在赛后补充了 小规模实例与长周期实例 的扩展实验。所有实验均在同一台笔记本（Intel i7-1355U，16 GB）上完成，代码开源于 GitHub [4]。具体实验内容如下：
1. 实验设置
项目t竞赛版t延长版
单实例运行次数t1 次（竞赛规则允许 10 次取优，但作者仅跑 1 次以验证稳健性）t同样 1 次
总时限t10 mint60 min
阶段时限分配tPhase1+2 共 300 s，Phase3 300 st同左 ×10
子组件时限tCP 5 s / 次，Theater 1 s / 天，SA 15 s 或 5000 次无改进t同左 ×10
随机种子tSA 固定 seed=0，其他因多线程与时间限制仍非确定t同左
2. 算例覆盖
公开集 i01–i30（30 例，用于选决赛队）
隐藏集 m01–m30（30 例，用于决赛排名）
赛后补充集
small01–small09（9 例，床位 ≤20，周期 1 周）
l35_1–l35_6、l42_1–l42_6、l49_1–l49_6、l56_1–l56_6（共 24 例，床位 35–56，周期 3–8 周）
3. 观测指标
目标函数值 Obj（软罚加权和）
与“竞赛官网最佳解”的相对 Gap
作者自己算出的 Lower bound（Phase-1 对偶界，$rho=0$）
解对应的 $rho$ 值（房间容量缩减量，反映 Admission 阶段保守程度）
8 类软约束分项成本（CoC、Unsched、Exc-WL、Open-OTs、Delay、Age-Mix、Skill-Match、Surgeon-Transfer）
10 min → 60 min 的 Improvement（%）
4. 主要结果（摘要）
公开集：平均 Gap 1.9%（10 min）→ 1.4%（60 min）；下界平均比最佳解低 6.4%。
隐藏集：平均 Gap 3.0%（10 min）→ 2.3%（60 min）；下界平均比最佳解低 7.9%。
大实例（i13、i17、m27、m28 等）Gap 仍可达 10–22%，主要瓶颈：
Admission 阶段因 $rho>0$ 被迫放弃过多择期患者
Nurse 子问题连续性-负荷权衡导致软罚高
small 实例：9 例中有 3 例在 10 min 内找不到可行解，说明分解流程无反馈时易陷入死区。
长周期实例（l56 系列）：60 min 运行可把 Gap 从 16–28% 压到 12–25%，但仍有 2 例未能在 1 h 内获得可行解（表 8 中标记 ∞）。
5. 事后分析实验
将 10 min 与 60 min 的分项成本并列（表 9 vs 表 10），确认：
延长运行主要削减 Unsched、Exc-WL、Skill-Match 三项
Delay 成本反而偶尔上升，系线程随机性与搜索路径不同所致
对比 Lower bound 与 Best known 发现： nurse-related 软罚下界偏松，提示后续研究需更紧的护理成本估算。
Q5: 有什么可以进一步探索的点？
以下列出 8 个可直接落地的后续研究方向，按“建模-算法-数据-评价”四条线组织，并给出可验证的量化指标，方便在下一轮竞赛或实际医院系统中落地。
1. 双向反馈机制（建模线）
问题：Phase-2 一旦 Room-CP 判不可行，只能被动提高 Admission-MIP 的 $rho$，无法定位“哪几类患者组合”导致房间性别/容量死锁。
探索：
用 Irreducible Infeasible Set (IIS) 从 CP 模型提取最小冲突患者集合 → 生成“冲突割平面”回切到 Admission-MIP，形成 Benders-like 反馈。
量化指标：每跑一次反馈，$rho$ 的增加量 $Deltarho downarrow$，Unscheduled 患者数 $downarrow$，Gap $downarrow$。
2. 护理成本紧下界（建模线）
问题：Phase-1 的 $omega^{care}_p,d$ 仅考虑单患者，忽略同房间患者对技能/连续性的耦合。
探索：
以“房间-日”为单元，预先解多患者技能覆盖问题，得到 room-based care cost；
用列生成或 Dantzig-Wolfe 把“护士-患者子集”定价问题嵌入 Admission-MIP。
量化指标：Lower bound 提高百分比；10 min 内根节点 Gap 缩小百分比。
3. 连续性-负荷权衡割平面（算法线）
问题：Phase-3 Nurse-MIP 的 LP 松弛通过“平均护士分配”同时获得低连续性成本与低负荷成本，导致分支定界效率极低。
探索：
设计 convexity-or-cardinality cuts：对任意患者子集，限制其照护护士数 $leq k$ 时，必须承担的最小超负荷量；
或采用 lifted cover inequalities 针对“技能-班次-房间”三维覆盖结构。
量化指标：Root gap $downarrow$，MIP 求解节点数 $downarrow$，Phase-3 改进幅度 $uparrow$。
Q6: 总结一下论文的主要内容
论文提出一套三阶段混合分解算法，在 10 分钟竞赛时限内求解 IHTC 2024“患者入院-病房-手术室-护士”一体化排程问题，并首次给出实例下界。核心内容可概括为：
问题
联合决定入院日、房间、手术室与护士班次，满足硬容量与性别同屋等约束，最小化延迟、未入院、护士超负荷、技能不匹配、连续性差等软罚。
思路
将四元决策拆成四个子问题 → 按“Admission → Room → Theater → Nurse”顺序求解，并用并行解池持续传递与改进可行解。
三阶段流程
Phase 1：四线程并行计算护理成本下界 $omega_{care}^{p,d}$，为 Admission 提供“前瞻”信息。
Phase 2：
① Admission-MIP（Gurobi）生成多组入院方案；
② Room-CP（OR-Tools）按天派房，若连续无解则递增容量缩减参数 $rho$；
③ Theater-MIP（按天独立）派手术室；
④ Nurse-SA（模拟退火）快速加护士。
Phase 3：对前阶段最优 4 条解，用精确 Nurse-MIP 重优化护士指派。
关键技术
容量缩减反馈 $rho$、回调式解池、双线程 CP、按天并行 Theater、SA 加权概率邻域、Barrier 解 LP 松弛。
实验
公开/隐藏/补充共 93 个实例，10 min 平均 Gap 2–3%，60 min 再降 0.5–1%；
给出所有实例下界，验证 nurse-related 软罚下界仍偏松；
small 实例 3/9 不可行，提示需反馈机制。
贡献
首次在竞赛环境下实现 MIP+CP+SA 混合并行框架；
提供可复现代码与下界基准；
指出“无反馈 + 护士权衡”两大开放问题，为后续研究划定方向。
阅读全文 →
来源：Arxiv2025-11-07 10:14:04 UTC
