基于带记忆模拟退火算法的门诊预约问题求解

郜振华，王红俊，周春柳，胡玉焕

(安徽工业大学管理科学与工程学院，安徽 马鞍山 243032)

门诊预约决策是指医疗机构根据前来预约患者提供的就诊偏好以及门诊的预约情况，为预约患者安排合适医生及时间段的过程[1]。对于门诊预约的研究，最先开始于1952年，Bailey[2]基于排队论对医院门诊预约系统进行了初步研究，后来Gupta等[3]和梁峰等[4]综合描述了影响预约系统的因素，为门诊预约系统研究提供方向。随着计算机技术的成熟，An等[5]研究并设计了门诊预约系统，有利于规范医院管理。由于医疗资源的有限性，需对有限资源进行合理配置，实现资源利用的最大化[6-7]。

近年，门诊预约的研究更加关注患者：以患者的等待时间最小为目标，根据服务时间确定患者服务次序[8]，考虑患者就诊时可能出现的行为特征[9-11]，给出门诊预约的最优策略。随着研究的深入，患者满意度成为研究热点，医疗机构考虑其偏好并以满意度[12]进行度量。但作为非理性人，其偏好情况不能简单描述，曹萍萍等[13]首先利用前景理论描述患者的满意度，构建门诊预约决策模型；梁峰等[14]利用累积前景理论刻画满意度，对门诊预约进行调度并与传统先到先服务（first come first service,FCFS）方式进行对比；Li等[15]考虑患者实时满意度，对患者的总体满意度进行优化，但上述研究都没有具体说明解决该问题的方法与过程。门诊预约问题规模不大，模拟退火算法求解时间短，同时其在前中期局部收敛并且在后期可实现全局收敛[16]，理论上解为全局最优解，而其他启发式算法的解一般为较优解。但传统模拟退火算法在寻优过程中易丢失找到的较优解，为避免此类情况的发生，增加记忆功能[17]。

因此，本文利用前景理论描述患者对医生以及时间段的偏好，建立门诊预约决策模型；利用带记忆模拟退火算法设计编码以及邻域解生成方式，同时设置不同预约患者数量求解模型，以期实现患者的总价值最大，从而提高患者的满意度。

1 问题描述与模型建立

1.1 问题描述及假设

在门诊预约的大环境下，门诊拥有多名医生，每位医生在单位工作日内可预约的患者数相同；患者可在就诊前向医疗机构提出预约，同时完成对医生以及时间段的偏好选择，医疗机构每隔一段时间会对预约的患者进行预约处理，为其选择合适的医生及时间段。根据医疗机构已预约医生的时间段以及患者对医生以及时间段的偏好程度为患者选择合适的医生和就诊时间以达到整体价值最大化，用价值刻画满意度，进而提高满意度。根据上述关于门诊预约问题的描述，给出下列假设：

1)门诊就诊患者全部需要预约，不存在现场挂号；

2)患者预约之后不存在爽约、迟到现象，且患者预约时间不分先后；

3)患者对不同医生以及时间段之间的损失间隔相同，即在患者主观意识中，只存在排名差异，不存在具体差异大小；

4)医生一个时间段只为一位患者服务；

5)不接受超出可接受数量的患者。

1.2 模型建立

根据问题描述以及患者提供的偏好信息，依据前景理论[18-19]构建基于医生的价值矩阵以及基于时间段的价值矩阵，将两者进行加权可得到预约的患者对不同医生以及时间段的价值关系，从而构建门诊预约决策模型。其中模型涉及的参数及含义如表1。

表1 主要参数及其含义Tab.1 General parameters and their meanings

1.2.1 基于医生的价值矩阵

1.2.2 基于时间段的价值矩阵

1.2.3 模型构建

整合患者对医生和时间段的价值矩阵，可得到患者Pk的综合价值矩阵，

2 算法设计

2.1 编码和解码

2.2 带记忆模拟退火算法

2.2.1 能量函数

根据模型可知目标函数为总价值最大，但模拟退火算法的最优解为最低能量状态，因此构造能量函数。通过倒数的方法将目标函数求最大变成求最小，对数据进行分析可发现目标函数的倒数较小，在进行差值计算时不明显。因此，构造的能量函数为目标函数的倒数形式并扩大1 000倍，如式(15)。

2.2.2 邻域解

2.2.3 算法步骤

传统模拟退火算法在初始温度较高时，跳出局部最优的概率较高，这也是理论上能找到全局最优解的原因；但算法采用概率接收较优解的方式，局部最优的解可能被舍去，从而导致算法效率下降，因此采用添加记忆功能的模拟退火算法进行求解。算法步骤如下：

1)设置初始化数据，给定初始温度Tmax，随机产生初始状态x，给定内循环次数L，温度缩减系数δ，给定最低温度Tmin；

2)随机产生可行解x，记录当前可行解的能量E(x)；

3)对k= 1,2,…,L，进入内循环，进行步骤4)～7)迭代；

4)利用交换、逆序、变异产生新状态即新解xnew；

5)计算新状态与旧状态能量的增量ΔE=E(xnew)-E(x)；

