周期性家庭护理人员分配问题研究

陆雨薇，袁 彪

（1.广西科技大学 机械与交通工程学院，广西 柳州 545006；2.上汽集团人工智能实验室，上海 200038；3.赛可智能科技（上海）有限公司，上海 200038）

0 引言

家庭护理是指以医院、社区和社会护理企业为主体，由其指定护理人员上门为客户提供医疗、辅助医疗和生活照料等服务.与传统的住院医疗相比，家庭护理服务有如下几个优势[1-2]：1）顾客足不出户就能享受到个性化的医疗服务；2）减少住院等所需费用；3）提高医疗资源（如医院的病床等）利用率.目前家庭护理这一服务模式已经得到了大家的认可，且发展迅速.在此背景下，如何为家庭护理服务模式提供更科学的运作管理理论，使这一服务模式得到更好地推广与应用，值得我们考虑.

家庭护理中的人员计划与安排是决定服务质量的重要决策活动之一.客户通常需要若干周的服务，并指定一周内的服务次数以及允许服务日期，也称作服务模式（Service pattern）.对于新客户，需要确定为其服务的护理人员以及具体的护理计划.而这一决策过程目前是由有经验的护理人员提前一周靠手工完成，需消耗大量时间和精力.本文正是为解决这一问题而提出的，问题具体描述如下：给定一个计划期（通常一周），一个客户集合以及护理人员集合，需为客户指定护理人员，确定护理人员的服务模式以及每个护理人员每天的访问路径.这一问题类似于经典的周期性车辆路径问题（Periodic Vehicle Routing Problem，PVRP）[3].与PVRP相比，考虑如下约束：1）多类型护理人员约束，不同的客户需要不同类型的服务，如家庭保洁、注射和物理治疗等，这些服务需要不同医疗护理技能.管理者会按照服务所需技能难度以及护理人员所拥有技能，将客户和护理人员分类，构成层次化多类型护理人员结构，即最高层次护理人员能服务所有类型客户，而最低层次护理人员只能服务仅需简单技能类型的客户；2）护理连续性约束，对客户而言，应尽量避免他们接触不同的护理人员.在客户的角度，他们不用在每次服务时都和不同护理人员建立新关系，可减少陌生和不适感，而在护理人员的角度，他们对客户的身体状态十分熟悉，可提供更专业的服务.护理连续性约束可用客户在护理公司接受服务时访问他的不同护理人员数量小于或等于某一设定值表示；3）随机路途时间和服务时间，在实际服务过程中，路途时间与具体的交通状况相关，服务时间与客户的身体状态相关[4]，因此，需考虑随机的路途时间和服务时间.

本文所提出的问题包含护理人员分配以及路径优化两个子问题，可使用两阶段算法或集成式算法求解.本文选择两阶段算法对问题求解，原因如下：1）尽管集成式算法可以求得问题的近优或最优解，但它只能求解规模很小的问题，并且所得的解可能会因为取消或增加某一客户的服务而变得很差或不可行；2）家庭护理人员日调度中的一些约束很难在集成式算法中考虑，如服务优先次序约束[5].在所提出的两阶段算法中，使用启发式算法估计护理人员的路途时间（即路径优化子问题），设计基于禁忌搜索和整数规划的混合算法求解护理人员分配子问题.在求解护理人员分配子问题后，可以得到两类信息：一是每个客户由哪些护理人员服务；二是每个客户选择何种服务模式.以这两类信息作为输入构建护理人员日路径优化问题，采用已有的一些算法对此问题求解，即可得到护理人员每天的访问路径.

