考虑工作均衡性的家庭医疗人员调度研究

李 艳, 许 箫, 王付宇

(1.安徽工业大学管理科学与工程学院 安徽 马鞍山 243032; 2.上海理工大学管理学院 上海 200093)

随着老龄化社会的到来,养老问题成了突出的民生问题,迅速激增的养老需求是摆在社会现实面前的一大难题。家庭养老和居住养老院等传统的养老模式难以应对老龄化带来的养老压力,居家养老模式应运而生。但目前我国专业的家庭医疗护理人员极其缺乏,为了合理利用有限的家庭医疗资源,提供给老年人更满意的居家养老服务,如何调度家庭医疗人员以及合理安排他们的服务路径是居家养老服务运作管理研究领域中的热点问题。

关于家庭医疗人员调度模型的研究有许多,其研究重点各有侧重。在成本方面,一般通过缩短服务时间或行驶路径来降低成本。S E Moussavi等[1]利用经典的VRP与AP模型对居家医疗调度问题进行建模,采用元启发式算法为每位医护人员寻求最佳服务时间和最短行驶距离。Yang Zhan等[2]认为居家医疗调度问题的关键就是人员分配以及路径规划。Jamal Abdul Nasir等[3]综合考虑家庭服务的时间窗约束以及距离约束提出混合遗传算法求出最优路径。Jonathan F Bard等[4]提出一种贪婪随机自适应搜索方法解决了多类型医护人员服务成本最小化的问题。Toufik Boudouh等[5]考虑了不确定的服务时间等因素对于总成本的影响,构建成本最小化模型。María I Restrepo等[6]考虑了患者需求的不确定性,利用两阶段随机规划模型来整合医护人员配置与调度。Zhang Zizhen等[7]研究了医护人员的服务分配顺序以及救援车辆路径问题,构建了总成本最小化的调度模型。

上述文献仅研究了以成本最小化为目标的调度模型,然而在服务过程中会出现一些不确定因素造成患者情绪的波动,例如:时间的偏差、紧急需求等。Gang Du等[8]针对服务的取消、紧急护理的需求和医疗设备故障这些不确定的因素会降低患者的满意度进行建模。Ahmet Kandakoglu等[9]认为医护人员的服务时间表和服务顺序均会影响总成本以及患者满意度。Mascolo等[10]综合考虑家庭医护人员的服务时间窗和性别对患者满意度的影响。胡晓伟等人通过构建成本以及满意度模型为疫情下因医疗物资的短缺而造成分配不均提供解决方案[11]。家庭医疗人员调度问题属于NP-hard问题,随着问题规模的扩大,精确解算法已不能完全胜任。在此情况下,多数学者利用元启发式算法求解问题。Yong Shi等[12]将患者的不确定性需求设置为一个模糊变量,通过提出一种混合遗传算法与随机模拟相结合的方法来求解模型。陆雨薇等[13]提出一种禁忌搜索和整数规划的混合算法来求解医护人员的路径问题。康丽等[14]针对家庭医疗护理人员分配问题,利用遗传算法求解大规模资源分配问题。Chananes Akjiratikar等[15]在PSO(Particle swarm optimization)算法中嵌入了局部改进程序(LIP),求得医护人员服务调度最佳方案。李艳等[16]设计了一种改进的多目标鲸鱼群算法来求解居家养老医护人员调度的多目标模型。

就求解算法而言,利用等元启发式算法均能在一定程度上解决家庭医疗人员调度问题,但也存在编程实现复杂、收敛速度慢等不足之处。随着智能算法的发展,越来越多的算法被相继提出,天牛须算法位列其中。许多学者将该算法用于求解应急资源调度、电力调度等组合优化问题,并取得了一定的成果。王付宇等[17]利用天牛须算法求解应急资源调度问题,最终求得最佳分配方案。Li等[18]构建了以互补系统和等效负荷中波动性最小化为目标的调度模型,利用天牛须算法求解模型。家庭医疗人员调度问题也属于组合优化问题,在文献检索过程中,尚未发现利用天牛须算法求解此类问题。

因此,针对国内某医护中心的实际运营情况,构建调度模型,设计改进的BAS算法求解模型。将改进算法分别与遗传算法(GA,Genetic Algorithm)和粒子群算法进行对比分析,验证改进算法的有效性,为医护机构寻找最优调度方案提供决策依据。

1 问题描述与建模

1.1 问题描述

