一种基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法

摘要

本发明公开了一种基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法，具体为先在调度周期起始时刻之前采集待指派的护士信息及顾客的订单信息；在调度周期起始时刻，根据护士与顾客之间的位置信息计算旅行距离矩阵，并根据历史数据估计出旅行时间的分布参数，随后确定建立模型所需要的参数；考虑旅行时间为随机变量的情况下，以最小化公司的运营成本为上层目标函数，以最大化顾客满意水平为下层目标函数，建立随机双层家庭医疗护理路径规划与调度优化模型；针对该模型，设计三阶段混合启发式算法进行求解，进而得到一个随机环境下的家庭医疗护理订单分配决策的方案。本发明从随机优化的角度来考虑分层决策下的家庭医疗护理服务调度问题。

说明书

技术领域

本发明涉及智能信息管理技术领域，具体涉及一种基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法。

背景技术

21世纪以来，我国的老龄化程度呈现加速态势，持续的老龄化趋势给国家的养老系统带来很大压力，政府急需在医疗资源配置方面探索新的模式以应对人口老龄化带来的挑战。家庭医疗护理服务是西方国家的一种养老服务的新模式，它是以医院、社区疗养院和提供养老服务的社会企业为主体，由这些机构指定护士上门提供多种多样的护理服务来帮助病人恢复健康。在国外，家庭医疗护理的服务行业已经发展了很多年，居家护理的观念已经能被大多数人接受。在国内，这种居家养老的服务模式还处于发展的初步探索阶段，但是可以预见的是，随着中国当前人口老龄化问题不断严峻，未来的家庭医疗护理具有很大的发展空间以及市场。

在实际运作中，家庭医疗护理服务调度是一个分层决策的过程，首先由公司将平台顾客订单指派给护士，再由护士决定访问顾客的顺序和到达每个顾客的时间。在服务期间，护士的收入主要来自顾客支付的基本护理工资以及其服务质量的奖金，公司需要承担护士在执行工作期间产生的交通成本以及加班成本。在上门护理的过程中，护士到各个顾客处的旅行时间是家庭医疗护理公司在决策时需要参考的一个重要参数。在现实的环境中，护士的旅行时间经常是不准时的。因为天气状况、交通状况、护士的驾驶技能等外部因素会使旅行时间呈现一定的不确定性，继而影响到护士的服务开始时间。

尽管家庭医疗护理调度问题在国外的文献成果比较丰富，但是该领域所有的文献都没有考虑为考虑随机旅行时间的家庭医疗护理的路径规划与调度的分层决策问题提供优化方案。由于我国的老龄人口基数大，对于医疗服务的需求将会在未来呈爆发性的增长，随之会有越来越多的企业提供家庭医疗护理服务；另一方面，旅行时间的估计又经常受到各种因素的干扰，无法进行正确的估计，用随机变量来表示旅行时间是一种更贴近现实问题的方法。因此，如何解决随机环境下的家庭医疗护理调度问题具有实际意义。

本发明方法从随机优化的角度来考虑家庭医疗护理服务的调度问题，解决了随机环境下的家庭医疗护理公司的订单分配决策问题，求解得到的调度方案同时考虑了家庭医疗护理公司和护士的分层决策行为，降低公司运营成本的同时，也保证了较好的顾客服务满意水平。

发明内容

针对现存在的问题，本发明提供一种基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法，考虑旅行时间为随机变量的情况下，以公司的运营成本最小为上层目标函数，以顾客满意水平最大为下层目标函数，建立随机双层家庭医疗护理路径规划与调度模型，并对模型用三阶段混合启发式进行求解，得到一个同时考虑公司运营成本与顾客满意水平的均衡调度方案。

为了实现本发明的发目的，本发明采用如下技术方案：

一种基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法，包括如下步骤：

S1、在调度周期起始时刻之前，采集待指派的护士信息及顾客的订单信息；