在现有研究中，一些学者也提出两阶段算法对周期性护理人员分配问题求解.Begur等[6]研究了护理人员周调度问题，将问题分解为一系列独立的日调度问题，然后使用简单的启发式算法求解，但并未考虑护理连续性约束.Borsani等[7]将问题表示为一个护理人员分配模型和调度模型，分配模型为新客户确定护理人员，调度模型以分配模型的解为输入，构建护理人员一周的访问计划，值得注意的是他们假设路途时间与访问顺序无关.Yalçindağ等[8]首先以均衡化护理人员负荷为目标，确定最好的护理人员分配方案，然后通过求解一个带服务模式的旅行商问题为每个护理人员确定一周的访问路径，同样值得注意的是第一阶段中护理人员工作负荷与访问顺序无关，后来，他们又提出了基于Kernel Regression的方法估计护理人员的路途时间[9].从以上文献可以看出，目前提出的两阶段算法假设护理人员路途时间与访问顺序无关，只能适用于客户分布在一个较小区域内的情况.

1 问题描述

1.1 数学模型

本文所研究的问题可概括为：在计划期H={1,…,h,…}内，为每个客户i∊N选择和确定满足技能要求的护理人员k∊K，K为护理人数最大数.每个护理人员k∊K拥有的技能或所属类别为sk(sk=1,…,m)，每天正常工作时间长度为D.每个客户i∊N有技能要求si和服务模式集合Pi.客户i的服务模式p∊Pi定义了计划期内的访问次数fi以及可访问日期bph，如果在服务模式p中第h天需服务，则bph=1，反之，则为0.客户i∊ N的服务时间tsi服从正态分布，即tsi～ N（μi，σi2）.客户i与j间的路途时间ttij也服从正态分布，即ttij～N（μij，σij2）.每个客户i∊N只能被技能等于或高于其技能需求的护理人员k∊K服务，即sk≥si.为满足护理连续性要求，访问同一客户的护理人员数量不能超过设定值Q，即在客户接受服务时，最多只有Q个护理人员-客户对，同时需保证以前周期确定的护理人员-客户对（i，k）∊PNK在本周计划时仍然满足.为了构造所提出的混合算法，建立基于集分割的数学模型，其中，Rhk表示护理人员k在第h天的路径集合，chkr表示路径r∊Rhk的总成本，ahkri表示客户i是否在路径r∊Rhk中，若在则为1，反之为0.决策变量定义如下：xhkr为0～1变量，表示最优解中是否选择路径r∊Rhk；yik为0～1变量，表示护理人员k是否服务客户i；zip为0～1变量，表示客户i是否选择服务模式p∊Pi.基于以上描述，定义的数学模型如下：

目标函数（1）最小化总成本.约束（2）保证每个护理人员选择一条路径，注意Rhk中可能包含空路径（即路径上不包含任何服务人员）；当从Rhk中选择空路径时，表示护理人员k在第h天不需工作.约束（3）和约束（4）表示护理人员在周期内按照服务模式访问客户.约束（5）和约束（6）满足客户的护理连续性约束.约束（7）确保满足以前周期所确定的护理人员与客户关系.约束（8）预先将部分yik因为技能约束设定为0.约束（9）—约束（11）定义决策变量为0～1变量.

1.2 路径总成本计算

路径r总成本包含3个部分：路途成本T（r）、服务成本S（r）以及加班惩罚成本O（r）.以类型为l的护理人员路径r={n0=0，n1，n2，…，ni，…，nr，nr+1=0}为例，ni表示路径r上的第i个客户，nr表示路径r访问客户的数量，Ct表示单位时间路途成本，Csl表示类型为l的护理人员的单位时间服务成本，pc表示加班惩罚系数.由于客户间的路途时间以及客户的服务时间服从正态分布并且相互独立，护理人员访问路径r的总时间Tr仍然满足正态分布，即，按期望值的定义，3种期望成本计算公式如下：

从式（12）—式（14）可看出，对包含相同客户的路径而言，路径总成本只与期望路途时间相关，因此，计算一条路径的总成本，只需确定该路径的期望路途时间即可，而这一问题是一个旅行商问题，故采用最远插入法来求得期望路途时间，这部分将会在数值实验中讨论.

2 混合算法

