考虑临时床位的病床联合分配问题*

周晓鸣 叶春明 王 爽

（1.上海理工大学 上海 200082）（2.江苏大学 镇江 212013）

1 引言

1.1 问题的由来

手术室的调度包括了很多范围，不仅仅局限于手术室内。由于手术后创口的愈合以及麻醉的恢复都需要较长的一段时间，因此引申出了手术后的病床管理。病房管理的目的就是为了接受完手术以及做术前准备等待手术的患者提供更加舒适、合理的环境，以及能够最大化地利用有限的空间使更多的患者入住以获得更高的经济效益［3］。

病房管理主要包括住院管理、病床管理、卫生、饮食等［4］。其中病床管理是造成目前医院供不应求的主要因素，因此本文主要研究病床管理即本章的病床分配问题的研究。

1.2 病床分配问题的研究现状

对于整个医疗调度的研究，国外都要早于国内，病床的资源调度问题也不例外。相比较国外已经取得了一定的成果并且已应用到实际管理中，国内在此方面的研究还处于探索阶段。

Handyside 等对择期患者和急诊患者使用病床的比例分配问题做出了综述［5］。在这之前，Young等着重从计算患者的平均使用病床时间等多种角度研究，来控制患者人数以缓解紧急床位需求问题［6］。有了之前研究的基础，Chavis 等使用仿真的技术方式研究了紧急情况下的床位需求，针对每日平均住院率以及紧急使用床位率进行模拟，并以此预测了排班对于床位使用率的影响［7］。

Bettinelli 等使用了语言编码经过计算机仿真后得到医疗系统规划的新数值，这个研究也为医院的扩张计划给予了理论上的指引。目前已被某重点医院在实际病床管理中实现了［8］。

Harrois 等对住院系统的管理现状写了比较全面的综述，并提出了迭代分配模型［9］；Lizotte发表的一篇综述中提出了能够用于定期静态调度系统模型以及持续动态调度系统［10］。

Harper 等提出了病床占用率和住院拒绝率两个指标，他们认为医院作为一套完整的系统，其内部是一个动态的、复杂的非线性结构，因此对于病床的管理必须在不确定的并且资源受限的情况下［11］。

Tutuncu 等在该领域研究了较长一段时间后，首次把迪杰斯特拉算法和遗传算法应用于短期确定性的病床分配问题中，优化了每个时间段内的床位类型。他们认为手术室资源的优化和控制是为了满足患者的需求，提高资源的使用效率。但是，服务行业的需求变化过快，之前的数据不一定符合当下的情况，需求和预测不一定能够得到准确的结果［12］。

病床的优化调度分配问题，国外学者的研究已领先很多，而国内的研究尚处于起步阶段。直到近五六年，有关病床分配和患者入院安排问题的相关文献才渐渐丰富起来，研究的难度和宽度也日益上升［13］。近来，有学者将病床分配问题与收益管理思想相结合，用收益管理的存量控制方法实现对病床的分配。该论文运用了两阶段容量控制模型，开启了床位分配问题中运用收益管理思想的先河［14］。

综上所述，无论是研究还是应用，在病床分配问题上我国都落后于一些发达国家。因此，有必要吸取他们的经验和成果，结合我国实际情况进行探索［15］。就目前已有文献来看，大多都局限于某家医疗系统内部，尚未有病床联合调度的先例。

1.3 问题描述

在我国经济和科技的飞速发展以及医疗技术的迅猛进步下，人们对于医院的依赖也变得日益严重。因此，近年来国内相关部门投入了大量的精力研究关于怎样能够更充分地利用病床资源的问题，并且已有了一些显著的效果。然而由于我国人口基数过大、研究起步较晚，想要短时间内解决好此类问题还存在较大难度［16］。就目前研究而言，几乎所有研究都局限于某一家医院内尝试各种模型以及各类算法来寻求最优解［17］。然而，现实存在的问题是某些医院每天人数超过最大负荷，甚至出现提前三天排队、夜里到医院排队、黄牛代排队等一系列社会问题，而有些医院的患者量却远低于其能接纳人数的上限，造成了很多医疗资源的浪费。造成这种情况发生的原因也有很多，比如医师的水平、医院的规模、医院的宣传力度和口碑以及医院的交通便利程度等［18～20］。综上种种因素，能够发现，完全可以考虑将两家甚至多家医院的病床联合调度。