所述待指派的护士信息包括待指派的护士的数量、护士的技能水平、家庭住址位置经纬度和可提供服务的时间窗；

所述顾客的订单信息包括待服务的顾客的数量、护理服务要求的护理水平、家庭住址位置经纬度和要求服务的时间窗；

S2、在调度周期起始时刻，根据护士与顾客之间的位置信息计算旅行距离矩阵，并根据历史数据估计出旅行时间的分布参数，随后确定建立模型所需要的参数；

所述参数包括护士服务顾客所需要的时间、护士的正常工作时间、每单位加班成本、单位旅行距离所需费用、服务满意水平度量间隔；

S3、考虑旅行时间为随机变量的情况下，以最小化公司的运营成本为上层目标函数，以最大化顾客满意水平为下层目标函数，建立随机双层家庭医疗护理路径规划与调度优化模型；

S4、针对随机双层家庭医疗护理路径规划与调度优化模型，设计三阶段混合启发式算法进行求解，进而得到一个随机环境下的家庭医疗护理订单分配决策的方案；

其中，三阶段混合启发式算法由迭代邻域搜索主框架、集划分求解过程以及后优化算法三部分组成；

在第一阶段，生成初始解，并采用大邻域搜索算法结合路径内部寻优算法进行邻域搜索，迭代邻域搜索主框架在迭代时不断地往路径池中填充每代的邻域最优解；

在第二阶段，使用第一阶段生成的路径集合来建立集划分模型，之后循环地求解集划分模型，直到得到的解方案对于下层的路径规划与时间调度模型来说是最优的，该过程停止；

在第三阶段，在求得随机双层家庭医疗护理路径规划与调度优化模型的解之后，设计确定最优出发时间的后优化算法来实现对服务满意水平的预测。

作为优选方案，所述步骤S3中，随机双层家庭医疗护理路径规划与调度优化模型，包括：

(一)模型中已知变量符号以及决策变量；

C表示顾客集合，N表示护士集合，L表示技能水平集合；q

(二)模型中需要模型约束条件如下：

(1)上层公司模型的指派约束如下：

三项约束确保护士的出发时间不超过护士梯形上线的临界点，每个顾客都能被服务，并且保证指派给护士的订单都是护士有资格去服务的；

(2)护士的执行服务的路径顺序约束如下：

这两项约束确保每个护士从家出发与返回最多一次；

该项约束确保每个顾客点由同一个护士进出访问最多一次；

(3)护士到达顾客处的服务开始时间的约束如下：

(4)护士工作开始时间的约束如下：

这两项约束的作用是确保护士的出发时间和返回时间都在其工作时间范围内；

(5)护士的加班时间计算的约束如下：

(6)计算护士到达顾客时刻获得的顾客满意分数的公式如下：

(三)目标函数建模过程如下：

对于分层决策的情形下的随机家庭医疗护理路径规划与调度问题，模型的优化目标分为上、下两个层次：

(1)上层目标是最小化公司的运营成本，其包含路径成本与期望加班成本，目标函数表达式如下：

(2)下层目标是最大化所有顾客的服务满意水平：

在该式中优化目标为最优化整体服务满意水平；

(四)模型的随机变量的期望计算

问题模型假设单位旅行时间服从伽马分布，则在两个顾客之间的旅行时间也服从伽马分布，有

其中，

(1)加班成本期望的计算

定义变量

其中，

因此，结合两种情况E[O

(2)服务满意评分的计算

将该顾客的梯形窗口的临界点的时间都根据累计服务时间以及出发时间向左平移，平移后的新临界点为

1)当

根据该表达式，p

2)当

则p

3)当

p

4)当

p

5)当

作为优选方案，所述步骤S4中，所述的求解随机双层模型的三阶段混合元启发式算法的过程，包括：

(一)初始解生成；