本文研究的是家庭医疗护理过程中,医护人员的分配以及服务路径问题,服务路径如图1所示。具体问题描述为假设有一个医护中心,多名医护人员和多个患者,医护人员从医护中心出发去往不同患者的家里,每天一个患者均只能被访问一次,而一个医护人员可以访问多个患者,每位患者将会提前告知医护中心希望被服务的时间范围以及服务时长。

图1 家庭医疗护理调度图

医护人员等待或迟到均会产生成本,与此同时会影响患者满意度。根据以上信息,如何调度医护人员可以使得医护中心总运营成本最小,患者满意度最大以及医护人员工作时间最均衡。

1.2 模型建立

W={0,1,2…n},0代表服务中心;N={1,2,3…n},表示患者需求集合点,i,j∈N;K={1,2,3…k},表示医护人员;Dist:医护人员的旅行负载差;P:医护人员早于或晚于患者可接受服务时间窗的时长;Ck:医护人员固定工资;PCk:超过规定时间的单位惩罚成本;Lk:医护人员最大工作时间;D:医护人员基本工作时间;Tik:医护人员为患者开始服务时间;tik:医护人员为患者提供服务时间;tij:从患者i到患者j的时间;ETi:患者可接受的最早开始服务时间;LTi:患者可接受的最晚开始服务时间;Xijk:医护人员k在对患者i进行服务之后再对患者j进行服务;X0jk:医护人员k从服务中心出发直接去往患者j;Xi0k:医护人员k为患者i服务结束之后回到服务中心;M:足够大的正整数;b:实际开始工作时间早于患者可接受的最早开始时间或者超出患者可接受的最晚开始服务的时间时,患者给出的单位惩罚成本;distk:医护人员k实际旅行距离;Length:医护人员最大旅行距离;v:车辆行驶速度。

目标函数为

(1)

(2)

MinZ3=Dist

(3)

(4)

(5)

∑j∈NX0jk=1,∀k∈K

(6)

∑j∈NXj0k=1,∀k∈K

(7)

Tik+tik+tij-M(1-Xijk)≤Tjk,∀k∈K

(8)

(9)

Dist=max|distk-distr|,∀k,r∈K

(10)

distk=∑i∈N∑j∈N,i≠jtij*v*Xijk,∀k∈K

(11)

∑i∈N∑j∈N,i≠jtij*v*Xijk≤Length,∀k∈K

(12)

其中式(4)是确保每位患者只访问一次,式(5)至(7)表示医护人员从医护中心出发最终返还到医护中心,式(8)表示医护人员在为患者i结束服务到达下一位患者的时间不得超过为下一个患者的实际开始服务时间,式(9)表示实际开始工作时间与期望的最早服务时间和最迟服务时间的偏差,式(10)表示医护人员之间的最大旅行距离差,式(11)表示医护人员的实际旅行距离,式(12)表示医护人员单条线路旅行不能超过最大旅行距离。

本文采用线性加权法将多目标问题转化为单目标问题,目标函数为

MinZ4=β1Z1+αβ2Z3-γβ3Z2

(13)

其中Z1表示成本,Z2表示满意度,Z3表示工作时间差,三者有着不同的量纲,则通过引入系数α、γ使得三者可以统一量纲,β1、β2、β3表示权重。

2 改进BAS算法

天牛须搜索算法(BAS)是一种生物启发的智能优化算法,是受到天牛觅食原理启发而开发的算法[19]。在天牛觅食的过程中,根据食物气味的强弱来分辨食物的具体位置,天牛有两只长触角,如果左边触角收到的气味强度比右边大,那下一步天牛就往左飞,否则就往右飞,依据这一原理天牛可以找到食物。天牛须搜索算法只需要一个个体就可以完成任务,运算量较小,但算法稳定性较差,全局搜索能力弱容易陷入局部最优。因此,本文在原始BAS算法的基础上对其步长、初始种群等方面进行改进。

2.1 编码与解码

由于家庭医疗人员调度问题涉及老年患者服务顺序部分和医护人员分配部分,所以本文采用两段式编码。用X={X1、X2…XN}表示老年患者服务顺序编码,其中N表示患者数目,X1,…,XN取(1,N)中的任意整数不得重复,0表示医护中心;用Y={Y1、Y2…YM}表示医护人员分配编码,其中M表示医护人员数目,Y1,…,YM取(1,M)中的任意整数可重复,两段编码长度相等。以3位医护人员为8位老年患者提供居家医疗服务为例介绍算法的编码与解码。随机生成的X=[6,3,7,5,1,4,2,8]表示8位老年患者依次的服务顺序,Y=[1,3,1,2,2,1,2,3]表示相应的医护人员分配,解码过程如图2所示。在解码过程中,医护人员根据老年患者服务顺序进行服务安排,且医护人员均有固定工作时间,若即将超过最大工作时间,则返还医护中心结束工作。同时利用罚函数将不符合约束条件与符合约束条件的服务路径区分开来,从而得到有效的服务路径。由此可知1号医护人员的服务路径为0→6→7→4→0,2号医护人员的服务路径为0→5→1→2→0,3号医护人员的服务路径为0→3→8→0。

