基于分支定价算法的多时间窗家庭医护人员调度问题研究_李妍峰.pdf

doi:10.3969/j.issn.1007-7375.2023.03.012基于分支定价算法的多时间窗家庭医护人员调度问题研究李妍峰，罗楠，向婷(西南交通大学 经济管理学院，四川 成都 610031)摘要:为了减少医护人员调度成本，提高客户满意度，研究了家庭医疗护理人员调度问题。考虑客户具有多个可接受服务的时间窗，并对不同时间窗具有不同偏好的特性，建立以总运营成本最小、满意度最大为目标的数学模型。基于Dantzig-Wolfe分解原理将所建模型重构为集合划分主问题和含多时间窗的最短路径子问题模型。运用将列生成嵌入分支定界框架中的分支定价算法对问题求解，并根据多时间窗的问题特性设计了快速获得初始解的随机贪心算法和求解子问题的改进标签算法。对50组算例进行测试，将所提出的算法与CPLEX对比，验证了算法的有效性。最后比较单时间窗和多时间窗算例结果发现，客户提供多个可接受服务的时间窗能有效降低调度成本。关键词:家庭医护；多时间窗；改进标签算法；列生成；分支定价中图分类号:TP301文献标志码:A文章编号:1007-7375(2023)03-0107-09Home Health Care Scheduling with Multiple Time WindowsBased on Branch and Price AlgorithmLIYanfeng,LUONan,XIANGTing(SchoolofEconomicsandManagement,SouthwestJiaotongUniversity,Chengdu610031,China)Abstract:Inordertoreducetheschedulingcostofhealthcareworkersandimprovecustomersatisfaction,thehomehealthcare scheduling problem is studied.Considering multiple time windows of customers acceptable service and differentpreferencesfordifferenttimewindows,amathematicalmodelisestablishedwiththeobjectiveofminimizingtotaloperatingcost and maximizing the satisfaction degree.Based on the Dantzig-Wolfe decomposition principle,the model isreconstructedintoasetpartitioningmasterproblemandashortestpathsubproblemwithmultipletimeWindows.Theproblemissolvedbybranchandpricealgorithm,wherethecolumngenerationisembeddedintoabranch-and-boundframework.Accordingtothecharacteristicsofproblemswithmultipletimewindows,arandomgreedyalgorithmtoquicklyobtaintheinitialsolutionandanimprovedlabel-settingalgorithmtosolvethesubproblemaredesigned.TheeffectivenessoftheproposedalgorithmisverifiedbycomparingwithCPLEXthrough50testingnumericalexamples.Finally,bycomparingthe results with single time window and multiple time window examples,it is found that the scheduling cost can beeffectivelyreducedwhencustomersprovidemultipleacceptableservicetimewindows.Key words:homehealthcare;multipletimewindows;improvedthelabel-settingalgorithm;columngeneration;branchandprice近年来，人口老龄化程度不断加深，人们对医疗卫生服务和资源的需求日益增加。家庭医护服务(homehealthcare,HHC)是指家庭护理中心雇佣医护人员在病人家中提供医疗、康复护理和生活照料等第26卷第3期工 业 工 程Vol.26No.32023年6月Industrial Engineering JournalJune2023收稿日期：2021-10-21基金项目：国家自然科学基金资助项目(72071161,71571150)；四川省科技厅应用基础研究重大前沿项目资助(2017JY0225)；西南交通大学智慧物流与供应链管理研究生导师团队资助项目(YJSY-DSTD201918)；四川省科技厅应用基础研究资助项目(2020YJ0220)作者简介：李妍峰(1980)，女，四川省人，副教授，博士，主要研究方向为物流优化、交通优化。服务。该服务不仅可以改善病人的生活条件，而且可以缓解医院拥挤和减少医疗体系增加的费用。一些发达国家如法国、荷兰和瑞典已经建立了较完善的家庭医护服务1-2；我国一些医院和企业也已在上海、北京、广州等城市开始发展家庭医生服务。家庭医护人员调度问题是家庭医护服务运营管理中的核心问题，被描述为医护人员上门为某一地区的病人提供医护服务，决策者需要为医护人员设计一组调度路线优化方案，在考虑诸多约束的情况下尽可能减少运营成本或提高服务质量3。该问题是经典车辆路径问题(vehicleroutingproblem,VRP)的一种扩展，具有另外的特殊约束，例如需要考虑医护人员工作时长限制、客户可以接受服务的时间窗、偏好满意度等，使其更难求解。Fikar等4把它按照决策规划周期分为单周期(以一天为决策周期)调度和多周期(以多天为决策周期)调度问题。目前在单周期家庭医护人员调度问题研究中，多数学者考虑了客户接受服务的时间窗。如Mutingi等5让每个病人在固定时间窗内获得护理者的医护服务，提前到达或迟到则不能服务。Martin等6通过设置医护人员的优先工作时间窗和客户的服务时间窗保证他们各自的时间偏好。Liu等7综合考虑医护人员的午餐休息时间和客户的服务时间窗。Redjem等8解决患者接受多个护理人员在同一时间窗内被服务的问题。Mankowska等9考虑服务之间的时间依赖性，允许医护人员在服务客户时同时违反时间窗。Andrea等10提出通过完成的时间比例衡量客户满意度的软时间窗。Hiermann等11设置时间窗约束可以违反，但有惩罚的代价。关于客户时间窗也存在特别的约束，Bertels等12考虑客户的服务时间窗为硬时间窗包含软时间窗。这些研究仅考虑每个客户进行医疗护理的一天中只有一个可接受服务的时间窗。然而在实际中，客户可能存在一天有多个可接受服务的时间窗，同时对时间窗偏好满意度不同。结合实际运营，本文考虑客户的服务时间窗多个可选，并对时间窗从偏好满意度进行评价。目前对于该类问题的求解算法主要分为两大类：启发式算法5-6,8-12和精确算法7。大部分研究选用启发式算法，例如禁忌搜索算法、模拟退火算法、邻域算法、蚁群算法、混合启发式算法等。这些算法可以在较短时间内求出近似解，但解的精度较低。小部分研究采用精确算法，例如有分支定界、分支切割、分支定价等，这些算法可以求出最优解，保证解的质量。本文结合多时间窗特征设计分支定价算法获得最优解。单周期家庭医护人员调度问题研究中缺乏考虑多个服务时间窗可选以及时间窗存在偏好不同的情形，较少采用精确算法提高解的精度。基于此，本文考虑客户存在多个服务时间窗、医护人员工作时间限制等特征，并用惩罚成本表示客户不同时间窗的满意度(惩罚成本越低表示客户满意度越高，惩罚成本越高表示客户满意度越低)，建立以运营成本最小化满意度最大化为目标的模型。结合多时间窗特性，设计基于列生成的分支定价算法求解该问题的精确解。最后，通过多组算例测试，将结果与CPLEX对比，验证了本文算法的有效性和高效性。1 问题描述及模型建立 1.1 问题描述G=(V,A)V=N0,n+1A=(i,j)|i,j V,i jN=1,2,3,nV1=N0V2=Nn+1i Ngiawi,bwiWi=1,2,3,whwitijcijK=1,2,3,mfkk K多时间窗家庭医护人员调度问题描述如下。给定一个有向欧氏图，是所有点的集合，是弧集。其中点0和点n+1分别代表护理中心的起点和终点，是客户点集合。定义客户点和起点集合为，客户点和终点集合为。每个客户对应的地理位置和服务时间 已知，并且每个客户具有多个互不重叠的服务时间窗，其服务时间窗集合定义为，不同的时间窗对应不同的偏好满意度，以表示第i个客户的第w个时间窗的偏好惩罚成本。医护人员可以选择其中一个时间窗服务客户，每个客户只能被一个医护人员服务一次，若医护人员在时间窗左端前到达，需要等待时间窗开启才可服务。客户(i,j)之间的旅行时间和成本分别为 和。所有医护人员集合为，固定成本为的医护人员从护理中心出发，每天需要在工作时间窗0,T内对客户进行服务，服务完毕后返回护理中心。问题以最小运营成本和最大客户满意度为目标建数学模型。sikzwikxijk为了描述模型还需定义以下变量：为医护人员k在客户i处的开始服务时间；为0-1变量，医护人员k在客户i的第w个时间窗服务时为1，否则为0；为0-1变量，医护人员k先服务客户i，后服务客户j时为1，否则为0。108工业工程第26卷 1.2 数学模型基于以上问题描述和数学符号，建立以下多时间窗家庭医护人员调度问题模型P。minjNkKfkx0jk+kKiV1jV2cijxijk+kKiNwWihwizwik+kKiNwWihwizwik。(1)s.t.kKjV2xijk=1,i N;(2)jV2x0jk=1,k K;(3)iV1xi(n+1)k=1,k K;(4)jV2xijk=jV1xjik,i N,k K;(5)iVxi0k=0,k K;(6)jVx(n+1)jk=0,k K;(7)sik+gi+tijsjkM(1xijk),iV1,jV2,kK;(8)0sikT,i N,k K;(9)iV1xijk=wWjzwjk,j N,k K;(10)awiM(1zwik)sik,i N,k K,w Wi;(11)sikbwi+M(1zwik),i N,k K,w Wi;(12)xijk 0,1,i V,j V,k K;(13)zwik 0,1,i V,k K,w Wi。(14)k式(1)表示最小化运营成本(包括固定成本和路途成本)和惩罚成本；式(2)表示每个客户只能由一个医护人员服务；式(3)(5)表示每个医护人员从护理中心出发，访问客户后，最后回到护理中心；式(6)表示医护人员不能返回点0；式(7)表示医护人员不能从点n+1出发；式(8)表示医护人员相继到达两个客户的时刻之间的关系；式(9)表示医护人员在工作时间窗内服务；式(10)表示第 个医护人员到达客户j并在其中一个时间窗内服务(保证变量xijkzwikk和 的一致性)；式(11)、(12)保证第 个医护人员满足第i个客户的第w个时间窗约束；式(13)、(14)表示决策变量为0-1变量。2 列生成Dantzig等13在1960年提出列生成算法的理论基础，随后列生成算法快速发展，常被应用于求解含有众多变量的大规模整数规划问题。算法伪代码具体可以参照文献14，核心步骤如下所示。步骤步骤1将问题模型通过Dantzig-Wolfe分