用临时需求库表示等待插入的临时顾客集合，其初始包含所有的顾客；对于每位护士都有一条空的路径被初始化，接着对每条路径随机从临时需求库中随机抽取一位顾客进行插入；插入准则是插入顾客时需要考虑的目标，这里采取两级的分层目标，第一级是最小化插入顾客后增加的路径成本和期望加班成本，第二级是最大化插入后增加的服务满意水平；插入顾客时采用两种插入策略，第一种是顺序插入策略，在该种策略中，顾客的插入顺序地考虑每条路径；第二种策略是平行插入策略，使用该策略插入一个顾客时，所有的路径被同时地比较；当临时需求库为空时或者在临时需求库中的顾客不能被插入到当前任何路径时，插入过程终止；

(二)邻域搜索；

迭代邻域搜索框架中的解搜索阶段采用大邻域搜索算法，包括：

(1)对解进行破坏移除操作，移除后的顾客加入到临时需求库中；移除算子包含随机移除、路径移除、最大旅行成本移除、最大加班成本移除以及相似顾客移除；随机移除算子随机地选择q个顾客从当前解中移除，而路径移除算子是随机从当前解中移除一条路径并直到移除的顾客数量超过q；最大旅行成本和最大加班成本移除算子分别选择当前解中带有最大旅行成本节省和加班成本节省的顾客进行移除；相似顾客移除算子移除在当前解中移除相似的顾客，具体操作是首先移除随机选择的顾客i，然后选择与顾客i最相似的顾客j进行移除；该过程重复地执行直到移除顾客的数量达到q；为了评估两个顾客之间的相似性，定义R(i,j)作为两个顾客之间相似性变量，该变量包含旅行时间、偏好服务开始时间以及要求的技能水平相似性的加权和，其表达式如下：

其中，t′

(2)对解进行插入重建操作，插入的顾客来自临时需求库中；算法使用的插入算子包含三种，分别是贪婪插入、随机贪婪插入和regret-2插入，对于前两种算子，评估一个插入位置的插入准则与初始解构造时的准则相同，贪婪插入算子采用平行插入策略来贪婪地插入顾客，而随机贪婪算子随机地选择顾客贪婪地插入；对于regret-2插入算子来说，该操作考虑了插入后的遗憾值，即运营成本和服务满意分数；

(3)对邻域解采用路径内部寻优算法；算法得到的邻域最优解可能包含着对于下层来说是非最优的路径，因而这样的最优解对于双层问题来说是不可行的；由于随机双层家庭医疗护理模型中的时间窗为软约束，所以该模型的解空间远远超过之前的确定模型，这导致大量的不可行路径会被加入路径池；为了提前对不可行的路径进行排除，因而新增了路径内部寻优算法来解决该问题；令r

(三)解的接受；

大邻域算法得到的邻域解首先根据其在临时需求库中剩余等待插入顾客的数量进行评估，如果在临时顾客库中顾客的数量少于在大邻域算法过程执行之前临时顾客库的数量，那么将进一步计算该解的上层目标函数值，并将该解添加至路径池，否则对于该解的评估过程不被执行；计算完该解后需要继续根据上层目标值决定该解是否代替该次搜索的起点；

(四)解的扰动；

该操作多次地执行顾客的随机移除顾客和插入顾客的操作进行扰动，使得每次大邻域算法开始的起点都不同；

(五)建立集划分模型；

当路径池中获得了求解问题的所有可行路径后，算法使用这些路径建立集合划分模型；

(六)求解集划分模型；

循环地求解集划分模型，对于每一次得到的最小运营成本解，如果存在对于下层问题为不可行的路径，则需要在路径池中对其进行移除，之后使用新的路径池更新集划分模型，继续循环求解，直到当前得到的新解中的每条路径都满足下层问题的最优条件，则该解为双层问题的优解；

(七)对双层解使用后优化算法；

在求得随机双层规划模型的解之后，设计确定最优出发时间的后优化方法来实现对服务满意水平的预测；该方法具体是对解中每条路径的可能开始的出发时间都计算该路径期望服务满意评分的和，最后选择最大的服务满意评分的出发时间作为护士的出发时间。