针对所研究的问题，设计以禁忌搜索和整数规划为基础的混合算法.

2.1 算法描述

本文所提出混合算法的主要思想为：收集和存储禁忌搜索算法在迭代过程中产生的中间解或局部最优解，使用它们构建整数规划模型（1）—模型（11），利用优化软件求解模型，一方面可以得到禁忌搜索算法在迭代过程中可能遗漏的较好解，另一方面，可以评价禁忌搜索算法最近搜索的效果，如果若干次迭代后，禁忌搜索算法或整数规划模型无法得到更好的解，则说明要引入新解作为搜索的起点.设nTS表示禁忌搜索算法连续nTS×1 000次迭代未改善当前最好解，nIP表示Cplex连续nIP次未能改善当前最好解，n1和n2是算法的基本参数.混合算法步骤如下：

Step 1构建初始解s0，并令当前解s=s0；

Step 2以当前解s为起点，使用禁忌搜索算法进行搜索，并按照护理人员k和日期h将每次迭代中邻域的最好解分解，保存在Rhk中；

Step 3判断禁忌搜索算法当前1 000次迭代与前1 000次迭代中得到的最好可行解是否变小，如果变小，则说明目前的搜索是有效的，令nTS=0，继续当前搜索；反之，令nTS=nTS+1；

Step 4当nTS≥n1时，构建整数规划模型，并使用Cplex求解模型；

Step 5判断Cplex得到的解与当前最好可行解的大小，如果Cplex的解小于当前最好解，则令nIP=0，将Cplex得到的解作为当前解和最好解，继续搜索；反之，令nIP=nIP+1；

Step 6当nIP≥n2时，使用扰动机制对当前最好可行解扰动，扰动后的解作为当前解进行搜索；

Step 7判断计算时间是否超过设定值，若超过，则算法停止；反之，则继续搜索.

2.2 禁忌搜索算法

禁忌搜索算法（Tabu Search，TS）由Glover于1986年提出，算法主要思想为：首先产生一个初始解s0作为当前解s，然后在当前解的邻域NH（s）中使用移动评价函数g（s）选择最好解作为新的当前解.同时，使用禁忌表记录已搜索解的历史信息以避免陷入循环和局部最优.目前，禁忌搜索算法已广泛应用于求解优化问题，如定位——路径优化[10]和车辆路径优化[11]等.

本文使用的禁忌搜索算法与Cordeau等[12]在求解周期性车辆路径问题时提出的相似，但有如下几点区别：1）设置约束惩罚系数α在某一区间，避免搜索过程中深陷到不可行区域，而Cordeau等则没有这一设置；2）使用最远插入法评价路途时间，而Cordeau等使用GENI（GENeralized Insertion）完成客户的删除、插入以及路途时间计算.本文主要介绍禁忌搜索算法中的重要组成部分：初始解构造、禁忌表、特赦准则、邻域结构以及移动评价函数.

2.2.1 初始解构造

由于在禁忌搜索算法中我们只松弛了护理连续性约束，故构造初始解时需满足多类型护理人员约束，步骤如下：

Step 1按客户位置与护理中心所成角度的升序排列客户；

Step 2为每个客户i随机选择一种服务模式p∊Pi；

Step 3重复Step 4—Step 6，确定第h（h=1，2，…，|H|）天的访问安排；

Step 4重复Step 5和Step 6，确定类型为l（l=m，m-1，…，1）的护理人员的访问安排；

Step 5选择距离护理中心最近的类型为l的客户i∊Nl={j|sj=l，j∊N}；

Step 6按照Step 1中确定的客户顺序，将类型为l的客户i∊Nl分配给能服务他的护理人员，使目标函数值增加最小.

2.2.2 禁忌表和特赦准则

