居家护理行程和调度文献综述

摘 要：家庭卫生保健路由和调度问题（The home health care routing and scheduling problem，HHCRSP）包括设计一组由护理人员使用的路径，向必须在家接受治疗的患者提供护理服务。HHCRSP是车辆路径问题（vehicle routing problem，VRP）的一个扩展，具有不寻常的边约束，使得问题难以求解。为了解现有的研究成果，本文首先确定了HHCRSP模型中考虑的最相关的特征，然后从模型的约束和目标函数两方面重点分析现有文献。

关键词：居家护理;车辆路径问题;特征

Abstract：The home health care routing and scheduling problem（HHCRSP）involves designing a set of paths used by nursing staff to provide nursing services to patients who must receive treatment at home.HHCRSP is an extension of vehicle routing problem（VRP），which has unusual edge constraints，making the problem difficult to solve.In order to understand the existing research results，this paper first determines the most relevant features considered in HHCRSP model，and then analyzes the existing literature from two aspects of model constraints and objective function.

Keywords：home health care;vehicle routing problem;features

HHCRSP問题可以描述为：护理人员上门为患者提供护理服务，如注射药物、康复训练、心理疏导等[1]。该问题重点在于设计一组路线，在满足若干限制条件的同时使成本最小化或使服务质量最大化。HHCRSP问题类似于VRP问题，主要目的是设计一组服务于所有患者的路径，而两者又不完全相同，因为HHCRSP问题的特性，产生了新的约束。以下特征使该问题更具挑战性：（1）护理的连续性确保每个患者被分配到一组有限的护理人员。当一个病人在计划期内由唯一护理人员访问时，即为“完全连续的护理”。（2）护理服务之间可能存在时间依赖和析取服务关系。例如一项服务应在另一项服务之后开始，或不能同时向患者提供两项服务。（3）考虑护理人员和患者的特点，护工会有资格/技能限制，患者也可能对护理人员的偏好、语言等方面有特定要求。

一、HHCRSP模型中约束考虑的特性

现有HHCRSP模型约束中考虑的特征反映了居家护理（The home health care，HHC）操作的多样性。这些约束可以分为三组：时间约束、分配约束和地理约束，主体涉及HHC服务组织、病人和护理人员，具体见下表。

（一）与HHC组织相关约束

（1）时间约束。路由决策中的“计划周期”是指HHC计划分配和路由决策的时间段。HHCRSP模型中考虑的计划期限通常为一天[2]或一周[3]。Hewitt等人[4]将计划期限延长至两到三个月，但是大多数论文考虑的还是一周或更短的计划期限，通常以滚动的方式延长期限[5]。“路由决策频率”是指路由决策在计划周期内重复的频率。决策可能是因为病人和护理人员的可用性发生变化，所以可以在固定的时间间隔内修改路由决策，也可以在满足某些条件时进行更新[6]。（2）分配约束。分配约束与护理的连续性有关，也被称为病人—护士忠诚性或员工的规律性[7]。对病人的护理服务一般分为全部、部分或无连续护理。在完全连续护理下，HHC提供者将患者分配给一名且仅一名护理人员，负责患者在HHC服务期间的全部护理。在病人需要一种以上护理的情况下，通常可以观察到部分连续性护理。在无持续护理的情况下，提供者不需要完全参照护理人员上一批患者分配信息。大多数在满足时间和任务限制的情况下，很难为同一个患者保留相同的护理人员，所以该约束通常被视为软约束[8]。完全和部分连续性护理可以混合使用[9]，对于每周需要一次或两次就诊的患者，指派相同的护理人员进行就诊。（3）地理约束。HHC中心可以根据地域、护理人员技能和患者需求等相关标准，决定将现有团队集中在某区域内，这样可以减少在指定的区域内护理人员的行程时间，并组建更容易管理的小型护理团队。Eveborn等人[10]考虑的多地区案例中，每个地区可以作为一个中心独立管理。

（二）与患者相关约束