7)判断算法是否达到规定的内循环次数L，找到L次内循环所有产生的能量最优解，并记录为当前状态,此时一次外循环结束；

8)判断当前状态能量与上一次外循环最优状态的能量，记录其中较优的能量，且为当前状态；

9)判断算法是否满足规定的终止条件T＜Tmin，若满足则当前的状态为最优解，若不满足则继续；

10)降低温度T，令T=T×δ，返回步骤3)。

带记忆模拟退火算法的流程图如图1。

图1 带记忆模拟退火算法流程图Fig.1 Flow chart of Simulated Annealing algorithm with memory

3 算例分析

已知某医疗机构门诊部每隔一段时间进行一次预约决策，该门诊共有4名医生，每位医生单个工作日将时间段分为10 个工作时间段，门诊会对每次决策时间间隔提交的预约申请进行处理，使预约的患者总满意度达到最优。在某时间间隔中收集24名预约患者对医生以及时段的偏好排序，如表2，且在这之前医疗机构门诊已预约的就诊时间段如表3。

表2 患者偏好情况Tab.2 Patients preferences

表3 已预约时间段Tab.3 Booked service time periods

根据预约前患者提供的偏好数据，将其转变为矩阵格式导入MATLAB 中，依据前景理论求解出患者基于医生以及就诊时间段的价值矩阵，并进行规范化处理，得到患者的价值矩阵；利用带记忆的模拟退火算法对门诊预约决策模型进行求解。设置价值函数参数α=β=0.88，λ=2.25[14]，模拟退火算法参数Tmax=1 000，Tmin=0.01，内循环次数L=100，温度缩减系数δ=0.98，交换、逆序概率P=0.80，变异概率Pb=0.60。在Windows10环境下，利用MATLAB 2018b将该医疗机构在面对12，16，20，24名患者预约的情况下，分别运行50次，得到其中某次能量变化迭代图，如图2。

图2 能量变化迭代图Fig.2 Iterative diagram of energy change

由图2 可看出，在面对12，16，20，24 名患者预约的情况下，采用建立的预约模型并利用带记忆模拟退火算法进行求解都可找到较优解，相比于随机生成的解，能量一直呈下降趋势，说明患者的总价值逐步趋近于最大值。因此，利用前景理论量化患者对门诊预约决策结果的价值并计算出满意解，可有效提高患者对决策结果的总价值，提高患者满意度。

随机挑选运行10 次的实验数据，记录患者数目变化时运行时间以及最终能量变化情况，结果如表4，并计算运行10 次的平均运行时间与平均能量函数值。根据能量函数与目标函数的转换关系计算出目标函数值，可得到患者数为“12，16，20，24”时的平均目标函数值分别为9.46，12.28，15.29，17.30。为了更清楚地看出每位预约患者的价值，计算人均价值(人均价值=平均目标函数值/患者数)，可得到患者数为“12，16，20，24”时的人均价值分别为0.79，0.77，0.76，0.74，均处于较高水平。根据图2 及表4 可看出：当预约患者人数增加时，运行时间并没有大幅度增加，24名患者预约时，运行时间少于10 s，可满足日常决策时间要求，证明了该算法求解门诊预约问题的效率较高；运行结果与较优结果能量函数值相差不足5%，说明该算法求解问题的稳定性。

表4 运行时间及能量变化情况Tab.4 Changes of running time and energy

对上述运行10 次中挑选出较最优结果，整理解码的预约结果如表5。利用传统FCFS 方法进行预约，当存在24 名患者预约时，结果如表6，由于先到先服务的方式，后到患者的决策结果不影响先到的患者，当患者数为“12，16，20”时，预约结果不变。FCFS方法与本文方法得到预约结果的价值如表7。

表5 不同数量患者预约时的预约结果Tab.5 Results of different number of patients’appointments

表6 FCFS规则下的预约结果Tab.6 Results of FCFS reservation

表7 本文方法与FCFS方法价值对比Tab.7 Value comparison betwen this method and FCFS method

结合表5～7 可看出，在不影响已预约患者情况下，文中建立的模型根据患者自身对预约时间段及医生的偏好情况计算价值,并通过带记忆模拟退火算法进行求解，得到的决策结果可将患者全部安排到适合自己的医生以及时间段，总价值比传统方法的价值高，提高了患者的总体满意度。

4 结论

综合患者对医生以及就诊时间段的偏好情况，利用前景理论对偏好进行量化，设计两种偏好的合成方法，建立患者满意度最大的门诊预约决策模型。依据问题的特殊性，设计符合问题特性的编码以及邻域解的生成方式，利用带记忆模拟退火算法对门诊预约决策模型进行求解。不同预约患者算例的求解结果表明，采用带记忆模拟退火算法求解门诊预约决策模型，能够在短时间内使整体患者满意度达到最优，为提高医院门诊服务满意度提供方法支持。

对于患者的心理偏好，未考虑患者取消预约或者未在规定时间点到达的情况，此类情况的发生会导致医生在该时间段的闲置，降低了资源的利用率。因此，后续研究会根据患者的往期行为特征预测预约之后的行为特征，为医疗机构更好地提供柔性决策。