本发明与现有技术相比，具体如下技术效果：

本发明方法从随机优化的角度来考虑分层决策下的家庭医疗护理服务调度问题，求解得到的调度方案同时考虑了家庭医疗护理公司和护士的决策行为，降低了公司的运营成本同时保证了较好的顾客满意度，同时对现实中的其他基于分层决策的相关物流配送问题也具有很好的指导意义。

附图说明

图1为本发明实施例的基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法的步骤S4的三阶段混合元启发式的流程图；

图2为本发明实施例的求解集划分模型的迭代过程的流程图。

具体实施方式

下面结合附图对本发明的具体实施方式做详细说明。

本发明实施例的基于三阶段混合启发式算法的家庭医疗护理调度随机优化方法，包括如下步骤：

S1、在调度周期起始时刻之前采集待指派的护士信息及顾客的订单信息；

需要采集待指派的护士信息包括待指派的护士的数量、护士的技能水平、家庭住址位置经纬度和可提供服务的时间窗；

需要采集的顾客的订单信息包括待服务的顾客的数量、护理服务要求的护理水平、家庭住址位置经纬度和要求服务的时间窗。

S2、在调度周期起始时刻，根据护士与顾客之间的位置信息计算旅行距离矩阵，并根据历史数据估计出旅行时间的分布参数，随后确定建立模型所需要的参数；

其中，参数包括护士服务顾客所需要的时间、护士的正常工作时间、每单位加班成本、单位旅行距离所需费用、服务满意水平度量间隔。

S3、考虑旅行时间为随机变量的情况下，以最小化公司的运营成本为上层目标函数，以最大化顾客满意水平为下层目标函数，建立随机双层家庭医疗护理路径规划与调度优化模型；

S4、针对该模型，设计三阶段混合启发式算法进行求解，进而得到一个随机环境下的家庭医疗护理订单分配决策的方案。

其中，三阶段混合启发式算法由迭代邻域搜索主框架、集划分求解过程以及后优化算法三部分组成；

在第一阶段，生成初始解，并采用大邻域搜索算法结合路径内部寻优算法进行邻域搜索，迭代邻域搜索主框架在迭代时不断地往路径池中填充每代的邻域最优解；

在第二阶段，使用第一阶段生成的路径集合来建立集划分模型，之后循环地求解该集划分模型，直到得到的解方案对于下层的路径规划与时间调度模型来说是最优的，该过程停止；

在第三阶段，在求得随机双层规划模型的解之后，设计了确定最优出发时间的后优化算法来实现对服务满意水平的预测；

具体地，步骤S3中，双层家庭医疗护理路径规划与调度优化模型进一步如下：

S3-1、模型中已知变量符号以及决策变量说明如下：

C表示顾客集合，N表示护士集合，L表示技能水平集合；q

S3-2、模型中需要模型约束条件如下：

(1)上层公司模型的指派约束如下：

三个项约束确保护士的出发时间不超过护士梯形上线的临界点，每个顾客都能被服务，并且保证指派给护士的订单都是护士有资格去服务的；

(2)护士的执行服务的路径顺序约束如下：

这两项约束确保每个护士从家出发与返回最多一次；

该项约束确保每个顾客点由同一个护士进出访问最多一次；

(3)护士到达顾客处的服务开始时间的约束如下：

(4)护士工作开始时间的约束如下：

这两项约束的作用是确保护士的出发时间和返回时间都在其工作时间范围内；

(5)护士的加班时间计算的约束如下：

(6)计算护士到达顾客时刻获得的顾客满意分数的公式如下：

S34、目标函数建模过程如下：

对于分层决策的情形下的随机家庭医疗护理路径规划与调度问题，模型的优化目标分为上、下两个层次：

(1)上层目标是最小化公司的运营成本，其包含路径成本与期望加班成本，目标函数表达式如下：

(2)下层目标是最大化所有顾客的服务满意水平：