禁忌表的目的是为了避免重复搜索并引导算法搜索解空间的其他区域，这是区别于其他局部搜索算法的重要特征之一.禁忌表中保存了已搜索过解的信息.本文定义每个解s对应一个属性集B（s）={（i，k，h）：客户i在第h天由护理人员k服务}，这些属性（即禁忌对象）被保存在禁忌表中.因此，禁忌表可以使用一个|N|×|K|×|H|的三维数组表示.解s的邻居s'∊ NH（s）通过邻域结构删除和添加B（s）中的部分属性后得到.当从护理人员k在第h天的访问客户列表中删除客户i时，属性（i，k，h）被标记为禁忌状态，令禁忌长度为θ，表示在后面θ次迭代中不能在第h天将客户i重新分配给护理人员k.当包含某一禁忌属性的可行解优于当前最优解时，可使用特赦准则对这一属性解禁.特赦准则是基于每个属性的特赦水平（Aspiration level），特赦水平定义为搜索过程中包含这一属性的最好可行解的目标函数值.

2.2.3 邻域结构

禁忌搜索算法通过邻域结构产生新解，采用的邻域结构如下：1）在第h天，从护理人员k的客户列表中删除客户i，并重新将客户i分配给同一天能够服务他的护理人员k'（k'≠k）；2）在第h天，如果护理人员k和k'（k'≠k）都能服务客户i和j（j≠i），交换服务客户i的护理人员k和服务客户j的护理人员k'；3）从客户i的服务模式集合Pi中重新选择一种新服务模式p'代替当前解中的服务模式p，如果第h天在服务模式p中却不在服务模式p'中（即bph=1和bp'h=0），则将客户i从这一天删除，如果第h天不在服务模式p中却在服务模式p'中（即bph=0和bp'h=1），则将客户i分配给能服务他的护理人员使目标函数值增加最小.以上各邻域的大小分别为 O（|N||H|）、O（|N|2|H|）和.

2.2.4 移动评价函数

移动评价函数是为选取邻域中的解而设计的一个评价公式，与遗传算法中的适应度函数相似.本文使用的移动评价函数g（s'）包含3个部分：目标函数值c（s'）、护理连续性约束违反惩罚值q（s'）和多样性函数值d（s'），即g（s'）=c（s'）+αq（s'）+d（s'）.c（s'）定义为目标函数值，包括路途成本、服务成本以及加班惩罚成本.q（s'）定义为护理连续性约束违反惩罚值，具体计算如下：对客户i，如果解中分配给i的护理人员数量（包含以前周期确定的）小于或等于Q时，表示客户i的护理连续性满足，无需惩罚；如果分配给i的护理人员数量（包含以前周期确定的）大于Q，若以前确定的护理人员数量已等于Q，计算解中实际分配的护理人员（不包含以前周期确定的）访问客户i的总次数，并以此作为惩罚，若以前确定的护理人员数量小于Q，从解中选择访问i次数最多的护理人员作为虚拟的以前确定的护理人员，直到这一数量等于Q时，计算解中分配的其他护理人员访问客户i的总次数，并以此作为惩罚.d（s'）定义为多样性函数值，只有当邻域中的解s'的目标函数值c（s'）与护理连续性约束违反惩罚值q（s'）之和大于当前解s时才使用，与c（s）、ρikh和的乘积相关，计算公式如下：其中，ρikh表示搜索过程中属性（i，k，h）∊B（s'）B（s）被添加到解中的次数，λ表示当前的迭代次数，γ表示多样性系数.

2.3 扰动机制

当整数规划模型无法得到更好解时，说明当前搜索已陷入局部最优，因此，使用扰动机制[13]对当前最优解扰动，以产生多样性的解.具体过程如下：首先随机选择一个客户i以及离客户i最近的w个客户，w为之间的随机整数；然后将这w+1个客户从当前最优解中的分配关系删除，重新为他们分配新的服务模式；最后，按照随机的顺序为他们分配新的护理人员使目标函数值增加最小.

3 数值实验