图2 解码

2.2 改进步长

由于原始BAS算法步长为定值,寻优能力有限,容易陷入局部最优,则通过变步长设计来控制算法的搜索能力。前期采用较大初始步长,随着迭代系数的增加,步长逐渐减小。从最初在全局范围内搜索,到最终进行局部寻优从而求得全局最优解,提高算法的精度。设置步长更改系数为r1∈(0,1)。

step=c*d0

(14)

step=r1*step

(15)

其中c是个常数,表示步长与两触须之间距离的比值,step则表示步长,d0表示两触须之间的初始距离。

2.3 利用混沌理论初始化种群

随机生成的初始种群容易降低最优解的质量,通过利用混沌的遍历性、随机性和规律性的特点对天牛须搜索算法进行初始化,可以使得初始种群遍历整个空间,增加算法找到最优解的概率,加快算法的收敛速度。本文采用Logistic映射模型[20]对天牛的位置进行初始化,回归方程为

Xi+1=4Xi(1-Xi),Xi∈(0,1)

(16)

在种群初始化时,可以提高初始解的质量使得初始种群中的初始解更接近最优解,优于随机产生的初始种群。

2.4 改进BAS算法的步骤

(1)初始化改进BAS算法的参数,更改步长因子参数r1∈(0,1),两触须之间的初始距离d0,最大迭代次数N。

(2)建立天牛触须的随机向量,并做归一化处理。

(17)

其中,rands()为随机向量,n为医护人员和患者的数量。

(3)利用上述混沌初始化方法初始天牛的位置X0,并令最优位置Xbest=X0,根据式(19)和(20)计算天牛左右触须的位置坐标,然后根据式(13)计算左右适应度值Z(x0),最优位置Zbest=Z(Xbest)。

(18)

(19)

其中,Xl、Xr表示左右触须的坐标。

更新迭代次数,p=p+1,根据式(15)更新步长,生成新的方向。确定左右触须的位置Xl,Xr,根据式(13)计算左右触须的适应度值Zl,Zr。根据式(20)计算新一代的天牛的位置,计算新的适应度值Z(Xp)。

(20)

其中sign()表示符号函数,Xp表示第p次迭代更新后天牛的位置。

(4)采用3-opt局部搜索方法,随机选择3个位置调换顺序,若比原来的解好,则接受当前解,否则按照原来的解继续进行下去,进而将天牛的位置进行运算更新。

(5)计算最优适应度值。

(6)判断是否达到最大次数,满足条件则输出最优解,否则跳转至步骤(2)继续进行。

改进的天牛须搜索算法流程图如图3所示。

图3 改进BAS算法流程图

3 算例分析

3.1 算例构造

由于缺乏标准算例,本文仿真算例是在文献[21]的算例基础上进行修改所得。利用3种患者规模的算例来验证改进算法的性能,规模信息如表1所示,基本参数设置如下:为简化算法,考虑到目标函数的重要性程度设β1=0.5、β2=0.3、β3=0.2,参数v=20 km/h,Length=200,系数α=102,γ=-102。

表1 规模信息

为了进一步验证改进BAS算法的有效性,本文将改进BAS算法、GA算法以及PSO算法进行对比分析。其中,改进BAS算法中更改步长因子r1=0.95,系数c=2,初始两触须之间的距离d0=2;GA算法中交叉概率为pc=0.8,变异概率pm=0.1;PSO算法中学习因子c1=c2=1.457,最大最小惯性权重Vmax=-0.5,Vmin=0.5。

3.2 实验结果分析

所有算法均通过MATLAB R2019a编程实现,为保证实验的公平性,在同等种群规模和迭代次数下,取各算法在不同算例规模下分别运算10次的最优值作为最终结果。图4至图6分别为3种规模算例下算法的迭代图,不同规模的仿真结果对比数值如表2所示(其中Z1代表总成本,Z2代表满意度,Z3代表工作时间差)。

表2 不同规模仿真结果对比

图4 改进BAS、GA、PSO迭代寻优曲线(规模20)

图5 改进BAS、GA、PSO迭代寻优曲线(规模40)