在该式中优化目标为最优化整体服务满意水平；

S3-4、模型的随机变量的期望计算

问题模型假设单位旅行时间服从伽马分布，则在两个顾客之间的旅行时间也服从伽马分布，有

其中，

(1)加班成本期望的计算

定义变量

其中，

(2)服务满意评分的计算

将该顾客的梯形窗口的临界点的时间都根据累计服务时间以及出发时间向左平移，平移后的新临界点为

1)当

根据该表达式，p

2)当

则p

3)当

p

4)当

p

5)当

具体地，如图1和2所示，步骤S4中，求解模型的三阶段混合启发式算法的进

一步过程如下：

S4-1、初始解生成；用临时需求库表示等待插入的临时顾客集合，其初始包含所有的顾客。对于每位护士都有一条空的路径被初始化，接着对每条路径随机从临时需求库中随机抽取一位顾客进行插入。插入准则是插入顾客时需要考虑的目标，这里采取两级的分层目标，第一级是最小化插入顾客后增加的路径成本和期望加班成本，第二级是最大化插入后增加的服务满意水平；插入时服务满意分数计算表达式如下：

其中，n

插入顾客时采用两种插入策略，第一种是顺序插入策略，在该种策略中，顾客的插入顺序地考虑每条路径；第二种策略是平行插入策略，使用该策略插入一个顾客时，所有的路径被同时地比较。当临时需求库为空时或者在临时需求库中的顾客不能被插入到当前任何路径时，插入过程终止；

S4-2、邻域搜索；迭代邻域搜索框架中的解搜索阶段采用大邻域搜索算法，该算法该步骤进一步包括：

S4-2-1、对解进行破坏移除操作，移除后的顾客加入到临时需求库中；移除算子包含随机移除、路径移除、最大旅行成本移除、最大加班成本移除以及相似顾客移除；随机移除算子随机地选择q个顾客从当前解中移除，而路径移除算子是随机从当前解中移除一条路径并直到移除的顾客数量超过q；最大旅行成本和最大加班成本移除算子分别选择当前解中带有最大旅行成本节省和加班成本节省的顾客进行移除；相似顾客移除算子移除在当前解中移除相似的顾客，具体操作是首先移除随机选择的顾客i，然后选择与顾客i最相似的顾客j进行移除；该过程重复地执行直到移除顾客的数量达到q；为了评估两个顾客之间的相似性，定义R(i,j)作为两个顾客之间相似性变量，该变量包含旅行时间、偏好服务开始时间以及要求的技能水平相似性的加权和，其表达式如下：

其中，t

S4-2-2、对解进行插入重建操作，插入的顾客来自临时需求库中；算法使用的插入算子包含三种，分别是贪婪插入、随机贪婪插入和regret-2插入，对于前两种算子，评估一个插入位置的插入准则与初始解构造时的准则相同，贪婪插入算子采用平行插入策略来贪婪地插入顾客，而随机贪婪算子随机地选择顾客贪婪地插入；对于regret-2插入算子来说，该操作考虑了插入后的遗憾值，即运营成本和服务满意分数；

S4-2-3、对邻域解采用路径内部寻优算法；算法得到的邻域最优解可能包含着对于下层来说是非最优的路径，因而这样的最优解对于双层问题来说是不可行的。由于随机双层家庭医疗护理模型中的时间窗为软约束，所以该模型的解空间远远超过之前的确定模型，这导致大量的不可行路径会被加入路径池。为了提前对不可行的路径进行排除，因而新增了路径内部寻优算法来解决该问题。令r

S4-3、解的接受；

大邻域算法得到的邻域解首先根据其在临时需求库中剩余等待插入顾客的数量进行评估，如果在临时顾客库中顾客的数量少于在大邻域算法过程执行之前临时顾客库的数量，那么将进一步计算该解的上层目标函数值，并将该解添加至路径池，否则对于该解的评估过程不被执行；计算完该解后需要继续根据上层目标值决定该解是否代替该次搜索的起点；