首先介绍期望路途时间估计算法，然后描述算例的生成过程，接着验证所提出算法的有效性，最后比较和分析多类型护理人员与护理连续性约束对总成本的影响.本文所提出的算法使用C++编程，整数规划模型采用IBM ILOG Cplex 12.5求解，在Intel E5-2670 2.6 GHz CPU和10 GB内存的电脑上测试，操作系统为Linux.

3.1 期望路途时间估计算法

为选择合适的期望路途时间估计算法，比较了最远插入法[14]、不同邻居个数np值下的GENI和GENIUS（Unstring and String）[15].在[0，100]2的平面上，出发点为（50，50），生成服从均匀分布的100个点，从中分别选择5、8和10个点作为要访问的客户，随机生成1 000个实例，使用以上算法构建从出发点开始，访问指定客户点后，返回出发点的路径并计算路途时间，np值设置在2～6.实例最优解使用Cplex求解.表1列出了3种算法1 000个实例的平均路途时间和总计算时间、3种算法得到的最好解与最优解之间的Gap（G-Gap、GU-Gap和FI-Gap）.

表1 不同启发式算法求解1 000个实例的结果Tab.1 Result summary of 1 000 cases under different heuristics

表1 （续）Tab.1 （Continued）

表1表明：G-Gap、GU-Gap和FI-Gap分别小于0.43%、等于0和小于0.84%，GENIUS和np等于6时，GENI所得的解优于最远插入法.但要取得如此好的解，需要比最远插入法消耗更多的时间，这将会大大增加混合算法的计算时间.而最远插入法的Gap相对较小，是可以接受的，因此，综合解的质量和计算时间，选择最远插入法作为最终的路途时间估计算法.

3.2 算例生成方法

为了测试算法的性能，生成包含100和200个客户的算例各5个.具体过程如下：在二维平面[0，100]2随机产生|N|个点，护理中心的坐标为（50，50）.令两点间的路途时间均值μij等于其欧几里德距离，标准差σij=0.25μij，单位时间路途成本ct为1.0.客户和护理人员分为3类，类型为1、2和3的客户比例分别为50%、30%和20%，对应的护理人员数量与客户总数量的比值分别为4%、2%和2%，单位时间服务成本cs1、cs2和cs3分别为0.6、0.8和1.0.客户服务时间的均值μi从均匀分布[15，30]中随机产生，标准差σi=0.25μi.护理人员正常工作时间长度D为300，加班惩罚系数pc为5.0.一个计划周期包含5天，客户服务模式分为4类，包含访问次数、组合数、可能组合以及每种模式所占百分比，如表2所示，“可能组合”中的值表示了客户允许服务的日期，以服务模式3中的“21”为例，将它转化为二进制数“10101”，表示客户只在周一、周三和周五接受服务.对于护理连续性约束以及以前确定的护理人员-客户对，设Q=2，40%的客户已经分配了2个护理人员，20%的客户已分配了1个护理人员.

表2 4种服务模式介绍Tab.2 Introduction of four service mode

3.3 算例结果

通过一系列测试，本文所提出混合算法的参数取值如下：禁忌搜索算法中的禁忌长度θ为[7.5lg|N|]，多样性系数γ为0.015，护理连续性约束惩罚系数α的初始值、最小值和最大值分别为200、0.000 1和1 000，惩罚系数α的更新系数为0.5，混合算法中Cplex每次最长求解时间为1 000 s，n1和n2均等于2，预定计算时间为0.2|N|min.

为了验证所提出混合策略的有效性，比较使用和未使用这一策略的禁忌搜索算法，分别用TSIP和TS表示，两种算法的计算结果见表3.表3中列出了TS得到目标函数的最小值和平均值，TSIP得到目标函数的最小值和平均值，两种方法最小值之间的相对偏差（Gap%），构成最大整数规划模型的平均列数以及搜索过程中多次求解整数规划模型总时间的平均值（IP CPU）.

表3 计算结果比较Tab.3 Results comparison