（1）时间约束。针对患者所需就诊频率的限制而言，一些研究认为患者应每天服务一次[11]，一些研究允许患者一天访问多次[12]。大多数研究会给患者分配一个时间窗，可以是硬时间窗[13]或软时间窗[11]。前者护理人员必须在时间窗内安排访问，后者则可以违反时间窗。Bertels等[14]认为每种服务包含两种类型的时间窗，软时间窗包含在服务必须开始的硬时间窗中。护理人员的访问可能有时间依赖关系。一种情况是（依赖性路由）访问可能需要多个护理人员提供协同服务。Eveborn等人[10]考虑了协同服务，从而确定护理人员共享访问的最佳时间。另一种情况是（路径内的依赖性）服务之间存在优先关系，必须先进行某一项服务。Kergosien等人[15]引入析取服务的概念，即两个服务不能同时执行，这种限制决定了每一个护理人员对病人的访问顺序。（2）分配约束。在病人的偏好方面，患者会根据个人偏好选择护理人员，如文献[16]以病人的性别不适合拒绝护理人员服务。（3）地理约束。根据环境（农村或都市）和患者家庭分散在该地区的位置，护理人员的行程时间可能有所不同。Rest和Hirsch[17]提出了城市中考虑时间依赖性的出行时间的模型，因为该时间会根据某些时间段发生很大的变化，例如高峰时间或非高峰时间出行时间有所不同。

（三）与护工相关约束

（1）时间约束。合同护理人员可以是全职、兼职或外包员工。为了满足护理人员合同的特点，一些研究引入了多种合同类型。例如有些模型区分全职和兼职护理人员[18]，他們不受相同的约束，而且每种类型的合同的成本也不同。（2）分配约束。第一种类型的分配约束与工人资格有关。护理人员必须满足资格/技能要求，以提供特定的服务。Cire和Hooker[19]认为每个护理人员都应该有一个资格等级，并且每项服务也需要一个等级，代表该服务需要护理人员的最低等级。第二类任务限制与工作量平衡[20]有关，从而保持员工的积极性。由于很难获得工作量的完美平衡，这种约束通常嵌入到目标函数中，视为一种软约束来评估护理人员的工作量。（3）地理约束。大多数研究考虑的是单一的HHC中心，每个护理人员的路线都必须从这个中心开始和结束，这也被称为车辆路径中的单站点问题。相对而言多站点问题的情况[13]较少被考虑，如果服务区域很大，可以有一个以上的医疗保健中心。

三、HHCRSP模型中考虑的目标函数特性

（一）最小化总路由成本

总路由成本最小化是VRP的一个标准准则。成本包括行程成本、行程时间和行程距离，因为它们都息息相关。

（二）最小化未分配服务的数量

当HHC没有足够的护理人员为所有患者提供服务时，无法分配的服务通常分包给另一个HHC中心，而分包成本[21]总是高于内部执行的成本。

（三）最大化满意度

第一种情况是满足患者的偏好，Braekers等人[20]最大化了患者对护士和就诊时间的偏好。由于尊重所有的偏好是困难的，这些约束通常是软约束。

第二种情况是满足护理人员的偏好，主要标准是工作量平衡。为了满足这一标准，有人提出了两种方法：一是平衡分配的服务数量;二是尽量减少加班时间提升护理人员满意度。

四、求解算法

HHCRSP问题的求解方法有精确算法和启发式算法两大类。由于精确算法的计算量随着客户点的增多呈指数级增加，在实际中应用有限，而启发式算法则具有全局搜索能力强、求解效率高的特点，求出的解也具有较好的参考性，因此，目前大部分研究者们主要把精力集中在如何构造高质量的启发式算法上，其中研究较多的主要有遗传算法[22]、模拟退火算法[23]、蚁群算法[24]和粒子群算法[25]等。

五、总结与展望

本文通过分析HHC组织中涉及的典型特征进行了文献梳理，重点介绍在现有模型中如何将这些特征作为约束条件或在目标函数中需要满足的准则。当然现有的研究也是不全面的，后续还可以考虑多个时间窗等特性。目前研究中假设患者不能离开自己的家，接受全天护理服务，现实中他们可能希望某些时段不受打扰，比如午餐时间等。考虑多个时间窗将使路线的评估更加复杂，因为就诊时间窗的选择并不简单。另一方面，现有的研究大多集中在确定性HHCRSP模型上，没有考虑不确定性因素。不同的参数涉及不确定性，例如两个不同地点之间的行程时间、护理服务持续时间、突发路况等。在现实中，随机事件可能造成护理人员的路线被重新安排。因此，对现有的模型进行这样的扩展也是今后的研究方向。

参考文献：

[1]陈醒，秦月兰，石泽亚，汤珂，李珍，申微.患者“互联网+”居家护理服务需求调查及参与现状的影响因素分析[J].中华现代护理杂志，2020，26（28）：38693875.

