基于分支定价算法的多时间窗家庭医护人员调度问题研究.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分解为集合划分主问题(masterproblem,MP)模型和定价子问题(sub-problem,SP)模型。步骤步骤2将主问题模型中的整数约束松弛，得到线性松弛问题。步骤步骤3使用随机贪心算法初始化线性松弛问题，得到受限主问题(restrictmasterproblem,RMP)。步骤步骤4求解RMP，得到对偶变量，传递对偶变量值给定价子问题。步骤步骤5用改进动态规划算法求解定价子问题，如果定价子问题的目标函数全为非负，得到RMP的最优解，算法结束；否则找到定价子问题中目标函数为负的列加入RMP，跳转步骤4。2.1 基于Dantzig-Wolfe分解的模型重建模型P是一个混合整数规划模型，当问题规模变大时，变量与约束条件增加，求解变得复杂，难以获得精确解。由Dantzig提出的Dantzig-Wolfe分解原理可以把复杂的线性规划模型转换为若干规模较小的子规划，从而降低求解复杂度，本文运用此原理将模型分解为基于访问路线的主问题模型和定价子问题模型。2.1.1主问题模型为了呈现主问题模型，定义以下变量和参数。r为访问路径；R为所有可行的访问路径集合；fr为访问路径r的固定成本；cr为访问路径r的总成本；zwir表示在路径r的客户i的w时间窗开始服务为1，反之为0；ijr表示路径r经过弧(i,j)为1，反之为0；ir表示路径r经过客户i为1，反之为0；r表示在最优解中医护人员选择路径r为1，反之为0。第3期李妍峰，罗楠，向婷：基于分支定价算法的多时间窗家庭医护人员调度问题研究109由上述变量和参数关系可知：cr=fr+iV1jV2ijrcij+iNwWihwizwir,r R;(15)ir=jV2ijr,i N,r R;(16)xij=rRijrr,i V1,j V2。(17)将上述3个式子代入模型P，经过变换整理可以得到MP模型。minrRcrr。(18)s.t.rRirr=1,i N;(19)rRrm;(20)r 0,1,r R。(21)rR当找到部分可行路径，加入以上模型计算，就可得到RMP，再计算对偶变量值，传递对偶变量值给定价子问题，列生成算法便可进行下去。2.1.2定价子问题模型根据对偶理论，RMP的对偶模型如下。maxiNi+m0。(22)s.t.iNiri+0cr,r R;(23)i R(i N),00。(24)i0以上、分别为约束(19)、(20)对应的对偶变量。RMP检验数(reducedcost)为cr=criNiri0=fr+iV1jV2ijr(ciji)+iNwWizwirhwi。(25)cr0根据单纯形法原理，把求出检验数的路径加入主问题模型中迭代，可以优化主问题目标函数值。定义以下变量。f表示对应路径的固定成本；si表示在路径中到达客户i的时间；xij表示该路径经过弧(i,j)为1，反之为0；zwi表示该路径在客户i的w时间窗开始服务为1，反之为0。由以上描述可知定价子问题模型为min f+iV1jV2xij(ciji)+iNwWizwihwi。(26)s.t.jV2x0j=1;(27)iV1xi(n+1)=1;(28)jV2xij=jV1xji1,i N;(29)jV2xij=wWizwi1,i N;(30)0siT,i V;(31)si+gi+tijsjM(1xij),i V1,j V2;(32)awiM(1zwi)si,i N,w Wi;(33)sibwi+M(1zwi),i N,w Wi;(34)xij 0,1,i V,j V;(35)zwi 0,1,i V,w Wi。(36)式(26)表示最小化主问题的检验数(路径成本)；式(27)(29)表示从起点出发访问客户再返回终点；式(30)表示到达客户并选择在一个时间窗服务；式(31)表示医护人员在工作时间窗内服务；式(32)表示访问前后的连续性；式(33)、(34)保证路径满足客户时间窗要求；式(35)、(36)表示决策变量为0-1变量。2.2 改进动态规划算法求解定价子问题定价子问题通常称为一类带资源约束的基本最短路径问题(elementaryshortestpathproblemwithresourceconstraints,ESPPRC)，普遍用动态规划算法求解15。本文带多时间窗的最短路径定价子问题是一个NP-Hard问题，根据定价子问题的多时间窗的特点设计动态规划算法，它的实质为标签算法(thelabel-settingalgorithm)。通过标签记录每个客户点的状态信息，从一系列的标签中得到医护人员访问客户的路径信息。本文基于文献16-17提出改进标签算法，算法由标签定义、扩展规则与支配规则构成。110工业工程第26卷2.2.1标签定义(i,wi,i,ci,Vi,Di)在动态规划算法中，标签包含多种资源变量，医护人员每访问一个客户点就形成一个标签状态，每个标签状态由标签表示。标签中各个元素定义如下。i为当前访问的客户点i；wi为在客户点i处选择的服务时间窗；sii为医护人员在客户点 处的开始服务时间；ci为路径到达客户点i的检验数(路径总成本)；Vi记录客户点i能到达的客户点集合，到达为1，否则为0；Di记录标签的支配状态，未被支配记为false，被支配记为true。2.2.2扩展规则(i,wi,si,ci,Vi,Di)=(0,0,0,0,N,false)V(i,wi,si,ci,Vi,Di)j Vi(j,wj,sj,cj,Vj,Dj)从护理中心0开始生成初始标签，然后通过扩展规则生成新的标签，一直重复到不可扩展。标签的扩展需要根据当前客户可到达集合 向其他客户点扩展，从而得到另一客户点的新标签。当前客户i的标签为，沿着弧(i,j)扩展到客户的新标签为，其扩展规则如下。wj=w1)；sj=maxsi+gi+tij,awjj2)；cj=ci+cij=ci+cij+hwjj0.5(i+j)3)；Vj=Vil:(j,l)A and sj+gj+tjl+glbwl,w Wl j4)；Dj=false5)。扩展过程中，每次扩展需要满足客户的时间窗以及医护人员的工作时间窗要求，当标签扩展到n+1时，遍历这些标签则可以找到医护人员的访问路径。2.2.3支配规则iLi(i,wi,si,ci,Vi,Di)Li(i,wi,si,ci,Vi,Di)LiLi当问题的规模逐渐增大时，标签的数量呈指数增加，标签算法的效率逐步降低，通过支配规则可以减少标签的数量，提高标签算法的效率。假设有访问节点 的两个不同的标签和，符合以下支配规则时，标签支配。sisiciciViVi1)；2)；3)。LiLiLiLiLi支配规则通常满足如下原则。对于点i的不同标签 和等，若 标签的可扩展操作都是的一个可扩展操作，即从 标签对应的子路径扩展到其他顶LiLiLiLiLi点形成的新标签均可由对应的子路径扩展得到，同时从标签对应子路径扩展得到的路径费用均少于从标签对应路径扩展得到的路径费用，标签支配。LiLiViViLiLiR(Li)Lic(r)cicic(Li+)=ci+cc(Li+)=ci+c(R(Li)LiLiLiLi对于同时到达i点的两个标签 和，通过能到达的客户点集合V扩展标签，由于，则由标签可扩展的标签包含所有 标签扩展的标签。假设表示从出发扩展到终点的所有子路径集合，表示路径r的总成本(检验数)，则因为。故有，由此可知从标签对应子路径扩展得到的路径费用均少于从对应路径扩展得到的路径费用，标签支配。3 分支定价算法上一节描述的求解大规模线性规划问题的列生成算法，求出的解不一定是整数解，因此需要把列生成算法嵌套到分支定界算法的框架中，构成分支定价算法，求得最优整数解。3.1 分支定价算法的流程图分支定价算法主要由列生成算法和分支定界算法构成，其分为两层，外层为求出原问题整数解的分支定界，内层为求出原问题线性松弛问题解的列生成。在分支定界的搜索树的每个节点上，使用列生成算法求解，列生成算法主要构成是定价子问题的求解。本文完整的分支定价算法求解框架如图1所示。3.2 RMP的初始化分支定价算法中，利用列生成算法求解根节点的线性松弛问题，需要对RMP进行初始化，即找到可行路径，作为初始列加入RMP，求出对偶解，计算定价子问题。在大多数情况下，使用启发式方法求解，可以获得较优的初始解决方案，最终显著减少列生成过程中生成的列的数量18。初始解可以由一条或多条路径组成，必须保证每个客户被服务，满足时间窗要求。目标函数由固定成本、路途成本、惩罚成本组成，同时考虑3个目标会使得初始路径的生成变复杂，为了快速生成较优的初始解，本文使用随机贪心算法，只考虑路途成本的变化，忽略其他成本，等客户分配完成，再重新计算路径总成本。算法基本思想如下。步骤步骤1判断待分配客户集合是否为空，若为空，算法结束，否则随机选择一个客户，作为第第3期李妍峰，罗楠，向婷：基于分支定价算法的多时间窗家庭医护人员调度问题研究1111个被服务的客户与护理中心形成路径，转向步骤2。步骤步骤2判断待分配客户集合是否为空，若为空，算法结束，否则选择离上一个客户路途成本最低的客户作为下一个被服务的客户，同时检查是否符合时间窗要求，符合则加入路径并且重复步骤2，不符合则转向步骤1。3.3 分支策略xij=r Rijrrxij(i,j)(i,j)(i,j)ji分支定价算法效率的提升还需制定有效的分支策略，一个有效的分支策略可以在维持搜索树平衡的前提下快速剪掉分数解同时找到整数解。本文采用Zhang等19使用的基于弧的分支策略，当医护人员是否经过弧(i,j)的变量为分数时，本文选择最优解中最接近0.5的弧分支，直到找到整数解，分支产生的两个子节点，需要对子节点中的数据进行处理。如果第1个分支选择弧，为了保证最优解中存在弧，需要将其他所有到达客户 点的弧和其他所有离开客户点 的弧删除，(i,j)(i,j)(i,j)(i,j)并在已经生成的访问路径中删除包含这些弧的路径，重新计算；那么第2个分支就删除弧，为了保证最优解中不存在弧，需要将弧删除，并删除已有访问路径中包含弧的路径，再重新计算。4 数值实验本节首先介绍如何生成测试算例，然后对惩罚成本进行灵敏度分析，再将本算法与CPLEX计算结果相比较，测试算法性能，最后对单时间窗和多时间窗算例进行特性分析。本文所提出的分支定价算法采用Java编程实现，所有数据在处理器为11thGenIntel(R)Core(TM)i7-1165G72.80GHz(8CPUs),1.7GHz的计算机上进行实验。4.1 测试算例目前没有针对本问题的标准算例，参考Solomon20提出的标准VRPTW算例生成方法，结合本文特征随机生成包含10、20、30、40、50个客户算例各10组，否是否是标签算法选择节点求解 RMP删除节点更新上界是是否否L=IP上界=+下界=开始把 Reduced cost0的列加入 RMP搜索树是否为空？或上界=下界？输出最优解构建 RMP传递对偶变量求解定价子问题是否 Reducedcost上界？是否为分数解？更新下界分支并生成子节点列生成计算随机贪心算法图 1 分支定价算法流程图Figure 1 Flowchart of branch and price algorithm112工业工程第26卷dijtijcijdijaw0+t0i,bw0t0igi生成算例方法如下。在二维平面0,1002内随机产生n个客户点坐标，护理中心位于(0,0)，两点间的距离定义为欧氏直线距离。为了方便计算，令路途时间 和成本在数值上等于其距离。客户的服务时长为均匀分布在U30,60间的随机整数，每个客户最多生成两个服务时间窗，时间窗由时间窗中心和宽度构成，分别为均匀分布在U和U60,90间的随机整数。两个时间窗的惩罚成本设置为均匀分布在U0,5或U25,30间的随机整数。假设医护人员的固定成本为50，工作时间窗为0,480。其中算例名称R10_1表示随机生成的第1组包含10个客户点的算例，其他符号具有类似含义。4.2 惩罚成本灵敏度分析h1h2h1=1h2=1,2,3,50为清楚体现时间窗惩罚成本设置对求解结果存在的影响，假设每个客户存在的两个时间窗惩罚成本分别为 和，其中固定惩罚成本，惩罚成本。生成一个包含20个客户的算例进行灵敏度分析，其坐标、服务时间、时间窗的生成方法与上文测试算例描述相同。根据算例测试结果如表1所示，依次列出运营成本(包括固定成本和旅行成本)、总成本(包括运营成本和惩罚成本)和访问路线。h2h2h225h2h2由表1可知，随着惩罚成本 逐渐增大，运营成本和总成本也逐渐增加，增大的幅度对调度方案会造成不同程度的影响；但在一定范围内变化时，不会使得运营成本增加和访问路线改变。如在47、810之间变化，运营成本和访问路线不发生变化；当，运营成本和访问路线不再变化。这是因为在问题目标中考虑了客户的偏好程度，随着增大，会优先选择较小的时间窗服务，进而影响了医护人员的访问路线。4.3 算法性能分析使用精确算法求解器CPLEX对模型进行计算，将结果与本文的分支定价算法计算结果作比较，验证模型的正确性和算法的有效性。随着客户数量的增加，CPLEX不能求解大规模的数据，实验过程中设置CPLEX最长运行时间为7200s。测试结果见表2表4，表中依次列出了分支定价算法的成本(Cost1)、时间(T)、上界与下界的Gap%，以及CPLEX计算的成本(Cost2)、时间(T)、Gap%，以及CPLEX与分支定价算法得到最优解的相对偏差RGap%(Cost2Cost1)/Cost1)。由表2可知，在以上10组客户数量为10的算例中，两者结果的一致性验证了本文提出的模型与分支定价算法的正确性；分支定价算法在平均计算时表 1 不同惩罚成本算例结果1)Table 1 Results of instances with different penalty惩罚成本运营成本总成本访问路线h1=1,h2=11159.21179.20-5-16-8-19-7-21,0-15-1-3-2-13-21,0-18-14-17-4-6-21,0-9-20-11-12-10-21h1=1,h2=21159.91190.90-15-5-16-3-1-21,0-8-19-7-2-13-21,0-18-14-17-4-6-21,0-9-20-11-12-10-21h1=1,h2=31201.9h1=1,h2=41162.31212.30-15-5-16-3-1-21,0-8-19-2-7-13-21,0-18-14-17-4-6-21,0-9-20-11-12-10-21h1=1,h2=51222.3h1=1,h2=61232.3h1=1,h2=71242.3h1=1,h2=81174.51258.50-15-5-16-3-1-21,0-8-19-2-7-13-21,0-18-14-17-4-6-21,0-9-12-11-20-10-21h1=1,h2=91266.5h1=1,h2=101274.5h1=1,h2=111223.11273.10-6-15-4-5-21,0-2-7-13-21,0-19-8-3-1-21,0-9-18-14-17-16-21,0-10-12-11-20-21h1=1,h2=121276.1h1=1,h2=131279.1.h1=1,h2=241312.1h1=1,h2=251269.31313.30-15-6-4-5-7-21,0-2-13-21,0-19-8-3-1-21,0-9-18-14-17-16-21,0-10-12-11-20-21h1=1,h2=261314.3h1=1,h2=271315.3.h1=1,h2=501338.31)加下划线的路径表示较上一次发生变化。表 2 包含10个客户算例结果Table 2 Results of instances with 10 customers实例分支定价算法CPLEXRGap%Cost1T/sGap/%Cost2T/s)Gap/%R10_1728.500.120.00728.502951.810.410.00R10_2685.000.101.81685.009.7510.460.00R10_3869.500.120.27869.505586.202.760.00R10_4766.100.090.12766.10999.661.740.00R10_5770.900.120.20770.901632.133.220.00R10_6848.100.180.22848.101569.002.740.00R10_7805.800.070.00805.803153.742.640.00R10_8875.200.110.69875.201530.771.460.00R10_9911.400.070.09911.401922.962.150.00R10_10610.500.100.00610.50410.191.930.00均值0.100.341976.622.950.00第3期李妍峰，罗楠，向婷：基于分支定价算法的多时间窗家庭医护人员调度问题研究113间0.1s求得最优解，所得的Gap均值为0.34%。相比之下，CPLEX的平均计算时间为1976.62s，计算得到Gap均值2.95%，均不如本文提出的分支定价算法的表现好，故分支定价算法对于小规模算例在求解质量和求解效率上存在优异表现。由表3可知，在以上10组客户数量为20的算例中，分支定价算法在平均计算时间为1.73s内获得最优解，所得的Gap均值为0.15%。相比之下，CPLEX在2h内没有得到最优解，计算的Gap均值为69.83%，远远大于分支定价算法的Gap(0.15%)，并且CPLEX与分支定价算法得到最优解的相对偏差平均值为5.27%，最高偏差可达12.87%。因此说明分支定价算法可以更快地找到问题的下界，并求出最优解；对于较小规模案例，验证了本文设计的分支定价算法在求解质量和求解效率上表现更优异。由表4可知，对以下10组各包含30、40、50个客户的算例而言，分支定价算法分别在平均67.99s、121.09s、310.78s求出最优解，所得的Gap均值分别为0.10%、0.05%、0.03%。由于CPLEX在2h内未得到可行解，故在表中没有列出。随着客户人数的增加，计算时间也呈现上升的趋势，对于同一规模大小的算例，求解时间存在大小差异，说明分支定价算法性能不仅与问题的规模存在联系，还受数据特征影响。对于较大规模算例的求解时间在可接受范围内可以找到最优解。表 4 包含30、40、50个客户算例结果Table 4 Results of instances with 30,40 and 50 customers实例分支定价算法实例分支定价算法实例分支定价算法Cost1T/sGap/%Cost1T/sGap/%Cost1T/sGap/%R30_11779.804.020.08R40_12526.00140.920.03R50_12542.8063.800.00R30_21742.002.530.10R40_22168.30161.430.06R50_22667.20105.260.01R30_31834.8015.710.05R40_32250.108.020.03R50_32967.10442.220.06R30_41873.203.350.02R40_42312.8043.750.03R50_42715.60505.650.02R30_52083.60302.280.00R40_52234.80113.620.07R50_52460.10116.290.00R30_62021.4022.090.22R40_62299.10188.880.01R50_62797.30178.000.13R30_72056.8011.150.12R40_72321.1020.690.05R50_72651.20532.150.01R30_82021.90229.660.22R40_82303.80250.930.14R50_82595.8053.890.08R30_91813.9055.620.08R40_92216.90247.900.08R50_92757.20493.670.02R30_101850.7033.450.08R40_102360.6034.720.00R50_102632.50616.840.01均值67.990.10均值121.090.05均值310.780.03 4.4 成本计算分析本节生成一个包含50个客户的多时间窗算例和单时间窗算例(保留同一算例中惩罚成本较低的时间窗)，对固定成本、路途成本、运营成本(包含固定成本和路途成本)三方面进行比较分析。首先在多时间窗的情况下，比较考虑客户满意度最大化与不考虑客户满意度算例的求解结果，如图2所示。其次在不考虑满意度情况下比较单时间窗和多时间窗算例的结果，如图3所示。由图2可知，在多时间窗的情况下考虑最大化表 3 包含20个客户算例结果1)Table 3 Results of instances with 20 customers实例分支定价算法CPLEXRGap%Cost1T/sGap/%Cost2T/sGap/%R20_11161.300.870.151164.70720063.780.29R20_21313.100.160.001359.70720068.773.55R20_31243.702.740.201344.90720069.258.14R20_41545.401.250.111626.80720075.235.27R20_51368.303.090.121376.60720064.340.61R20_61329.601.670.181332.70720071.660.23R20_71095.000.370.001214.40720072.2110.90R20_81343.801.090.291449.30720071.617.85R20_91357.504.110.271397.94720070.162.98R20_101286.601.960.181452.15720071.3112.87均值1.730.15720069.835.271)加下划线表示非最优解。114工业工程第26卷客户满意度的家庭医护人员调度比不考虑客户满意度运营成本增加了5.18%，路途成本增加了6.51%，固定成本相同。增加了路途成本的原因主要是在为了使客户满意度最大化，选择了客户满意度最高的时间窗内进行服务，路途长度变大增加了路途成本进而增加了运营成本。运营机构需要在客户满意度和成本之间进行平衡。由图3可知，多时间窗的算例比单时间窗算例节约了17.83%的运营成本。客户有多个时间窗可以接受服务时，医护人员的调度变得更加灵活，访问路径中可以服务更多客户，减少了医护人员数量，于是固定成本和路途成本分别下降了11.11%和19.56%。因此，在实际中，护理机构可以鼓励客户提供多个可接受服务的时间窗使得调度方案更加弹性，也可进一步降低服务成本。5 结束语本文研究了考虑多时间窗的单周期家庭医护人员调度问题，对客户的多个时间窗设置惩罚成本表示客户的满意度，以运营成本最小化和客户满意度最大化为目标建立数学模型。为求出模型最优解，设计了分支定价算法求解，制定了随机贪心算法快速求得初始解。根据多时间窗的问题特点，设计了改进的动态规划算法求解定价子问题以便快速找到限制主问题中的列。最后通过多组算例证明了本文模型和算法的可靠性，验证了分支定价算法求解该问题的优越性。此外，还分析了单时间窗算例和多时间窗算例的特性。未来可考虑多周期的情形，也可进一步优化改进动态规划算法，增加启发式算法求解定价子问题，设计更有效的加速策略优化分支定价算法。参考文献：LIUR,XIEXL.Heuristicalgorithmsforavehicleroutingprob-lemwithsimultaneousdeliveryandpickupandtimewindowsinhomehealthcareJ.