表3所示结果表明，对所有实例而言，TSIP得到目标函数的最小值都要比TS小，两者之间Gap的均值为1.24%，最大的Gap为2.51%（R203）；同时，TSIP计算目标函数的平均值也优于TS.综合以上结果可以看出，所提出的混合策略确实改善了禁忌搜索算法的性能.在整数规划模型方面，构成最大整数规划模型（即搜索过程中最后一次构成的整数规划模型）的平均列数为17 991.33，搜索过程中所有整数规划模型的平均求解时间为245.03 s（约4.08 min），相对于算法的总计算时间（20 min和40 min），这一求解时间还是比较合理的，即在合理的时间内整数规划模型能为禁忌搜索算法提供新解或评估搜索效果.

3.4 成本比较与分析

本文所研究的问题主要考虑了多类型护理人员和护理连续性两个约束，前者是为了合理地利用人力资源及节约运营成本，而后者是为了提高服务质量以及客户满意度.以R201为例，分别对原问题中的这两个约束松弛，讨论它们对服务成本、路途成本、加班惩罚成本以及总成本的影响.仍然使用本文所提出的算法对松弛约束后的两个问题求解，选择10次计算中最好的解比较，具体成本见图1.

图1 不同约束间的成本比较Fig.1 Cost comparison under different constraints

从图1中可以看出，只使用一种类型护理人员时，服务成本增加了32.50%，路途成本和加班惩罚成本分别下降了0.91%和34.56%，总成本增加了12.73%.服务成本增加的原因在于：使用一种类型护理人员时只能使用最高层次护理人员，而最高层次护理人员的单位时间服务成本cs3是最大的（为1.0）.路途成本和加班惩罚成本减小是因为：最高层次护理人员可以服务任何类型的客户，因此，护理人员可以按最优路径（忽略类型）服务客户，而不用因为技能不足只能服务更远的客户.从总成本来看，虽然单一类型护理人员减小了路途成本和加班惩罚成本，却大大提高了服务成本，从而增加了总成本，故使用多类型护理人员确实能够减少公司总运营成本.

从图1中也可看出，无护理连续性约束时，服务成本增加了1.43%，路途成本和加班惩罚成本分别下降了11.05%和15.35%，总成本减小了5.76%.服务成本增加可能是因为：某些高层次护理人员在他们的服务路径上访问了一些低层次的客户，而这些低层次客户如果被对应层次的护理人员服务，虽然服务成本有所下降，但路途成本会增加更多，因此，应用这些高层次护理人员可使总成本增加最小.而路途成本和加班惩罚成本下降的原因在于：松弛护理连续性约束后，护理人员可以选择服务的客户集变大，即客户不再因为已分配的不同护理人员数量达到设定值而拒绝某一护理人员服务.从总成本来看，松弛护理连续性约束的确减少了总成本，但成本减少是以降低客户服务质量以及满意度为代价的，故公司管理者在决策时需考虑总成本和客户满意度间的平衡.

4 结束语

研究了考虑多类型护理人员、护理连续性和随机时间约束的周期性护理人员分配问题，针对问题的分配和路径优化部分，分别采用基于禁忌搜索和整数规划的混合算法以及最远插入算法进行求解.取得了如下成果：1）在周期性家庭护理人员分配问题中首次同时考虑了多类型护理人员、护理连续性和随机时间3个约束；2）将问题分解为一个分配子问题和若干个路径优化子问题，分别使用基于禁忌搜索和整数规划的混合算法以及最远插入算法求解；3）定量地比较和分析多类型护理人员以及护理连续性约束对总运营成本的影响，为管理者提供了明确的决策依据.

以本文研究的问题为基础，以后的研究可从以下两个方面展开：1）以本问题的解为输入构建每天的护理人员调度与路径优化问题，并设计相应的优化算法；2）寻找更有效的路途时间估计算法；3）设计更多的元启发式算法求解所提出的问题，如蚁群算法[16]、遗传算法[17]或粒子群算法[18]等.