Algorithms for physician scheduling under the online and offline combined service mode based on machine learning
-
摘要: 线上线下联合的医疗服务模式已经成为我国大型医院普遍采用的新型医疗服务模式，为了优化大型医院在此类模式下的医生资源配置，本文研究考虑切换成本的医生排班问题。针对此问题，建立考虑服务水平限制的医生排班马尔可夫决策过程模型，并设计近似动态规划算法对马尔可夫决策过程高效求解。进一步，考虑患者高度时变到达以及医疗服务时长等多维不确定性，基于合作医院的实际数据，构建数据驱动的循环神经网络模型，提出基于数据驱动的线上线下患者排队系统的性能评估方法。数值实验显示，所提出的方法能够降低医生总工作时长，并有效控制患者等待时间，保证系统的高效运行。本文研究结果可为大型医院合理配置线上线下医疗资源提供理论依据和决策支持。Abstract: The online and offline combined medical service mode has become a new medical service mode generally adopted by large hospitals in China. Under this mode, large hospitals need to allocate physicians to online and offline services, and arrange online and offline scheduling plans for physicians while considering the switching of physicians between the two services. To address this problem, a Markov decision process model for physician scheduling with service level constraints was developed and an approximate dynamic programming algorithm was designed to solve the Markov decision process with high efficiency. Furthermore, considering multi-dimensional uncertainties such as highly time-varying patient arrival and service hours, a data-driven recurrent neural network was constructed based on the real-life data of the cooperative hospital as a performance evaluation method for the online and offline queueing systems. Numerical experiments show that the proposed methods can reduce the total working hours of physicians, effectively control the waiting time of patients, and ensure the high-efficiency operation of the system.
-
近年来，伴随互联网的发展，在线医疗服务在全世界范围内蓬勃发展，形成与传统线下就诊并行的医疗服务方式[1-2]。在线医疗是借助无线互联等技术，通过患者与医生间的实时通信，完成远程医疗服务 [3]。在线医疗服务使医患双方均得到收益。患者通过在线医疗能够降低交通成本，减少在医院的排队时间，降低感染风险；医院则可以辐射更大的患者群体，缓解线下医疗资源挤兑[4]。截至2022年我国具有
2700 多家互联网医院，开展在线诊疗服务超过2590 万人次[5]，其中约85%为依托实体医院构建的线上医疗平台。相对应地，大量医院形成了线上线下联合的医疗服务模式，同时为患者提供在线和传统线下的医疗服务[6]，即科室的部分医生被安排到传统线下诊室工作，部分医生在特定时段提供线上诊疗服务。在这样的服务模式下，医院面临着一个重要难题，即如何有效确定每位医生的工作班次，以在不同时段内将有限的医生资源合理分配到线上和线下诊室。然而，医生的统筹排班对医院而言并不容易，这是因为同时考虑线上线下联合医疗服务模式下的医生排班问题具有特定的难点。首先，线上和线下医疗服务系统都具有很强的随机性和时变性。尽管很多医院推行门诊预约制，但由于患者的到达存在不守时、爽约以及部分患者不经预约直接挂号就诊等现象，线上和线下服务系统的患者到达具有较强的随机性。伴随随机性特征，患者到达还表现出高度时变性，存在显著的患者到达高峰期和低谷期。在如此复杂的随机时变系统中，优化医生线上线下排班以提升服务水平、提升系统运行效率非常困难。进一步，线上、线下服务过程存在显著的差异。线下问诊普遍采用医患之间“一对一”的方式，而典型的线上问诊中医生患者之间采用“一对多”的方式，即一名医生同时为多位患者服务[7]。线上问诊中，医生在多个线上患者的交流界面内切换，同时服务多位患者。这导致线上线下患者感受等有显著的差别。如何结合2种服务方式的不同特点，保证服务的公平与质量，成为线上线下医生服务调度难点。最后，高效的排班需要部分医生在线上、线下间进行动态切换，这导致医生调度比传统仅考虑线下的问题更为困难。针对以上难点，本文对线上线下联合服务模式下的医生资源进行排班优化，以提高患者就诊体验，降低医生工作强度。
目前，医生排班问题的研究主要面向线下医疗场景[8-9]。Brunner等[10]对麻醉科医生柔性排班方案展开优化，决策每位医生的班次开始时间、持续时间以及是否加班，并设计分支定价算法进行求解。Stolletz等[11]设计了一种集合覆盖模型，该方法预先确定所有可行的班次类型，然后将医生分配到各个班次中，以匹配各时段波动的医生需求。Wang等[12]针对带回流的急诊服务系统建立离散时间解析模型近似患者等待时间，采用禁忌搜索算法求解相关医生排班问题。Sinreich等[13]通过2种迭代启发式方法与仿真相结合，以最小化患者平均停留时间为目标，求解急诊科室内的最优医生工作班次。Liu等[14]针对患者随机到达的情况，利用稳态排队模型近似的方法计算患者平均等待时间，设计变邻域搜索算法求解医生排班问题。Zaerpour等[15]考虑医生服务新患者速率随其服务时长而递减的特征，以最小化患者总等待时间为目标，建立医生排班的随机规划模型，使用样本均值近似和L-shaped算法求解。祖漫漫[16]基于时间序列模型进行患者需求预测，将其转换为医生能力需求约束，在此基础上建立多目标的医生排班模型，采用分层序列法求解。王铖恺等[17]考虑新冠疫情期间发热门诊的特殊情况，利用逐点稳态流近似对排队系统建模，结合Benders分解与列生成算法高效求解医生排班问题。兰绍雯[18]针对医生资质与服务类型的匹配关系，提出了计划与调配协同的变邻域搜索算法，确定医生人员配置计划表。目前针对线上医生排班问题的研究较少。相关研究集中在探讨患者如何选择线上或线下服务[6, 19]、研究在线分诊对患者的引导作用[20]以及线上和线下医疗服务质量对患者就医决策的影响[21]等方面。面向线上线下联合医疗服务模式下的相关问题尚处于起步阶段。除医生排班问题外，如何合理配置资源匹配时变需求同样也是教务排课问题所关注的内容。Hossain等[22]考虑课程与教室、教师、学生等多元匹配关系，设计基于粒子群的优化算法最大化教务排课满意度。宋婷等[23]通过多类分类器根据排课问题特征对排课问题进行分类，根据分类设计相应迭代局部搜索算法求解。
本文针对该新型服务模式下的医生排班问题进行研究，建立了综合考虑患者平均停留/等待时间、医生工作时间以及加班时间的马尔可夫决策过程模型，利用近似动态规划算法求解排班方案；进一步，提出了基于数据驱动的循环神经网络模型以评估服务系统性能。研究对于提升诊疗效率、缓解医生的工作负荷，具有现实意义。
1. 医生排班问题
本文聚焦线上线下联合医疗服务模式，研究如何将有限的医生分配到线上、线下诊室中，并对线上线下服务的医生进行工作排班，为到达患者提供服务。该问题以最小化同科室内所有医生总工作时间为目标，面向各时段的患者等待时间、医生工作规则等约束，决策每位医生在计划周期内的工作班次数量、每个班次的具体工作时间以及所服务患者类型。依据本研究在上海合作医院的调研情况和实际数据，对所研究的问题定义如下文所述。
1.1 服务过程假设
本文研究一天的医生排班问题，一天的工作时间被划分为|T|个工作时段，每个时段的长度为∆（例如0.5 h或者1 h），一天的全部工作时段用集合T={1, 2, …, |T|}表示。研究考虑线上和线下诊室中患者候诊和服务的不同，如图1所示。线下门诊中，患者随机到达，挂号后在候诊区排队等待接受医生服务，患者遵循先到先服务的规则接受服务。当一名医生空闲，则队列最前的患者被此医生开始一对一的医疗问诊服务，完成后离开系统。设定每个时段t内的线下患者到达服从参数为
$\gamma_t^1 $ 的泊松过程，每位患者的服务时间服从参数为μ1的指数分布，即对线下患者排队就诊通过Mt/M/ct排队模型加以建模[14]。在线上问诊中，患者首先通过手机、网页等挂线上就诊号，进入系统在线等待队列，当有医生可为其服务则进入该医生在线诊室，进行在线服务，完成服务后离开系统[24]。设定每个时段t内的在线患者到达服从参数为$\gamma_t^2 $ 的泊松过程。需要注意的是和线下服务不同，由于线上问诊难以完全实时交流，患者的响应可能存在滞后现象，线上医生和患者之间的问诊并非一对一模式，而是一般采用一对多的模式，即一名医生的线上诊室中可以同时有多名患者[7]。当一名患者准备相关材料（例如上传病例、图片等），医生可以和线上诊室的其他患者交流以提供服务，从而提升医生工作时间的利用率。但是一般线上诊室会设定最大“同时服务”的患者数目，以保证服务的质量。本文设定一名医生最多同时为K名在线患者提供服务[25]。显然，一名医生对每位患者的服务速率受到其同时服务患者的影响，依据调研和已有文献研究[3]，本文设定每位线上患者的服务时间服从参数为μ2(k)的指数分布，其中k表示医生同时服务的患者总数。出于表达方便，下文将线上医生“同时服务k个患者”称为此医生“处于k层级”。线上诊室中采取“层级最低优先”的原则分配医生，即优先将等待队列队首患者分配给层级最低的医生进行服务，这是因为分配前该医生正在服务的患者数最少，负担最轻。如果每位医生都处于最大阈值K级，则新到达的患者处于等待队列中，不能进入任何一个医生的线上诊室[3]。
图 1 线上与线下诊室排队系统示意Fig. 1 Schematic diagram of queueing system in the online and offline clinic
下载:
全尺寸图片
1.2 医生工作规则
在一天的工作时间内，医生被安排在线上或者线下对患者提供服务。每位医生每天的工作日程由一个或者多个班次组成。一个班次是一段连续工作的时间，班次的开始与结束时间均可以灵活调整。医生上下班工作需要遵守以下规则：
1) 各时段线上、线下都至少有一名医生上班。
2) 一个医生每天最多安排一个线上诊室的班次与一个线下诊室的班次。
3) 一个医生在诊室j中的班次长度至少为
$d_j^{\min} $ 个时段，至多为$d_j^{\max} $ 个时段，j=1和j=2分别表示线上和线下诊室。4) 一个医生在2个班次之间的最短休息时间为1个时段。
5) 医生上班、下班都只能在一个时段的开始时发生。
6) 在每天的最后一个时段，工作的医生需要服务完所有患者后才能下班，因此可能产生加班的工作时间。
本文研究的问题目标是在保证服务水平的前提下降低医院的运营成本。保证医疗服务水平显然是必要的，但是由于线上、线下服务模式的差别，其服务水平的衡量方式有显著区别。对线下医疗服务，一般采用线下患者的“平均等待时间”体现服务水平；对线上医疗服务，服务水平指标则为线上患者的“平均停留时间”，即患者从进入到离开线上排队系统的总共时间的均值[3]。线上服务更关注“平均停留时间”，是因为在患者线上服务过程中，一位医生可能同时服务多名患者，随着同时服务患者数量越多，导致对单个患者的服务速度变慢，降低每名患者的服务满意度，平均停留时间能对该降低进行更为准确的表征；而“平均等待时间”无法对此进行衡量。本文将各时段到达的线上患者的平均停留时间和线下患者的平均等待时间的阈值上限分别设定为SM和WM。除了服务水平，医院关注其运营成本，本文设定此成本由医生的正常工作时间和加班时间加权构成，这也是所研究问题的优化目标。
2. 问题模型构建
首先，本文对一个有限周期内的医生排班进行优化，在服务过程假设中根据医生上下班的特点，将一天的工作时间分为了|T|个时段。医生只在时段开始时上下班，系统需要在每个时段开始时决策每位医生在该时段内是否上班。因此，整个问题是有限时域、离散时间的。时段t开始时，系统需要根据当前系统内的医生工作时长和患者等待时间等状态信息St，决策时段t内的医生工作Wt。时段t+1开始时的状态只取决于时段t时的状态和决策，符合马尔可夫性质。因此，以上问题可建模为有限时域内的离散时间马尔可夫决策过程（discrete-time Markov decision process, DTMDP）。每个时段为DTMDP中的每个阶段。在各时段开始时，运营者观察系统中已有的状态并做出决策。DTMDP的组成要素有状态、动作和状态转移。
2.1 系统状态
系统的状态是基于每个时段开始时对系统的观察。在时段t开始时，状态St定义为(H, Q, N, L, M)，其中H, Q和N表示各医生的工作状态，L和M则表示整个系统内的患者状态，其分别由以下变量组成：
1) Hi,j,t−1：到时段t−1末为止，医生i在诊室j的连续工作时间。
2) Qi,t−1：在时段t−1中，医生i所工作的诊室序号（若该医生休息，则序号为0）。
3) N j,t',t−1：到时段t−1末为止，在时段t'在诊室j工作的医生数量。
4) Lt−1,t'：到时段t−1末为止，在时段t'到达的线上患者的平均停留时间。
5) Mt−1,t'：到时段t−1末为止，在时段t'到达的线下患者的平均等待时间。
系统的初始状态定义为S0=(0, 0, 0, 0, 0)。
2.2 动作集合
各时段的动作决定了医生在该时段的工作状态。设定二元变量Wi,j,t表示医生i在时段t内是否在诊室j工作（j∈J={0,1,2}，其中j=1和j=2分别表示在线上和线下诊室工作；j=0表示医生休息）。所选动作需满足医生的排班规则，可行动作空间表示为
$$ \displaystyle\sum\limits_{j \in J} {{W_{i,j,t}}} = 1,\forall i \in I,t \in T $$ (1) $$ \begin{gathered}W_{i,0,t}=1, \\ Q_{i,t-1}=0,H_{i,1,t-1} > 0\text{ , }H_{i,2,t-1} > 0, \\ \forall i\in I,t\in T\end{gathered} $$ (2) $$ \begin{gathered} {W_{i,0,t}} + {W_{i,j,t}} = 1, \\ {Q_{i,t - 1}} = 0,{H_{i,j,t - 1}} = 0,\;\;{H_{i,3 - j,t - 1}} > 0, \\ \forall i \in I,j \in \{ 1,2\} ,t \in T \end{gathered} $$ (3) $$ \begin{gathered} {W_{i,0,t}} + {W_{i,j,t}} = 1, \\ {Q_{i,t - 1}} = j,\;\; d_j^{\min } \leqslant {H_{i,j,t - 1}} < d_j^{\max }, \\ \forall i \in I,j \in \{ 1,2\} ,t \in T \end{gathered} $$ (4) $$ \begin{gathered} {W_{i,j,t}} = 1, \\ {Q_{i,t - 1}} = j,\;\; {H_{i,j,t - 1}} < d_j^{\min }, \\ \forall i \in I,j \in \{ 1,2\} ,t \in T \end{gathered} $$ (5) $$ \begin{gathered} {W_{i,0,t}} = 1, \\ {Q_{i,t - 1}} = j,\;\; {H_{i,j,t - 1}} = d_j^{\max }, \\ \forall i \in I,j \in \{ 1,2\} ,t \in T \end{gathered} $$ (6) 式(1)保证一个医生在时段t内只有一种工作状态。式(2)~(3)表明，假设医生i在时段t−1内休息，如果此医生已经在2个诊室内都工作过，则只能继续休息；如果其只在一个诊室内工作过，那么可以在另一诊室内工作或者继续休息。式(4)~(6)表示，假设医生i在时段t−1内在诊室j工作，若其累计工作时间处于
$[d_j^{\min},d_j^{\max}] $ 内，那么其可以休息或者继续工作；若累计工作时间小于最短时长，则只能继续工作；若工作时间等于最长时长，则只能休息。2.3 状态转移
假设时段t开始时的系统状态为St=(H, Q, N, L, M)。系统从2.2节中定义的可行动作空间中选取动作Wt=(Wi,j,t | i∈I, j∈J)，从状态St转移到状态St+1。向量H表示了每位医生在各个诊室中所工作的累计时段数。在时段t中系统通过统计每位医生是否正在工作来更新向量H。
$$ {H_{i,j,0}} = 0,\forall i \in I,j \in J $$ (7) $$ {H_{i,j,t}} = {W_{i,j,t}} \cdot \left( {{H_{i,j,t - 1}} + 1} \right),\forall i \in I,j \in J,t \in T $$ (8) $$ \begin{gathered} d_j^{\min } \leqslant {H_{i,j,t}} \leqslant d_j^{\max }, \\ {W_{i,j,t}} = 0,\;\; {H_{i,j,t}} > 0,\forall i \in I,j \in \{ 1,2\} ,t \in T \end{gathered} $$ (9) $$ \begin{gathered} d_{\min }^c \leqslant {H_{i,j,T}} \leqslant d_{\max }^c, \\ {H_{i,j,T}} > 0,\forall i \in I,j \in \{ 1,2\} \\ \end{gathered} $$ (10) 式(7)确保在第一个时段开始前，每位医生在各个诊室内工作的时段数为0。式(8)给出了H的具体更新公式。式(9)和(10)将H中的元素限定在最短连续工作时长与最长连续工作时长中。向量Q和N描述了每位医生在上一个时段的工作状态，它与上个时段动作W相关。
$$ {Q_{i,t}} = \displaystyle\sum\limits_{j \in J} {j{W_{i,j,t}}} ,\forall i \in I,t \in T $$ $$ {N_{j,t',t}} = {N_{j,t',t - 1}},\forall j \in J,t' < t,t \in T $$ $$ {N_{j,t,t}} = \displaystyle\sum\limits_{i \in I} {{W_{i,j,t}}} ,\forall j \in J,t \in T $$ 而对于向量L和M，并没有精确的状态转移公式，只能通过仿真得到。
$$ L{_{t,t'}} = {f_{{\text{simu}}}}\left( {L{_{t - 1,t'}},{W_t}} \right) \leqslant S_M,\forall t' < t,t \in T $$ (11) $$ M{_{t,t'}} = {f_{{\text{simu}}}}\left( {M{_{t - 1,t'}},{W_t}} \right) \leqslant {W_M},\forall t' < t,t \in T $$ (12) 2.4 贝尔曼方程
求解马尔可夫决策过程（Markov decision process，MDP）中最优决策的重要方法是贝尔曼方程，它表述了不同阶段状态价值间的递推关系。本文问题目标为最小化医院运营成本，由正常工作时间和加班时间加权组成，表示为
$ \displaystyle\sum\limits_{i \in I} {\displaystyle\sum\limits_{j = 1}^2 {\displaystyle\sum\limits_{t \in T} {{W_{i,j,t}}} } } + \alpha \displaystyle\sum\limits_{j = 1}^2 {o{t_j}} $ 。其中，前项表示各医生正常工作时段总数，后项为2个诊室内医生的加班时间之和，α为加班时间权重系数。因此DTMDP模型的贝尔曼方程为$$ \left\{ {\begin{array}{*{20}{l}} {V_T^*\left( {{S_T}} \right) = \mathop {\min }\limits_{{W_T} \in {A_T}\left( {{S_T}} \right)}\left\{ \displaystyle\sum\limits_{i \in I} {\displaystyle\sum\limits_{j = 1}^2 {{W_{i,j,T}}} } + \alpha \displaystyle\sum\limits_{j = 1}^2 {o{t_j}} \right\}} \\ V_t^*\left( {{S_t}} \right) = \mathop {\min }\limits_{{W_t} \in {A_t}\left( {{S_t}} \right)} \left\{ {\displaystyle\sum\limits_{i \in I} {\displaystyle\sum\limits_{j = 1}^2 {{W_{i,j,t}}} } + V_{t + 1}^*\left( {{S_{t + 1}}|{S_t},{W_t}} \right)} \right\}\\ 1 \leqslant t < T \end{array}} \right. $$ (13) 在得到以上贝尔曼方程后，需要据此进行最优排班的求解。动态规划是经典的求解思路，但考虑到维数爆炸和仿真的复杂性，其能求解的问题规模极为有限，需要设计更高效的排班求解和系统性能评估策略。
3. 近似动态规划
在动态规划中，对于阶段t开始时的状态St，需要求解贝尔曼最优方程式（13）以确定最优的动作Wt。在该方程中，At(St)表示动作Wt的可行空间，
${\displaystyle\sum\limits_{i \in I}} {\displaystyle\sum\limits_{j = 1}^2} {W_{i,j,t}} $ 表示系统处于状态St时采取动作Wt所产生的立即成本，St+1为系统处于状态St时采取动作Wt后转移到的新状态，而Vt+1(St+1)则是处于状态St+1时的状态价值函数。由于存在维数爆炸和仿真的复杂性，确定最优策略非常耗时，因此本文提出一种基于rollout算法的近似动态规划（approximate dynamic programming, ADP）方法对问题进行有效求解[26]。rollout算法采取了前向动态规划的结构，并在各阶段中通过启发式策略帮助评估每个动作的成本，从而选取最优的动作[27-28]。对于阶段t中的某个状态St，定义$ \hat V\left( {{S_{t + 1}}} \right) $ 为通过启发式策略估计的值，rollout算法选择最优动作的公式为$$ {\boldsymbol{W}}_t^* = \mathop {\arg \min }\limits_{{W_t} \in {A_t}\left( {{S_t}} \right)} \left\{ {\displaystyle\sum\limits_{i \in I} {\displaystyle\sum\limits_{j = 1}^2 {{W_{i,j,t}}} } + \hat V_{t + 1}^*\left( {{{\boldsymbol{S}}_{t + 1}}|{{\boldsymbol{S}}_t},{{\boldsymbol{W}}_t}} \right)} \right\} $$ 总体算法框架如图2所示。在近似动态规划中，首先根据当前的状态St，生成所有可行的一步动作Wt。在此基础上通过启发式算法搜索每个动作Wt的后续最优策略，并将该后续策略的价值作为动作Wt价值的估算值，从而为每个阶段选取最优的动作。最后输出最优动作序列作为医生排班问题的最终解。
图 2 近似动态规划算法框架Fig. 2 Framework of approximate dynamic programming algorithm下载:
全尺寸图片
3.1 rollout算法
根据前视步数的不同，rollout算法可以分为one-step-rollout和multi-step-rollout。本文根据问题的性质选用了one-step-rollout算法，即当系统到达状态St，首先对所有可行动作展开评估。对于动作Wt，rollout算法调用启发式算法确定选定动作Wt后的最优策略π*(Wt)=(Wt+1, Wt+2, …, WT)。根据此最优策略计算得到动作Wt在当前阶段产生的直接价值
${\displaystyle\sum\limits_{i \in I}} {\displaystyle\sum\limits_{j = 1}^2} {W_{i,j,t}} $ 和状态St经过动作Wt转移到新状态St+1的价值$ \hat V_{t + 1}^*\left( {{S_{t + 1}}|{S_t},{W_t}} \right) $ ，从而选取最优动作。因此，对于状态St一共需要执行|At(St)|次启发式算法（|At(St)|为可行动作的数量）。特别地，当系统在阶段t末找不到可行动作时，表明系统在阶段t所选择的动作是不合适的。为了避免这种情况，系统将回退到阶段t−1末状态St−1，重新选择在阶段t的动作，前视多步直到阶段t+1。在计算得到系统在阶段t+1存在可行动作后，系统采用这一重新选取的动作。One-step-rollout算法的伪代码如下。输入 初始状态S0
输出 最优动作序列W
1） 将t初始化为0；
2） While t < T do
3） 根据启发式算法确定状态St下每个可行动作Wt的价值；
4） if 阶段t+1时存在可行动作then；
5）
$ {\boldsymbol{W}}_t^* = \mathop {\arg \min }\limits_{{W_t} \in {A_t}\left( {{S_t}} \right)} \left\{ {\displaystyle\sum\limits_{i \in I} {\displaystyle\sum\limits_{j = 1}^2 {{W_{i,j,t}}} } + \hat V_{t + 1}^*\left( {{{\boldsymbol{S}}_{t + 1}}|{{\boldsymbol{S}}_t},{{\boldsymbol{W}}_t}} \right)} \right\} $ 6） 根据St和Wt更新状态St+1和t；
7） else t ← max{0, t–1}；
8） End while
3.2 延迟接受的爬山算法
为了估算每个动作的成本，本文所提出的roll-out算法采用了启发式算法来生成可能的后续决策序列，从而得到每个动作所产生的立即成本与随后的状态价值
$ \hat V\left( {{{\boldsymbol{S}}_{t + 1}}} \right) $ 。给定状态St和动作Wt，通过启发式算法计算后续最优策略π*(Wt)=(Wt+1, Wt+2, …, WT)，该策略给定了时段t后各医生具体工作状况。结合状态St和最优策略π*(Wt)，即得到每个动作Wt的价值。本文采用基于延迟接受的爬山算法（late acceptance hill climbing，LAHC）作为rollout算法中的基础启发式算法[29]（即算法1中的步骤5)）。与传统爬山法不同，LAHC算法允许接受非改进的移动。在每次迭代中，LAHC算法在确定邻域最优解后，将其与解池中相应位置（迭代次数除以解池大小Lh的余数）的解进行比较，从而判断是否移动到该邻域最优解。以Vπ(Wt)(St)表示从状态St出发，按照策略π(Wt)所确定的医生排班的成本期望值。而LAHC算法的目标则在于选定单步前视的动作Wt后，求解得到最优的后续策略π*(Wt)。LAHC伪代码如下。
输入 决策前状态S和所选择的动作W
输出 动作的价值
1） 根据状态S和W生成初始策略π；
2） 计算初始策略的目标值C(π)；
3） 生成初始解池fv = C(π), v = 1, 2, …, Lh；
4） 初始化算法参数：I ← 0, Iidle ← 0；
5） While I ≤ ImaxIters or Iidle ≤ I * 0.02 do
6） 在π的邻域解中确定邻域最优解π*；
7） if C(π*) >= C(π) then
8） Iidle ← Iidle + 1；
9） else Iidle ← 0；
10） v ← I mod Lh；
11） if C(π*) < fv or C(π*) <= C(π) then
12） π ← π*；
13） if C(π) < fv then
14） fv ←C(π)；
15） I ← I + 1；
16） End while
3.2.1 初始解
当处于时段t时，LAHC算法需要根据当前的状态St和所选择的动作Wt生成初始解。初始解生成具体算法如下。1）检查医生i是否可以在阶段t+1以及随后阶段中工作：如果该医生在阶段t+1前已经完成了2个班次（一个为线上班次，一个为线下班次），则该医生不能够继续工作。否则，可以在阶段t+1以及随后阶段为该医生分配班次。2）如果所选择的动作Wt中该医生正在某个诊室上班，则将其班次长度延伸至最大时长djmax；如果所选择的动作Wt中该医生正在休息，则为其在随机诊室j内生成一个班次，具有随机的开始时间p和结束时间q。3）检查每个诊室在后续时段中是否至少有一个医生值班。如果没有，对在时段t内不工作的医生重新随机分配新的班次，直到满足约束。
3.2.2 邻域结构
在生成初始解后，LAHC算法将其设置为第一个当前解，在每次迭代过程中根据当前解生成邻域解。当前解的所有邻域解通过以下3种邻域生成：1）如果医生i没有在诊室j内的班次，则额外指派一个在诊室j内的班次给医生i；2）如果医生i有在诊室j内的班次，则修改医生i在诊室j内的工作时间；3）如果医生i有在诊室j内的班次，则取消医生i在诊室j内的班次。需要注意的是，如果邻域解与给定的状态St和动作Wt冲突，那么该邻域解将被跳过，只有符合医生排班约束的邻域解才会被保留。
3.2.3 解的评估
在搜索过程中，当前选择的动作会对服务水平产生长期的影响，这可能使得式(11)和(12)难以满足。在LAHC算法中对式(11)和(12)进行松弛，设定诊室j在时段t内的服务水平约束相关的惩罚系数为βj,t，阶段k内LAHC算法的目标函数为
$$ \begin{gathered} \min \displaystyle\sum\limits_{t = k}^T \bigg( \displaystyle\sum\limits_{i \in I} {\displaystyle\sum\limits_{j \in J\backslash \{ 0\} } {{W_{i,j,t}}} } + {\beta _{1,t}}{\left( {S{T_t} - {S_M}} \right)^ + } + \\ {\beta _{2,t}}{\left( {W{T_t} - {W_M}} \right)^ + } \bigg)+ \displaystyle\sum\limits_{j = 1}^2 {o{t_j}} \end{gathered} $$ 传统的系统性能评估方法往往通过仿真实现。为了保证求解速度，LAHC算法通过结合数据驱动和仿真方法计算解的目标值。对各邻域解，首先通过3.3节中提出的神经网络预测其系统性能，若该解的目标值与当前解的目标值差值百分比高于ε，则认为该邻域解质量较差，不再进行精确评估。否则，通过仿真对该邻域解做精细评估，从而提高算法搜索精度。
3.3 数据驱动的系统性能评估
在3.2.3节中，需要一类方法来对所采用的启发式算法所搜索到的邻域解进行评估，确定在该邻域解中医生的总工作时间和每个时段到达患者的平均停留/等待时间，从而判断该邻域解目标值的大小。传统的计算机仿真方法虽然可以实现这个功能，但需要较长的运行时间。本文设计了深度学习的方法来快速评估给定排班的性能指标。考虑到线上和线下服务系统的差异，其性能评估通过2个相互独立的深度学习模型分别完成。将线上/线下各时段的到达率表示为λ={λ1, λ2, …, λT}，各时段在该诊室工作的医生数量表示为N={N1, N2, …, NT}，二者共同构成了该深度学习模型的特征。对于线上服务系统，深度学习模型的标签是各时段到达的患者的平均停留时间L和最后一个时段的加班时间ot1，表示为{L1, L2, …, LT, ot1}。对于线下服务系统，深度学习模型的标签是各时段到达的患者的平均等待时间M和最后一个时段的加班时间ot2，表示为{M1, M2, …, MT, ot2}。由于输出变量是连续的序列，该问题是一个序列到序列的回归问题。
3.3.1 模型选择
考虑到问题序列到序列的结构特征，对系统性能的评估采用长短期记忆（long short-term memory, LSTM）的神经网络框架实现[30]。LSTM在处理时间序列型数据方面具有优势，其利用多个单元间的递归连接，捕捉和处理来自先前步骤的信息，并将其用于更新当前的预测或输出，从而保持数据中序列前后固有的依赖关系[31-33]。在单元间，LSTM相较于传统循环神经网络（recurrent neural network, RNN）多了一条承载细胞状态的传输轴，细胞状态在一个衰减较少的通道里沿时间轴传递，对时间跨度较大的信息的保持能力比隐藏状态要强很多，更有效地解决了RNN的短期依赖瓶颈。而在单元内，LSTM通过遗忘门、输入门和输出门对信息进行筛选。LSTM的特点与本文研究问题结构相吻合，医生的排班和患者的到达率为时间序列，同样表现出时间上的依赖性，前一时刻的系统状态会对后一时刻产生直接影响。LSTM中输入与输出间的关系具体如下：
$$ {{\boldsymbol{i}}_t} = \sigma ({{\boldsymbol{W}}_i} \cdot [{{\boldsymbol{h}}_{t - 1}},{{\boldsymbol{x}}_t}] + {{\boldsymbol{b}}_i}) $$ $$ {{\boldsymbol{f}}_t} = \sigma ({{\boldsymbol{W}}_f} \cdot [{{\boldsymbol{h}}_{t - 1}},{{\boldsymbol{x}}_t}] + {{\boldsymbol{b}}_f}) $$ $$ {{\boldsymbol{o}}_t} = \sigma ({{\boldsymbol{W}}_o} \cdot [{{\boldsymbol{h}}_{t - 1}},{{\boldsymbol{x}}_t}] + {{\boldsymbol{b}}_o}) $$ $$ {{\boldsymbol{c}}_t} = {{\boldsymbol{f}}_t} \odot {{\boldsymbol{c}}_{t - 1}} + {{\boldsymbol{i}}_t} \odot \tanh ({{\boldsymbol{W}}_c} \cdot [{{\boldsymbol{h}}_{t - 1}},{{\boldsymbol{x}}_t}] + {{\boldsymbol{b}}_c}) $$ $$ {{\boldsymbol{h}}_t} = {{\boldsymbol{o}}_t} \odot \tanh ({{\boldsymbol{c}}_t}) $$ 所使用的神经网络结构如图3所示。在LSTM模型结构上，首先通过嵌入层将工作医生人数映射为连续的向量空间中，提供更好的特征表示。然后在嵌入层基础上，将工作医生人数与到达率相连接，共同作为一层LSTM层的输入。LSTM层能够通过隐藏状态和细胞状态捕捉数据中的长短期依赖关系。通过LSTM层后，再经过一个以线性整流函数（rectified linear unit, ReLU）为激活函数的全连接层输出最终所需的系统性能指标。全连接层能够对LSTM层输出的抽象特征进行进一步的非线性建模，从而提高模型的表达能力，使得模型能够更好地拟合复杂的数据分布。
图 3 LSTM神经网络结构Fig. 3 Structure of LSTM neural network下载:
全尺寸图片
3.3.2 数据集准备
神经网络模型的有效性取决于数据集在准确性和广泛适用性方面的质量。通过分析合作医院的实际数据，发现对于一定时期的数据（例如3个月内），考虑不同日期，对于一个时段虽然其患者到达率并不相同，但是都基本保持在一定范围内，即不同天的同一时间段内，患者到达率呈现出上下波动的趋势。图4为合作医院实际每日患者到达率数据。
图 4 合作医院实际每日患者到达率数据Fig. 4 Daily patient arrival rates in cooperative hospital下载:
全尺寸图片
图4给出了合作医院2023年3月某7天的每半个小时到达率数据，从上午8:00开始到下午5:30共19个时段。可见对每个时段而言，其患者到达率处于一定范围内的随机波动。同时，由于可以采集的医院数据量是有限的，为了进行高质量的基于数据驱动方法研究，参考相关研究的方法[34-35]，进一步通过计算机仿真生成样本数据以补充数据集。
数据集中每个样本由患者到达率向量λ、医生人数向量N和指标向量组成。依照医院实际情况，生成样本步骤如下。首先，如上所述，由于在实际数据中不同日期的对应同时段，患者到达率处于一定范围内波动，因此由实际医院数据得到每个时段的平均到达率，在此基础上将每个时段的到达率乘以一个随机系数，此系数服从[0.6, 1.4]区间均匀分布，以模拟每天此时段的患者到达率。同时，样本中各时段工作的医生数量也是随机生成，每时段数量在区间[1, |I|−1]内均匀分布随机产生。需要注意只有在医疗能力充足但不过量的范围内，诊室才能高效运作。因此，所生成的数据要求医生服务能力与患者到达量大致相等，即服务强度必须处于一定的范围内：
$$ \rho = \displaystyle\sum\limits_{t = 1}^T {{\lambda _t}} \bigg/\displaystyle\sum\limits_{t = 1}^T {\mu {N_t}} \in \left[ {0.6,2} \right] $$ 如果生成的样本的服务强度不处于此范围内，则重新生成该样本。最后，对每个训练样本，通过蒙特卡洛仿真105次，得到各时段到达患者的平均停留/等待时间，以及最后一个时段的加班时间。所得仿真结果作为每个样本的标签。按照以上方法重复生成不同样本，共生成106个样本，将其按照4∶1的比例随机划分为训练集与测试集。
3.3.3 模型训练
生成数据集后进行神经网络模型训练，关键任务之一是其超参数设置。考虑到当前问题的规模，采用了网格搜索的方法。每次迭代都按照特定顺序尝试超参数的组合，模型根据选定的组合对数据进行拟合，并记录模型性能，最后返回性能最优的超参数组合和与之对应的模型。根据网格搜索的结果，具体所使用超参数如表1所示。
表 1 LSTM所使用超参数Table 1 Hyper-parameters of LSTM超参数 值 含义 嵌入层维度 8×3 医生数映射维数 LSTM层单元数 400 决定模型复杂程度 全连接层单元数 400 决定模型复杂程度 批量大小 8 每次迭代训练时用于更新模型参数的样本数量 学习率 10−4 用于控制权重更新步长 本文使用了AdamW优化器，采用小批量梯度下降的算法进行训练。在训练过程中，通过训练集样本的平均绝对百分比误差（mean squared error, MSE）指标来衡量模型性能，选取最优超参数。假设总共n条训练数据，时段长度为T+1（包含加班时段），第i条训练数据在第t个时段的真实值为
$y_{i,t}^{{\text{true}} }$ ，预测值为$y_{i,t}^{\mathrm{pred}} $ ，则MSE的计算方式为$$ {E_{{\text{MSE}}}} = \frac{1}{{n\left( {T + 1} \right)}}\displaystyle\sum\limits_{i = 1}^n {\displaystyle\sum\limits_{t = 1}^{T + 1} {{{\left( {y_{i,t}^{{\text{pred}}} - y_{i,t}^{{\text{true}}}} \right)}^2}} } $$ 从训练集中随机选取小批量样本用于训练，最后通过在测试集下的百分比误差判断模型准确程度。
4. 医院实际数值实验
本节选取合作医院在2023年的7组实际算例进行数值实验，数据来自于内科科室，每个算例对应于一天的数据，包含实际患者的到达率等信息。该科室中共有7名医生，所使用的日常排班主要构成如下。在线上诊室中，2名医生在8:00~10:30工作，另外2名医生在10:30~17:30工作；在线下诊室中，2名医生在8:00~14:00工作，3名医生在14:00~17:30间工作。基于此7个数据算例，使用本文的方法对医生排班问题进行求解。
首先，数值实验验证第3.3节中所提出系统性能评估方法的精度，再利用第3章ADP算法求解得到新的排班方案，并对比医院实际排班方案以验证有效性。进一步，对比ADP算法与医生排班问题中常用的模拟退火算法在实际算例中的表现，以检验ADP算法求解的高效性。算法均由C++实现，运行硬件平台为3.1 GHz CPU。数值实验中一天医疗服务时间划分为19个时段，每个时段为0.5 h。单个医生线上最多同时服务3个患者，加班时间成本系数为2，线上各时段到达患者平均停留时间阈值为24 min，线下各时段到达患者平均等待时间阈值为45 min。患者到达率、医生服务速率和工作时长限制参数取值均取自医院实际数据和设定。
4.1 LSTM预测精度实验
首先对第3.3节所提出的数据驱动的系统性能评估方法进行精度检验，以检验其在各时段的线上到达患者的平均停留时间、线下到达患者的平均等待时间以及最后一个时段工作医生的加班时间的预测精度。每个算例中包含一天的线上和线下实际到达率，线上和线下分别根据实际到达率按照3.3.1节的方式生成2×104个由随机到达率和随机排班组成的测试集数据。每个测试集数据的特征作为LSTM预测模型和离散事件仿真模型的输入，计算LSTM预测模型所输出的系统性能指标的预测值和仿真模型模拟105次后输出的仿真值的平均差值百分比，结果如表2所示。
表 2 LSTM方法精度(Y)Table 2 Precision(Y) of LSTM neural network% 算例 st ot1 wt ot2 1 0.76 0.76 3.40 1.04 2 0.66 0.76 3.58 1.09 3 0.83 0.87 5.84 1.10 4 0.76 0.89 7.36 1.19 5 0.89 1.19 4.86 0.87 6 1.29 1.40 5.86 1.02 7 0.93 1.10 6.03 1.01 平均 0.87 1.00 5.28 1.05 表2中所有列为相应算例的测试集中LSTM预测值与仿真结果的平均差值百分比。其中，st列表示线上患者的平均停留时间预测值和仿真值的平均差值百分比，ot1列表示线上诊室医生的加班时间预测值和仿真值的平均差值百分比，wt列表示线下患者的平均等待时间预测值和仿真值的平均差值百分比，ot2列表示线下诊室医生加班时间预测值和仿真值的平均差值百分比。
$$ {E_{{\text{MAPE}}}} = \frac{1}{{nT}}\displaystyle\sum\limits_{i = 1}^n {\displaystyle\sum\limits_{t = 1}^T {\frac{{\left| {y_{i,t}^{{\text{pred}}} - y_{i,t}^{{\text{true}}}} \right|}}{{y_{i,t}^{{\text{true}}}}} \times 100\% } } $$ 可以发现，对于线上各时段到达患者的平均停留时间和线下各时段到达患者的平均等待时间，LSTM神经网络预测值与仿真值平均差距分别为0.87%、5.28%。而对于线上和线下诊室中工作医生的加班时间，7个算例中LSTM神经网络预测值与仿真值平均差距分别为1.00%和1.05%。这表明所提出的LSTM神经网络能够对线上、线下排队系统中的系统性能指标完成高精度的评估。
4.2 求解医生排班的结果
基于医院的7个实际算例，本节采用第3章中提出的ADP算法求解排班问题，并把结果和实际排班方案进行对比。ADP算法中LAHC算法迭代次数为20次，解池大小为5，服务水平约束相关的惩罚系数为104。计算结果如表3所示。其中TBreak为该排班方案违反阈值约束的次数；Twork为仿真得到的问题目标值，即医生正常工作时间与加班时间加权之和。第5列为实际排班与算法排班目标函数值的百分比相对差距。
表 3 ADP所求排班与实际排班比较Table 3 Comparison of ADP solutions and real-life plan算例 实际排班 算法排班 差距/
%TBreak Twork TBreak Twork 1 11.0 84.89 0 82.69 2.60 2 6.0 84.80 0 80.35 5.25 3 4.0 84.60 0 76.28 9.83 4 5.0 84.54 0 78.32 7.36 5 6.0 84.21 0 78.04 7.34 6 6.0 84.62 0 80.66 4.68 7 7.0 84.67 0 80.54 4.88 平均 6.4 84.62 0 79.55 5.99 表3结果显示，本文提出的ADP算法所得解优于实际排班方案。考虑患者停留/等待时间为代表的服务水平方面，实际排班平均违反最大停留/等待时间的阈值约束6.4次，而ADP算法得到的排班方案中各时段服务水平均满足阈值约束。在目标值方面，ADP得到的排班方案中的7个算例目标值相较于原始排班平均下降了5.99%，有效降低了医院的运营成本。可以进一步观察到，算法所得到的排班方案可以更有效地控制线上患者的平均停留时间和线下患者的平均等待时间。如图5所示，在算例1中，线上患者的平均停留时间在第4~6、12~15时段超出阈值，线下患者平均等待时间在第4~7时段超出阈值。相比之下，算法排班满足各时段服务水平限制，并能够在不增加医生容量的情况下提高对患者的服务水平。
图 5 算例1的ADP算法解与实际排班下服务水平对比Fig. 5 Comparison of service levels of ADP scheduling solutions and real-life scheduling plan of instance 1下载:
全尺寸图片
4.3 与其他算法结果对比
本节进一步将所提出的算法与医生排班常用的算法进行比较。模拟退火（simulated annealing, SA）算法被证明是解决医生排班问题的有效算法[8]。首先将所提出的ADP算法和SA算法进行排班问题求解的对比。在作为对比的SA算法中，初始解构造、邻域结构、解的评估与LAHC算法相同，但基于Metropolis准则判断是否接受新解。初始温度为100，降温系数为0.9，算法终止条件为10次迭代以内当前解未更新则终止。此外，在3.3节中设计了LSTM神经网络评估排队系统性能的方法，替代了传统的仿真方法，加速ADP算法的求解。因此在本节中，也将所提出的ADP算法和传统使用仿真的ADP方法进行了比较。在ADP–仿真算法中，使用仿真来评估排队系统性能而非LSTM神经网络，其他细节与本文所设计的ADP算法保持一致。SA、ADP和ADP仿真方法求解结果对比如表4所示，其中Twork为3种算法求解得到的排班方案目标值，t为3种算法求解所用时间，Gap计算为
$(T_{\mathrm{work}}^{\mathrm{SA}} -T_{\mathrm{work}}^{\mathrm{ADP}})/T_{\mathrm{work}}^{\mathrm{ADP}} $ 。表 4 ADP、SA算法求解结果Table 4 Solutions of ADP and SA algorithms算例 ADP SA ADP–仿真 Gap/
%Twork t/h Twork t/h Twork t/h 1 82.69 6.8 83.45 10.4 82.69 19.4 0.92 2 80.35 7.4 82.49 11.2 79.40 29.2 2.66 3 76.28 7.1 81.91 8.1 77.05 20.5 7.38 4 78.32 5.6 82.70 10.1 78.32 17.8 5.59 5 78.04 5.6 80.32 6.1 76.92 23.7 2.92 6 80.66 6.2 83.23 7.3 80.01 26.4 3.19 7 80.54 7.5 81.37 8.1 79.44 35.2 1.03 平均 79.55 6.6 82.21 8.8 79.12 24.6 3.40 可以发现，7个算例的ADP算法解对应的目标函数值相较SA算法解平均小3.40%，而ADP的求解时间相较SA算法平均低128.5 min。7个算例中2种方法的目标函数值最大差距为7.38%，最小差距为0.92%。通过以上对比显示，ADP算法相较于经典SA算法可在合理的时间范围内更有效地降低医院运营成本，减轻医生工作压力。而在所设计的ADP算法和传统ADP–仿真算法的对比上，可以发现ADP算法相较于ADP-仿真算法，目标值的平均差值仅为0.54%，求解时间却下降了73.14%，ADP–仿真算法的求解时间平均达到了24.1 h。这表明所设计的ADP算法能够在更有限的时间内得到高质量的医生排班，更符合实践应用的需要。
4.4 方法和结果的鲁棒性实验
本文提出的方法中，一个重要的假设是患者的服务时长服从指数分布。医院实际数据表明，在部分场景下，服务时间可能并不适用于指数分布，更加接近对数正态分布和一般分布（G分布）。因此，本节分别设定服务时长服从对数正态分布和G分布，验证所提出的ADP算法的鲁棒性。具体方案为按照ADP算法生成的排班，将服务时间设置为对数正态分布和G分布，基于此设定对生成的排班进行系统计算机仿真，得到系统的性能。对数正态分布和G分布的均值和方差均从医院实际数据中得到。仿真所得系统性能如表5和6所示。从实验结果来看，当服务时间设定为非指数分布时，ADP算法所得到的解仍能有效保证服务水平。例如，当服务时间满足对数正态分布时，阈值约束违反次数平均从14.7次降到了11.7次，医院总运营成本平均降低了5.98%。
表 5 对数正态分布服务时间下算法解与实际排班结果对比Table 5 Comparison of ADP solutions and real-life scheduling for lognormal distributed service time算例 实际排班 算法排班 Gap/
%TBreak Twork TBreak Twork 1 19.0 85.04 15.0 82.85 2.58 2 14.0 85.01 9.0 80.50 5.31 3 13.0 84.73 11.0 76.36 9.88 4 17.0 84.68 13.0 78.41 7.40 5 13.0 84.25 11.0 78.13 7.26 6 14.0 84.71 12.0 80.82 4.59 7 13.0 84.77 11.0 80.63 4.88 平均 14.7 84.74 11.7 79.67 5.98 表 6 一般分布服务时间下算法解与实际排班结果对比Table 6 Comparison of ADP solutions and real-life scheduling for general distributed service time算例 实际排班 算法排班 Gap/
%TBreak Twork TBreak Twork 1 14.0 85.06 7.0 83.22 2.17 2 10.0 84.98 5.0 80.84 4.87 3 7.0 84.74 7.0 76.73 9.45 4 8.0 84.69 5.0 78.79 6.97 5 8.0 84.33 4.0 78.47 6.95 6 9.0 84.85 4.0 81.15 4.36 7 9.0 84.89 5.0 81.06 4.51 平均 9.3 84.79 5.3 80.04 5.61 而当服务时间满足G分布时，阈值约束违反次数平均从9.3次降到了5.3次，医院总运营成本平均降低5.61%。这表明，当服务时间服从其他分布时，相较于实际排班，ADP算法所求解排班仍能有效减少医院总运营成本，控制患者平均停留/等待时长，具有很强的鲁棒性。
5. 结束语
在线上和线下联合医疗模式下，面对各自时变的患者到达流，医院需要通过制定医生的柔性排班方案，降低运营成本并确保医疗服务水平。为了解决这一问题，首先针对线上和线下联合医疗服务系统建立了离散时间马尔可夫决策过程模型。在该马尔可夫决策过程模型中，状态为各时段结束时系统中的患者和医生信息，动作为各时段的医生工作指派。为了高效求解马尔可夫决策过程问题，设计近似动态规划算法。接着，提出了基于数据驱动的系统性能评估方法，设计机器学习方法对系统性能高效评估。基于实际数据的数值实验显示，所提出的机器学习方法可快速且高精度完成对系统性能的评估，近似动态规划算法求解得到的排班方案能够有效降低医生工作负荷，并控制患者的停留和等待时间。
本工作可以从多个角度进行扩展。首先，在线下诊室等待队列较长时，一些线下的患者也可能会考虑转移到线上就诊，这将使得问题的建模和求解更具挑战性。同时，本文将每位医生可同时服务的最大患者人数设置为固定值，而在实际服务过程中，可考虑将该值设置为随时间变化的值，以便更容易满足高峰期的患者需求。
-
图 1 线上与线下诊室排队系统示意
Fig. 1 Schematic diagram of queueing system in the online and offline clinic
下载:
全尺寸图片
图 2 近似动态规划算法框架
Fig. 2 Framework of approximate dynamic programming algorithm
下载:
全尺寸图片
图 3 LSTM神经网络结构
Fig. 3 Structure of LSTM neural network
下载:
全尺寸图片
图 4 合作医院实际每日患者到达率数据
Fig. 4 Daily patient arrival rates in cooperative hospital
下载:
全尺寸图片
图 5 算例1的ADP算法解与实际排班下服务水平对比
Fig. 5 Comparison of service levels of ADP scheduling solutions and real-life scheduling plan of instance 1
下载:
全尺寸图片
表 1 LSTM所使用超参数
Table 1 Hyper-parameters of LSTM
超参数 值 含义 嵌入层维度 8×3 医生数映射维数 LSTM层单元数 400 决定模型复杂程度 全连接层单元数 400 决定模型复杂程度 批量大小 8 每次迭代训练时用于更新模型参数的样本数量 学习率 10−4 用于控制权重更新步长 表 2 LSTM方法精度(Y)
Table 2 Precision(Y) of LSTM neural network
% 算例 st ot1 wt ot2 1 0.76 0.76 3.40 1.04 2 0.66 0.76 3.58 1.09 3 0.83 0.87 5.84 1.10 4 0.76 0.89 7.36 1.19 5 0.89 1.19 4.86 0.87 6 1.29 1.40 5.86 1.02 7 0.93 1.10 6.03 1.01 平均 0.87 1.00 5.28 1.05 表 3 ADP所求排班与实际排班比较
Table 3 Comparison of ADP solutions and real-life plan
算例 实际排班 算法排班 差距/
%TBreak Twork TBreak Twork 1 11.0 84.89 0 82.69 2.60 2 6.0 84.80 0 80.35 5.25 3 4.0 84.60 0 76.28 9.83 4 5.0 84.54 0 78.32 7.36 5 6.0 84.21 0 78.04 7.34 6 6.0 84.62 0 80.66 4.68 7 7.0 84.67 0 80.54 4.88 平均 6.4 84.62 0 79.55 5.99 表 4 ADP、SA算法求解结果
Table 4 Solutions of ADP and SA algorithms
算例 ADP SA ADP–仿真 Gap/
%Twork t/h Twork t/h Twork t/h 1 82.69 6.8 83.45 10.4 82.69 19.4 0.92 2 80.35 7.4 82.49 11.2 79.40 29.2 2.66 3 76.28 7.1 81.91 8.1 77.05 20.5 7.38 4 78.32 5.6 82.70 10.1 78.32 17.8 5.59 5 78.04 5.6 80.32 6.1 76.92 23.7 2.92 6 80.66 6.2 83.23 7.3 80.01 26.4 3.19 7 80.54 7.5 81.37 8.1 79.44 35.2 1.03 平均 79.55 6.6 82.21 8.8 79.12 24.6 3.40 表 5 对数正态分布服务时间下算法解与实际排班结果对比
Table 5 Comparison of ADP solutions and real-life scheduling for lognormal distributed service time
算例 实际排班 算法排班 Gap/
%TBreak Twork TBreak Twork 1 19.0 85.04 15.0 82.85 2.58 2 14.0 85.01 9.0 80.50 5.31 3 13.0 84.73 11.0 76.36 9.88 4 17.0 84.68 13.0 78.41 7.40 5 13.0 84.25 11.0 78.13 7.26 6 14.0 84.71 12.0 80.82 4.59 7 13.0 84.77 11.0 80.63 4.88 平均 14.7 84.74 11.7 79.67 5.98 表 6 一般分布服务时间下算法解与实际排班结果对比
Table 6 Comparison of ADP solutions and real-life scheduling for general distributed service time
算例 实际排班 算法排班 Gap/
%TBreak Twork TBreak Twork 1 14.0 85.06 7.0 83.22 2.17 2 10.0 84.98 5.0 80.84 4.87 3 7.0 84.74 7.0 76.73 9.45 4 8.0 84.69 5.0 78.79 6.97 5 8.0 84.33 4.0 78.47 6.95 6 9.0 84.85 4.0 81.15 4.36 7 9.0 84.89 5.0 81.06 4.51 平均 9.3 84.79 5.3 80.04 5.61 -
[1] 于保荣, 杨瑾, 宫习飞, 等. 中国互联网医疗的发展历程、商业模式及宏观影响因素[J]. 山东大学学报(医学版), 2019, 57(8): 39−52. YU Baorong, YANG Jin, GONG Xifei, et al. Development process, business modes and macrocally influencing factors for Internet-based health service in China[J]. Journal of Shandong University (Health Sciences), 2019, 57(8): 39−52. [2] 初佃辉, 吴军, 刘志中, 等. 智能化医养融合服务平台关键技术及应用研究[J]. 智能系统学报, 2021, 16(5): 972−988. doi: 10.11992/tis.202103022 CHU Dianhui, WU Jun, LIU Zhizhong, et al. Research on key technologies and applications of intelligent medical and care integration service platform[J]. CAAI transactions on intelligent systems, 2021, 16(5): 972−988. doi: 10.11992/tis.202103022 [3] LUO Jun, ZHANG Jiheng. Staffing and control of instant messaging contact centers[J]. Operations research, 2013, 61(2): 328−343. doi: 10.1287/opre.1120.1151 [4] RAJAN B, TEZCAN T, SEIDMANN A. Service systems with heterogeneous customers: investigating the effect of telemedicine on chronic care[J]. Management science, 2019, 65(3): 1236−1267. doi: 10.1287/mnsc.2017.2979 [5] 国家互联网信息办公室. 数字中国发展报告(2022年)[EB/OL]. (2023−05−23)[2024−04−02]. https://www.cac.gov.cn/2023-05/22/c_1686402318492248.htm. Cyberspace Administration of China.Digital China development report(2022)[EB/OL]. (2023−05−23)[2024−04−02]. https://www.cac.gov.cn/2023-05/22/c_1686402318492248.htm. [6] ZHOU Cuihua, HAO Yifei, LAN Yanfei, et al. To introduce or not? strategic analysis of hospital operations with telemedicine[J]. European journal of operational research, 2023, 304(1): 292−307. doi: 10.1016/j.ejor.2021.12.020 [7] 罗利, 付颖, 徐雪茹, 等. 多方参与的互联网医院运营管理研究综述[J]. 工业工程与管理, 2024, 29(4): 205−222. LUO Li, FU Ying, XU Xueru, et al. The operation management of multi-participant internet hospital: a framework and review[J]. Industrial engineering and management, 2024, 29(4): 205−222. [8] ERHARD M, SCHOENFELDER J, FÜGENER A, et al. State of the art in physician scheduling[J]. European journal of operational research, 2018, 265(1): 1−18. doi: 10.1016/j.ejor.2017.06.037 [9] YOUN S, GEISMAR H N, PINEDO M. Planning and scheduling in healthcare for better care coordination: current understanding, trending topics, and future opportunities[J]. Production and operations management, 2022, 31(12): 4407−4423. doi: 10.1111/poms.13867 [10] BRUNNER J O, BARD J F, KOLISCH R. Midterm scheduling of physicians with flexible shifts using branch and price[J]. IIE transactions, 2010, 43(2): 84−109. doi: 10.1080/0740817X.2010.504685 [11] STOLLETZ R, BRUNNER J O. Fair optimization of fortnightly physician schedules with flexible shifts[J]. European journal of operational research, 2012, 219(3): 622−629. doi: 10.1016/j.ejor.2011.10.038 [12] WANG Zixiang, LIU Ran, SUN Zhankun. Physician scheduling for emergency departments under time-varying demand and patient return[J]. IEEE transactions on automation science and engineering, 2023, 20(1): 553−570. doi: 10.1109/TASE.2022.3163259 [13] SINREICH D, JABALI O, DELLAERT N P. Reducing emergency department waiting times by adjusting work shifts considering patient visits to multiple care providers[J]. IIE transactions, 2012, 44(3): 163−180. doi: 10.1080/0740817X.2011.609875 [14] LIU Ran, XIE Xiaolan. Physician staffing for emergency departments with time-varying demand[J]. INFORMS journal on computing, 2018, 30(3): 588−607. doi: 10.1287/ijoc.2017.0799 [15] ZAERPOUR F, BIJVANK M, OUYANG Huiyin, et al. Scheduling of physicians with time-varying productivity levels in emergency departments[J]. Production and operations management, 2022, 31(2): 645−667. doi: 10.1111/poms.13571 [16] 祖漫漫. 门诊医生排班问题研究[D]. 大连: 大连理工大学, 2019. ZU Manman. Study on outpatient doctors' scheduling problem[D]. Dalian: Dalian University of Technology, 2019. [17] 王铖恺, 范晓宇, 徐捷, 等. 结合Benders分解和列生成的发热门诊排班数学建模和优化算法[J]. 系统管理学报, 2023, 32(3): 476−487. WANG Chengkai, FAN Xiaoyu, XU Jie, et al. Mathematical modeling and optimization algorithm for fever clinics scheduling combining benders decomposition and column generation[J]. Journal of systems & management, 2023, 32(3): 476−487. [18] 兰绍雯. 门诊医生资源协同优化问题研究[D]. 合肥: 合肥工业大学, 2022. LAN Shaowen. Research on collaborative optimization of outpatient doctor resources[D]. Hefei: Hefei University of Technology, 2022. [19] PRAKASH A M, ZHONG Xiang. Queueing information management of primary care delivery with E-visits[J]. IEEE transactions on automation science and engineering, 2022, 19(2): 632−645. doi: 10.1109/TASE.2021.3115355 [20] ÇAKıCı Ö E, MILLS A F. On the role of teletriage in healthcare demand management[J]. Manufacturing & service operations management, 2021, 23(6): 1483−1504. [21] 姜劲, 白闪闪, 王云婷, 等. 线上和线下医疗服务质量对患者线下就医决策的影响[J]. 管理科学, 2020, 33(1): 46−53. doi: 10.3969/j.issn.1672-0334.2020.01.004 JIANG Jin, BAI Shanshan, WANG Yunting, et al. Influence of online and offline medical service quality on patients' offline medical decision-making[J]. Journal of management science, 2020, 33(1): 46−53. doi: 10.3969/j.issn.1672-0334.2020.01.004 [22] HOSSAIN I S, AKHAND M A H, SHUVO M I R, et al. Optimization of university course scheduling problem using particle swarm optimization with selective search[J]. Expert systems with applications, 2019, 127: 9−24. doi: 10.1016/j.eswa.2019.02.026 [23] 宋婷, 陈矛, 吴超, 等. 基于多类迭代局部搜索的自动化排课算法[J]. 计算机应用, 2019, 39(6): 1760−1765. doi: 10.11772/j.issn.1001-9081.2018102183 SONG Ting, CHEN Mao, WU Chao, et al. Automated course arrangement algorithm based on multi-class iterated local search[J]. Journal of computer applications, 2019, 39(6): 1760−1765. doi: 10.11772/j.issn.1001-9081.2018102183 [24] GUPTA V, ZHANG Jiheng. Approximations and optimal control for state-dependent limited processor sharing queues[J]. Stochastic systems, 2022, 12(2): 205−225. doi: 10.1287/stsy.2021.0087 [25] CUI L, TEZCAN T. Approximations for chat service systems using many-server diffusion limits[J]. Mathematics of operations research, 2016, 41(3): 775−807. doi: 10.1287/moor.2015.0754 [26] POWELL W B. Approximate dynamic programming: Solving the curses of dimensionality[M]. New York: John Wiley & Sons, 2007. [27] POWELL W B. Perspectives of approximate dynamic programming[J]. Annals of operations research, 2016, 241(1): 319−356. [28] LIU Derong, XUE Shan, ZHAO Bo, et al. Adaptive dynamic programming for control: a survey and recent advances[J]. IEEE transactions on systems, man, and cybernetics: systems, 2021, 51(1): 142−160. doi: 10.1109/TSMC.2020.3042876 [29] BURKE E K, BYKOV Y. The late acceptance hill-climbing heuristic[J]. European journal of operational research, 2017, 258(1): 70−78. doi: 10.1016/j.ejor.2016.07.012 [30] YU Yong, SI Xiaosheng, HU Changhua, et al. A review of recurrent neural networks: LSTM cells and network architectures[J]. Neural computation, 2019, 31(7): 1235−1270. doi: 10.1162/neco_a_01199 [31] 张驰, 郭媛, 黎明. 人工神经网络模型发展及应用综述[J]. 计算机工程与应用, 2021, 57(11): 57−69. doi: 10.3778/j.issn.1002-8331.2102-0256 ZHANG Chi, GUO Yuan, LI Ming. Review of development and application of artificial neural network models[J]. Computer engineering and applications, 2021, 57(11): 57−69. doi: 10.3778/j.issn.1002-8331.2102-0256 [32] 李倩玉, 王蓓, 金晶, 等. 基于双向LSTM卷积网络与注意力机制的自动睡眠分期模型[J]. 智能系统学报, 2022, 17(3): 523−530. doi: 10.11992/tis.202103013 LI Qianyu, WANG Bei, JIN Jing, et al. Automatic sleep staging model based on the bi-directional LSTM convolutional network and attention mechanism[J]. CAAI transactions on intelligent systems, 2022, 17(3): 523−530. doi: 10.11992/tis.202103013 [33] 常明煜, 田乐, 郭茂祖. 基于HHT-LSTM的冬奥会临时设施运行趋势预测方法研究[J]. 智能系统学报, 2024, 19(1): 228−237. doi: 10.11992/tis.202303003 CHANG Mingyu, TIAN Le, GUO Maozu. Research on the HHT-LSTM-based operation trend prediction method of temporary facilities for the Winter Olympic Games[J]. CAAI transactions on intelligent systems, 2024, 19(1): 228−237. doi: 10.11992/tis.202303003 [34] XAVIER Á S, QIU Feng, AHMED S. Learning to solve large-scale security-constrained unit commitment problems[J]. INFORMS journal on computing, 2021, 33(2): 739−756. [35] WANG Zixiang, LIU Ran. Managing appointments of outpatients considering the presence of emergency patients: the combination of the analytical and data-driven approach[J]. International journal of production research, 2022, 60(13): 4214−4228. doi: 10.1080/00207543.2021.2007425