经过研究，本文在已有的研究的基础上考虑了联合调度的思想，为避免一些现实中难以预测的问题，本文并非直接用两家医院直接联合调度。而是引入了“临时床位”，即在某家医院已有的固定床位以外，假设了存在一套医疗环境相当，并且数量不限的临时床位。

2 模型的描述

模拟手术病人使用病床的过程，每位病人依次到达，一共有三种情况：

1）病人到达医院后，存在已开设且空余并符合要求的床位，将该病人安排于此病床；

2）病人到达医院后，若符合要求的病床已有病人使用，或者该病床的上一位病人离开时间小于45min，则将此病人依次安放在下一个符合要求的病床；

3）病人到达医院后，若已无符合要求的床位空余，或无床位距上一位病人离开时间大于等于45min，则将该病人安排在临时床位处。本文不考虑临时床位个数。

本题只考虑病人-床位的分配，要求尽可能多地分配病人到合适的病床，并且在此基础上最小化被使用床位的数量。

2.1 模型假设

1）有限时间段假设。一个医院中的患者住院出院活动属于连续性离散事件，前一时段患者的分配状态为当前工作的初始条件。本文假设以2018年1月20日的一昼夜为时间窗。

2）信息完备假设。床位分配问题的研究对象是患者和病床，其中患者信息包括进入和离开床位时刻，床位占用时间，性别以及病情的传染性等。病床信息包括病床的数量，病床的男女分类，以及该患者分配前病床的初始状况，研究时需要的信息均假设已知。

3）床位容量假设。现有多数床位分配问题的研究是基于容量允许假设，即医院床位资源是充足的，不考虑资源受限问题。即对于任意一个患者，总存在至少一个可用的床位。本文中将床位分为固定床位和临时床位两种，即在有限的固定床位无法满足的前提下才会启用临时床位且数量不受限制。

4）进入该医院里的患者只能分配到与之属性相吻合的床位。

5）每位患者的住院和出院两个时刻必须在同一床位，期间不能挪移别处。

6）分配在同一床位的两个患者之间的空档时间必须大于或等于45min。

7）本文所有问题只考虑手术患者。

8）假设所有患者按既定时间手术、恢复，没有延误。

9）不考虑患者的异质性。

10）不考虑手术室到病床的距离。

11）本文涉及所有时间以分钟为单位。

2.2 模型建立

问题优化模型的建立是基于一定的前提和假设条件的，以便抓住问题的主要矛盾，忽略对问题本质没有影响或影响不大的因素。病人-病床分配问题的研究基于有限时间段假设、信息完备性假设，以及床位容量状况假设等。

第一阶段优化模型：

第二阶段优化模型：

式（1）表示目标函数取安排在固定床位的病人占总病人数比值的最大值；式（2）表示唯一性约束，即一位病人只能安排在一个床位，且中途不能挪移；式（3）和（4）对yi，j，k的取值作出定义；式（5）表示独占性约束，即一个病床在同一时段内只能被安排一位病人，但是允许不同的病人分批安排在同一病床；式（6）表示两位连续安排在同一病床的病人之间的空档时间不小于45min；式（7）和（8）表示每位病人只能按照既定的男/女、长期/短期、传染/不传染等功能属性停在与之属性相吻合的床位；式（9）表示对各变量的约束。式（10）表示所有被使用床位的空闲时间总和，对于一般的分配问题，在每种分配方式中，共有N+M 个空闲时间，其中N 为病人数，M 为床位数。每个病人恰好对应一个紧前床位空闲时间Si，共N 个。每个床位最后各有一个空闲时间Sk无病人对应，共M 个，所以目标函数可以表示为式（11）。该公式计算比前者复杂度低，因此选择式（11）为目标函数；式（12）～（19）与第一阶段约束类似；式（20）～（22）表示对目标函数变量的定义；式（23）表示第二阶段模型建立在第一阶段的基础上。

2.3 模型的符号说明

模型中的各符号的含义说明如表1所示。

表1 符号说明

3 算法设计

本题采用两阶段优化分步优化方法建立模型，第一阶段模型设立被分配在固定床位的患者数与患者总数的比值最大为目标函数，在此基础上设立固定床位的空闲时间最小化作为第二阶段的目标函数。在确定的患者数的基础上保证被使用的床位的使用效率最大（即空闲时间最小）即可说明使用了最少量的床位。选用遗传算法对其进行求解，具体步骤如下。

