干扰管理在护工调度与路径规划的应用综述

黄锦昌

随着人口老龄化加深，居家养老医护资源紧缺，不确定性因素对居家养老服务质量的影响越来越明显。在對居家养老护工调度与路径规划问题的相关研究进行评述的基础上，着重讨论了干扰管理方法在该问题中的应用价值和研究情况，为后续研究提供文献基础。

随着我国老龄化程度的不断加深，积极应对人口老龄化已经上升为国家战略。国家发改委近期表示，预计“十四五”我国将进入中度老龄化阶段。可以预见的是，在未来几年，作为“以居家为基础、社区为依托、机构为补充、医养相结合”的养老服务体系的基础，居家养老服务需求将会持续稳步上升。本文提到的居家养老服务是指政府和社会力量依托社区，为居家的老年人提供生活照料、家政服务、康复护理和精神慰藉等方面服务的一种服务形式。

由于居家养老服务需要护理人员上门提供服务，但居家养老医护资源紧缺的现状仍没有得到很好的解决，居家养老服务机构存在着护工能力未被充分利用、客户服务要求不能被满足等问题。另外，在居家养老服务机构日常运营中，管理者通常为护理人员分配好了客户以及设计了对应的访问路线。但在实际执行中，可能会发生各种突发事件（如道路阻塞等），导致客户不能服务或延迟服务，使得原计划不可行。而干扰管理就是研究如何处理干扰，使得其对系统的副作用最小化。因此将干扰管理思想应用于居家养老护工调度与路径规划问题中，有利于在干扰发生时及时合理调整原计划，为居家养老服务机构提供科学的护工调度决策方案，使干扰带来的副作用最小化，提高服务的效率与满意度。

对居家养老护工调度与路径规划问题（Home Care Scheduling and Routing Problem，HCSRP）的研究早期以确定性情况为主，后来才逐渐增加考虑不确定的因素，因此本文虽然主要探讨干扰管理在HCSRP问题的应用，但仍将从确定性和非确定性两种情况进行讨论。

确定情况下的HCSRP研究现状

HCSRP问题是在中期（如一周）或短期（如一天）的计划期内考虑的，因此本小节将从这两个方面阐述。

Begur等（1997）关注每周5天的护士排班问题，并开发了一个基于一些简单启发式算法的空间决策支持系统来解决这个问题。Nickel等（2012）使用不同的元启发式算法（如自适应大邻域搜索和禁忌搜索）结合约束规划的方法来解决每周HCSRP问题，该问题将提供服务的护士人数最小化作为目标函数的一部分。An等（2012）研究了不同患者的就诊间隔可能出现不同的HCSRP，并提出了两阶段启发式方法求解问题。Bard等（2014）和Shao等（2012）设计了一个顺序贪婪随机自适应搜索程序（GRASP）、一个并行GRASP和一个分支定价集合分割算法来解决每周护理人员的路径和调度问题。Trautsamwieser等（2014）考虑额外的工作时间规定（如休息时间、每天的最大工作时间等），并将护士每日以及每周的休息时间转化为每周HCSRP问题，提出了一种分支定价切割求解方法，以便变邻域搜索（VNS）算法的解为上界精确求解问题。Cappanera等（2015）使用模式建模设备来联合协调分配、调度和路由决策。在他们的问题所考虑的计划范围内，最多可以为每个患者分配给定数量的操作员。该方法通过分析三种模式生成策略来生成模式集，利用商业优化软件求解由模式集构造的整数线性规划模型。Maya Duque等（2015）将每周HCSRP制定为一个双目标（即最大化服务水平和最小化旅行距离）数学程序，该程序基于集合分割公式，并设计了一个两阶段的解决方法来有效地解决问题。Liu等（2014）提出了一种可行和不可行局部搜索的禁忌搜索启发式算法，用于家庭健康护理问题中的周期性车辆路径问题。

上述论文研究中期计划周期中的HCSRP，而以下论文则考虑短期计划周期中的HCSRP。Bertels等（2006）应用禁忌搜索启发式算法、模拟退火启发式算法和约束规划，为护士找到一个可行的工作计划，该计划满足关于居家护理的各种硬约束和软约束以及各种偏好约束。他们考虑了病人对特定护士的偏好以及护士对特定病人的偏好。同时，他们为实际应用开发了优化软件PARPAP。Eveborn等（2006）提出了一种重复匹配算法，将约束和软目标纳入HCSRP，以求出护理人员的上门服务计划。他们定义了客户的偏好护工。此外，他们还开发了一个决策支持系统LAPS CARE来帮助调度人员。Akjiratikarl等（2007）设计了粒子群优化算法来解决日常HCSRP问题。Rasmussen等（2012）使用分支定价算法求解HCSRP，其中包含软偏好约束（即将护工就诊偏好的最大化作为目标函数的一部分）和服务开始时间之间的时间依赖性。此外，他们使用聚类技术来加速分支定价算法。Mankowska等（2014）提出了一种自适应变邻域搜索算法来解决考虑相互依赖服务和护工病人匹配性的HCSRP问题。Du等（2017）在考虑患者优先级和时间窗的情况下，提出了遗传算法求解HCSRP问题。Liu等（2017）构建了考虑午休需求和护工病人匹配性的HCSRP模型，并开发了一个分支定价算法来精确解决问题。