S4-4解的扰动；

该操作多次地执行顾客的随机移除顾客和插入顾客的操作进行扰动，使得每次大邻域算法开始的起点都不同；

S4-5、建立集划分模型；

当路径池中获得了求解问题的所有可行路径后，算法使用这些路径建立集合划分模型，其所述的模型进一步包括：

S4-5-1、集划分模型变量定义如下：R为护士n关于下层路径规划与时间调度模型可行的路径集合，R

S4-5-2、集划分模型目标函数如下：

S4-5-3、模型约束条件如下：

该约束确保最终选择的路径能覆盖所有的顾客并且每位顾客被访问仅仅一次；

该约束保证每位护士最多从其可行路径集合中选择一条路径。其中

S4-6、求解集划分模型；

循环地求解集划分模型，对于每一次得到的最小运营成本解，如果存在对于下层问题为不可行的路径，则需要在路径池中对其进行移除，之后使用新的路径池更新SP，继续循环求解，直到当前得到的新解中的每条路径都满足下层问题的最优条件，则该解为双层问题的优解；

S4-7、对双层解使用后优化算法；

为了对随机变量的期望进行计算，所有护士的出发时间默认为其最早工作开始时间；在求得随机双层规划模型的解之后，设计了确定最优出发时间的后优化方法来实现对服务满意水平的预测。该算法具体是对解中每条路径的可能开始的出发时间都计算该路径期望服务满意评分的和，最后选择最大的服务满意评分和的出发时间作为护士选择的出发时间行为；

为了验证本发明的技术效果，将通过具体实验案例验证本发明方法在解决分层决策下随机家庭医疗护理调度问题上的有效性：

在对测试实例运行之前，首先需要对算法的参数进行实验分析，以确定表现好的参数配置。数值实验采用30个小测试医疗护理实例以及15个大规模测试实例，这些实例可以在网址http://alpha.uhasselt.be/kris.braekers/上获得。关于模型的参数中，需要明确服务满意评分函数中参数的取值，即四个临界点的设置。对于每位顾客i∈C，假定临界点

表1 三阶段混合元启发式算法统计分析结果

其中，Best.TC表示在5次运行中与精确解偏差最小的运营成本(对于NT＝10顾客的案例)或者在5次运行中取得的最小运营成本(对于NT>10顾客的案例)；Best.SL表示对应于Best.TC的服务满意水平；avg.TC表示5次运行中TC的平均值；avg.SL表示5次运行中SL的平均值；std

表1给出了算法的统计分析结果。对于只包含10个顾客的实例来说，算法获得了这几个小实例的最优解，这反映出算法是有效的。对于大多数的实例，std

与确定性模型相比，随机模型在订单指派的阶段需要更多的护士数量，并且随着随机环境不确定性的增加，所需要的护士数量也相应地增加。随机模型比确定性模型有着更高的成本，并且随着随机波动程度的增加，大多数实例的运营成本是显著上升的。造成该现象的主要原因是随机波动导致了加班成本的大幅上升。确定性环境下得到的最优解往往在随机环境下表现的比较差。特别是在随机波动程度比较高的情况下，忽视随机环境将严重损害公司的经济利益以及服务满意水平。因此家庭医疗护理公司必须在指派订单阶段重视路径中的随机因素，因为在确定性环境下得到的最优解在现实情况中可能是不适用的。

因此结合上述案例结果可以看到，本发明方法从随机优化的角度解决了分层决策模式下家庭医疗护理公司的调度问题，求解得到的调度方案同时考虑了家庭医疗护理公司和护士的分层决策行为，降低公司在该服务模式下的运营成本同时，保证了较好的顾客满意水平。

以上所述仅是对本发明的优选实施例及原理进行了详细说明，对本领域的普通技术人员而言，依据本发明提供的思想，在具体实施方式上会有改变之处，而这些改变也应视为本发明的保护范围。