3.1 编码

这里我们采用简单易用的整数编码方法。对于有n 个患者的病床分配问题，将n 个患者随机赋予0 或1，0 表示该患者被安排至临时床位，1 表示该患者被安排至固定床位。例如有10 个患者的分配问题，｛0，1，1，0，1，0，1，1，0，1｝就是一个合法的染色体，表示第2，3，5，7，8，10 个患者被安排在固定床位，而1，4，6，9号患者被安排在临时床位。

3.2 产生初始群体和适应度函数

利用遗传算法寻优，就是要找到适应度最大的染色体，本章模型要求尽可能多的分配患者到固定的床位，因此可以直接以分配到固定床位的患者的总数量作为适应度函数进行，函数表达式为式（24）。

通过随机的方式产生初始群体，采用轮盘赌选择的方法进行选择。

3.3 遗传算子设计

1）采用正交交叉方式进行交叉算子设计。记当前的第K 代种群为先，然后对种群进行两两配对，种群依据预先产生的正交阵对进行交叉，得到种群Bk。

2）按照提前约定的变异概率对交叉后得到的种群Bk中的每个体Xi进行变异。

3）变异后产生的种群中最差的S 个体需要更新操作，并得的种群为Dk。

3.4 终止条件

遗传算法本身具有较大的随机性，因此使用几条基于启发式规则作为条件实现终止。

1）若算法迭代到5000代，则终止算法。

2）若某一代群体中的染色体平均适应度与当代的最佳染色体适应度的比值大于0.9，那么算法终止。

3）若最佳染色体连续保持200 代，则终止算法。

3.5 算法流程图

根据上述算法的步骤，作出算法流程图如图1所示。

4 实验结果

4.1 参数设置

使用python 语言实现该算法的求解过程。首先设计了多组实验对算法的交叉率和变异率进行选择，一般情况下，交叉率的取值范围为0.6～0.9，变异率的取值范围为0.01～0.1。本文经过多次迭代，选择变异率为0.07，交叉率为0.8。

图1 基于经典遗传算法的流程图

4.2 实例求解

为验证模型和算法的实用性，现以某大型三甲医院的手术间资源数据为依据进行测试。数据如下：时间窗为一周，该医院每周平均预约住院人数为303（将其进行编号1～303），医院目前已有固定床位（代号T）30 张，临时床位（代号S）37 张。患者的类型及住院预计时间等数据均已知。

在Intel Core i5-4590 CPU，主频3.30GHz，内存8GB 的操作系统下，使用python 语言，参数设置为交叉率0.8，变异率0.07，运行得出目标函数的最优解为：接待患者223人，使用固定床位28张，临时床位32 张，T 和S 的床位的使用数目和被使用床位的平均使用率（床位占用时间比率），通过Python程序的算法实现，得出其线状图如图2所示。

图2 被使用床位平均使用率

为证明此模型的合理性和求解算法的实用性，随机调取了该医院过去一年内十个时间窗的预约人数和实际安排住院人数的柱状图，如图3 所示；以及十个时间窗的床位平均使用率如图4（图中最右边点横坐标表示实验组）所示。由图3 及4 可以看出，与过去相比该实验组的患者入住率以及床位的使用率都有所增加，验证了本章模型的实用性。

图3 患者入院率对比图

图4 床位平均使用率

5 结语

本章针对患者住院信息已知的情况下，如何将固定病房床位与临时床位联合调度的问题进行了讨论。根据固定床位与临时床位的不同特点，建立了以尽可能安排最多的患者住院为第一优先级，以最大化被使用床位的使用率为第二优先级的目标函数，结合病床的使用特点进行约束，以保证在尽可能不浪费医疗资源的基础上最大化接受住院患者数量。使用了解决此类调度问题最经典的遗传算法进行求解，分析了算法中各参数的选择对求解结果的影响，并求出最优解。随机选取了该医院以往的安排情况与求解结果进行对比，发现此结果都有较明显的优势，证明了该模型和算法的有效性和实用性。

本章的研究还存在一定的局限性，例如对时间窗的选择不够长、假设的许多因素也许比现实完美、目标函数的没有考虑经济因素等。其中对研究对象的选择范围是本文研究的主要因素，考虑了带有临时床位的联合调度即相当于两家病床的联合调度，因此考虑n 家医院的手术室资源联合调度成为下一步研究的重点。