图6 改进BAS、GA、PSO迭代寻优曲线(规模60)

在3种规模算例下,改进BAS算法的迭代寻优曲线均优于对比算法(见表2),无论在大、中、小规模中,改进BAS算法获得的方案总成本、满意度水平以及医护人员之间工作均衡性均优于其他算法。

本文选择小规模算例进行具体分析,如表3、表4、图4、图7所示。(其中C1代表医护人员固定成本,C2代表医护人员的惩罚成本,C3/C4代表患者的等待成本或惩罚成本)。

表3 不同算法下医护人员的服务顺序

表4 改进BAS算法、GA算法、PSO算法的仿真结果对比

图7 3种算法运行结果

表3是运用改进BAS算法、GA算法、PSO算法求解医护人员调度方案的结果对比,其中改进BAS算法最满意的调度方案为:编号为3的医护人员的服务顺序为:0-18-7-11-5-6-0,编号为4的医护人员的服务顺序为:0-12-4-17-16-13-0,编号为5的医护人员的服务顺序为:0-20-10-8-14-3-0,编号为6的医护人员的服务顺序为:0-1-15-19-2-9-0。由表4可得在改进BAS算法下的总成本为646.85,满意度为8.54,旅行距离差为4。相较于其他算法,利用本文算法求解案例所得的服务路径明显优于其他算法。该算法生成的调度方案所花费的成本和产生的工作均衡性均优于GA算法和PSO算法,且满意度也较高。

由图4及图7的对比结果可以看出,改进BAS算法通过引入混沌理论进行种群初始化,提高了初始解的质量,使得算法可以在较少的迭代次数内快速收敛。设计3-opt局部搜索方法,提高了算法在求解过程中的寻优性能,当算法陷入局部最优时, 可快速跳出。当迭代至后期时,目标函数趋于平稳。改进BAS算法有效地提高了搜索到最优解的概率,增加了解的多样性与稳定性,而PSO算法和GA算法均存在一定的早熟收敛现象,在种群规模相同迭代次数相同的情况下,本文所提出的改进BAS算法的寻优性能优于GA算法和PSO算法,说明本文所提出的算法可行性较高适合解决居家医疗人员服务路径优化问题。

3.3 敏感度分析

由于BAS算法提出时间相对较短,理论研究较少,参数设置较为敏感,因此,分析不同参数如天牛两须间距、步长等对算法性能的影响具有重大研究意义。

考虑在同等种群规模下,分析天牛两须间距不同对算法性能的影响,分为3种情况:d0=1,d0=2,d0=3。由图8可得,随着天牛两须间距的减小,目标函数值也在逐渐降低,综合效益得到提升。但当间距减小到一定程度时,所得解的多样性与有效性却在降低。因此在一定范围内,间距大小对算法性能影响较为敏感,本文在保持算法求解性能最优的基础上设置d0=2。

图8 不同间距下BAS算法的迭代图

在实际工作过程中,医护人员的工作时间对总成本、满意度以及工作均衡性有着一定的影响。在本研究中,通过设定3种情景:基本工作时间和最大工作时间分别为(6,8)(8,10)(10,12),在不同情景下分别测得结果如表5所示(其中医护人员的单位固定成本为160)。

表5 不同工作时间下的仿真结果

由表5可知,在情景一中医护中心需要派出5名医护人员为20名患者提供服务,此时产生的总成本、工作时间差以及满意度均最大。在情景二中医护中心只需派出4位医护人员就可以完成对20位患者的服务,此时情景二产生的总成本虽然略高于情景三,但是就满意度、工作时间差来说,情景二均优于情景三和情景一。因此,通过采用不同时间窗进行总成本、满意度和工作均衡性对比,可以看出当基本工作时间为8 h,最大工作时间为10 h时产生的总效益最大,此时家庭医疗人员的调度方案最为合理。

4 结论

本文对家庭医疗人员调度问题展开研究,综合考虑患者接受服务的强时效性以及医护人员工作时间的差异性等特点构建调度模型,针对模型设计了带有混沌初始化和3-opt局部搜索方法的改进BAS算法,利用算例以及对比算法验证了改进算法的有效性。仿真结果表明,改进BAS算法可得到实例的最优解,且相较于GA、PSO算法,其搜索能力更强,所得可行解的质量更高,在实际服务系统中,能快速有效地为最优调配决策提供科学依据。

本文研究还存在一些有待改进的地方,如未考虑医护人员和患者之间的技能匹配问题、医护人员工作时间利用率问题,这些问题将是进一步的研究方向。