[2]D.S.Mankowska，F.Meisel，C.Bierwirth，The home health care routing and scheduling problem with interdependent services.，Health Care Manage.Sci.2014，17（1）：1530.

[3]J.F.Bard，Y.Shao，A.I.Jarrah，A sequential GRASP for the therapist routing and scheduling problem，J.Sched.2014，17（2）：109133.

[4]M.Hewitt，M.Nowak，N.Nataraj，Planning strategies for home health care delivery，AsiaPac.J.Oper.Res.2016，33（5）.

[5]A.R.Bennett，A.L.Erera，Dynamic periodic fixed appointment scheduling for home health，IIE Trans.Healthc.Syst.Eng.2017，1（1）：619.

[6]J.F.Bard，Y.Shao，H.Wang，Weekly scheduling models for traveling therapists，Soc.Econ.Plann.Sci.2013，47（3）：191204.

[7]S.Nickel，M.Schrder，J.Steeg，Midterm and shortterm planning support for home health care services，European J.Oper.Res.2019，219（3）：574587.

[8]T.Macdonald，K.Drner，X.Gandibleux，Metaheuristics for the consistent nurse scheduling and routing problem.Masters thesis，Université de Nantes.2009：130.

[9]P.M.Duque，M.Castro，K.Srensen，P.Goos，Home care service planning.The case of Landelijke Thuiszorg，European J.Oper.Res.2015，243（1）：292301.

[10]P.Eveborn，P.Flisberg，M.Rnnqvist，Laps Care—an operational system for staff planning of home care，European J.Oper.Res.2016，171（3）：962976.

[11]G.Hiermann，M.Prandtstetter，A.Rendl，J.Puchinger，G.R.Raidl，Metaheuristics for solving a multimodal homehealthcare scheduling problem，CEJOR Cent.Eur.J.Oper.Res.2013，23（1）：89113.

[12]M.S.Rasmussen，T.Justesen，A.Dohn，J.Larsen，The home care crew scheduling problem：Preferencebased visit clustering and temporal dependencies，European J.Oper.Res.2012，219（3）：598610.

[13]C.Akjiratikarl，P.Yenradee，P.R.Drake，PSObased algorithm for home care worker scheduling in the UK，Comput.Ind.Eng.2017，53（4）：559583.

[14]S.Bertels，T.Fahle，A hybrid setup for a hybrid scenario：Combining heuristics for the home health care problem，Comput.Oper.Res.2006，33（10）：2866 2890.

[15]Y.Kergosien，C.Lenté，J.c.Billaut，Home health care problem：An extended multiple traveling salesman problem，in：4th Multidisciplinary International Conference on Scheduling：Theory and Applications，MISTA09，Dublin，Ireland.2009：1012.

[16]A.Trautsamwieser，M.Gronalt，P.Hirsch，Securing home health care in times of natural disasters，OR Spectrum.2019，33（3）：787813.

[17]K.d.Rest，P.Hirsch，Daily scheduling of home health care services using time dependent public transport，Flex.Serv.Manuf.J.2016，28（3）：495525.

[18]S.V.Begur，D.M.Miller，J.R.Weaver，An integrated spatial DSS for scheduling and routing homehealthcare nurses，Interfaces.2018，27（4）：3548.

[19]A.Ikegami，A.Uno，Bounds for staff size in home help staff scheduling，J.Oper.Res.Soc.Japan.2007，50（4）：563575.

[20]劉瑞斌，袁斌，蒋子强.有午休需求的家庭护理人员路径问题的数学模型与精确算法.国际生产研究杂志，2017，55（2）：558575.

[21]H.Allaoua，S.Borne，L.Létocart，R.Wolfler Calvo，A matheuristic approach for solving a home health care problem，Electron.Notes Discrete Math.2013，41：471478.

[22]马跃如，文铮，易丹.考虑老年人满意度的多目标居家养老护理员路径优化[J].工业工程.2021，24（01）：7481.

[23]陈志，江治杰.带目标权重的物流路径优化研究—基于模拟退火蚁群算法[J].四川理工学院学报（自然科学版），2019，32（06）：6775.

[24]裴玉青.面向智慧医药的物流配送路径优化研究[D].南京邮电大学，2020.

[25]孙亮，王冰，郭栋，徐艺.求解不确定型车辆路径问题的弱鲁棒优化方法[J].国防科技大学学报，2020，42（03）：3038.

作者简介：谢云霞（1995— ），女，汉族，安徽六安人，硕士，学生，研究方向：物流工程居家护理行程和调度问题。