考虑不确定性因素的HCSRP研究现状

由于服务过程中的不确定因素会大大提高护工调度的难度和降低计划执行的可行性，对时效性要求较高的服务内容（如胰岛素注射等）影响极大。同时，护理资源越发紧缺，近年来越来越多的文献开始研究如何处理HCSRP问题中的不确定因素。Yuan等（2015）设计了一个针对随机服务时间和技能需求的HCSRP的分支定价算法。R.J.Kuo等（2016）研究在不断接收订单的情况下，考虑模糊服务时长、动态客户地点等因素，上门服务公司如何决定服务的顺序，以最大化服务客户的数量和最小化客户的等待时间的问题，并设计在蚁群算法（ACO）上改进的蚁群系统（ACS）算法求解问题。Cappanera P等（2017）首次将鲁棒框架应用于居家护理问题，其考虑了需求不确定（包括增加和取消）的情况，提出用非标准基数约束鲁棒方法建立模型。Shi Y等（2018）在HCSRP问题中首个同时考虑取送生物样本以及不确定旅行和服务时间，其以最小化总成本为目标函数，建立带资源约束的随机规划模型。Restrepo M I等（2019）首次提出集成人员配置和调度决策的优化方法，使用上下文无关文法建立长期调度时间表，以应对不确定需求。其提出两阶段随机规划模型：第一阶段决策对应于地理区域护理人员的配置和日程安排；第二阶段的决定涉及临时将护工重新分配到邻近地区，联系护工在休息日工作，以及允许需求不足和过度覆盖。Shi Y等（2019）考虑不确定旅行时间和服务时间，从鲁棒优化角度研究HCSRP问题，并分别设计模拟退火算法、可变邻域搜索算法、禁忌搜索算法求解问题。Du G等（2019）研究突发事件下的实时HHC护理人员调度问题，考虑时间窗约束、多个护理人员、多服务类型，以最小化所有医务人员的总周转时间和患者的总体满意度差值为目标，提出改进的模因算法求解问题。Demirbilek M等（2019）研究单计划周期新病人需求按指数分布随机到达的情况，以最大化计划周期内病人的服务次数为目标，提出基于场景的算法（SBA）求解问题。

目前在居家養老调度领域考虑不确定性的研究中，很少有文献使用干扰管理的方法。干扰管理是一种实时处理干扰或意外事件的方法，它已被广泛用于解决各种优化问题。Wang等（2012）提出了利用干扰恢复模型对带时间窗的VRP问题进行建模，并设计了一种嵌套划分方法进行求解。Kiefer等（2016）针对公共交通系统的严重故障，构建了一个混合整数规划模型，并用商业优化软件CPLEX进行了求解。Zhang等（2016）研究了泊位计划恢复问题，并使用基于词典优化的方法来解决该问题。Dollevoet等（2017）提出了一个迭代框架，用于重新安排与铁路干扰管理相关的时间表、机车车辆和乘务员。Marla等（2017）提出了综合飞机和乘客恢复的精确和近似模型，以及权衡延误和燃油消耗的飞行计划。Wu等（2017）采用整数规划迭代不动点的方法来获得可行的飞行路线，以重新分配飞机的飞行路线来应对一架飞机的停飞。Yuan B等（2017）对护工实时调度过程中出现的意外事件（包括客户新需求、客户服务取消、客户时间窗改变）进行了干扰管理，以最小化对病人、护工、护理企业的偏离为目标函数建立模型，并使用基于成本记录机制的禁忌搜索算法求解模型。

结 语

目前在居家养老调度领域的研究主要以国外发达国家为主，国内的研究近年才逐渐增多，主要因为国外现代养老服务市场发展较早，且更早更严重的社会老龄化问题都迫使其进行更多更深入的研究，这也为我国提供了宝贵的发展经验。针对HCSRP问题中的不确定因素，学者们提出了随机规划模型、鲁棒优化模型等解决方法，但这些方法要么不能实时处理突发事件，要么在处理突发事件的时候对原计划改动过大，相当于抛弃原来的计划又重新做了另外一个。干扰管理方法的应用可以有效避免以上问题，获得令人满意的计划，其对于HCSRP复杂的系统调整问题具有很强的适应性。

（华南理工大学）

参考文献：

[1]资元星. 区分任务紧急性的居家养老预约调度与路径规划问题研究[D].广州：华南理工大学， 2019.

[2]胡祥培， 丁秋雷， 张漪，等. 干扰管理研究评述[J]. 管理科学， 2007.

[3]Cappanera P ， Scutella M G， Nervi F， et al. Demand uncertainty in Robust Home Care Optimization[J]. Omega-international Journal of Management Science， 2017： 95-110.

[4]Restrepo M I， Rousseau L， Vallee J， et al. Home Healthcare Integrated Staffing and Scheduling[J]. Omega-international Journal of Management Science， 2019.

[5]Shi Y， Boudouh T， Grunder O. A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times[J]. Transportation Research Part E： Logistics and Transportation Review， 2019， 128： 52-95.