一种居家医疗服务车辆及医疗人员的重调度方法和装置

1.本发明涉及管理科学技术领域，尤其涉及一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法和装置。


背景技术：

2.居家医疗服务旨在为患者提供居家医疗和护理服务。对患者来说，期望获得的居家医疗服务质量应当不低于医院提供的同类服务；对医院等居家医疗服务中心（以下简称中心）来说，则期望尽可能控制成本。居家医疗服务研究领域问题涉及环节具备高度的不确定性和多样性，例如医疗人员针对不同患者的旅行时间、医疗持续时间和提供的医疗服务不定，不同医疗人员往往具备不同技能和专长，患者对医疗人员的技能、性别和对服务时间的偏好多变等等。因此，如何在尊重患者需求的前提下，用运筹学、工业工程和智能算法领域的工具实现医疗人员的高效分配（人员和时间），并设计科学访问路线从而最大限度节约医疗人力资源、节约中心成本，成为居家医疗服务研究领域的重点之一。
3.而在现有典型的居家医护服务车辆及医护人员的路径和调度问题（home health care routing and scheduling problem, hhcrsp）领域，研究大多假设患者数量、患者需求和访问安排是提前已知且固定的；即使考虑需求动态性，也更关注预约的临时取消等方面，较少考虑临时新增患者，对于临时新增患者后对原调度计划进行改变的重调度问题更是很少有研究。


技术实现要素：

4.本发明提供了一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法和装置，用以对允许拒绝新患者的居家医疗服务车辆及医疗人员进行重调度。所述技术方案如下：
5.一方面，提供了一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法，包括：
6.s1、建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解作为所述hhcrrp-npr的初始解，所述最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；
7.s2、分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；
8.s3、将所述初始解变换成自适应大邻域搜索算法alns的解的形式；
9.s4、设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；
10.s5、基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性
硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。
11.另一方面，提供了一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度装置，包括：
12.初始解求解模块，用于建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解或近似最优解作为所述hhcrrp-npr的初始解，所述最优解或近似最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；
13.模型建立模块，用于分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；
14.初始解变换模块，用于将所述初始解变换成自适应大邻域搜索算法alns的解的形式；
15.邻域变换算子设计模块，用于设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；
16.近似最优解生成模块，用于基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。
17.另一方面，提供了一种电子设备，所述电子设备包括处理器和存储器，所述存储器中存储有至少一条指令，所述至少一条指令由所述处理器加载并执行以实现上述允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法。
18.另一方面，提供了一种计算机可读存储介质，所述存储介质中存储有至少一条指令，所述至少一条指令由处理器加载并执行以实现上述允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法。
19.上述技术方案，与现有技术相比至少具有如下有益效果：
20.本发明构建针对居家医疗服务多元化和临时新增需求的重调度问题，分析问题特性并建立混合整数规划模型，设计了改进的自适应大邻域搜索算法，最终实现对问题的高效求解。本发明有助于解决医疗人员紧缺与居家医疗服务需求激增的矛盾，填补当前居家医疗服务资源调度优化领域较少针对新增需求的空白，不仅可以高效解决大规模算例，同时不依赖于算例本身，具有良好的适用性。
附图说明
21.为了更清楚地说明本发明实施例中的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
22.图1为本发明实施例提供的一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法流程图；
23.图2为本发明实施例提供的原患者不可拒绝策略示意图；
24.图3为本发明实施例提供的根据所需技能将患者实际结点转换为患者虚拟结点示意图；
25.图4为本发明实施例提供的患者实际结点、所需技能点和患者虚拟结点之间的映射关系示意图；
26.图5为本发明实施例提供的将所述初始解中的原患者-医疗人员分配方案，变换成原患者虚拟结点-医疗人员分配方案示意图；
27.图6为本发明实施例提供的最短边插入算子示意图；
28.图7为本发明实施例提供的加入扰动的最短边插入算子示意图；
29.图8为本发明实施例提供的2-opt算子示意图；
30.图9为本发明实施例提供的or-opt算子示意图；
31.图10为本发明实施例提供的最大生成距离移除算子示意图；
32.图11为本发明实施例提供的加入扰动的最大生成距离移除算子示意图；
33.图12为本发明实施例提供的使用患者虚拟结点表示的hhcrrp-npr的近似最优解的医疗人员-患者的分配方案；
34.图13为本发明实施例提供的一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度装置框图；
35.图14是本发明实施例提供的一种电子设备的结构示意图。
具体实施方式
36.为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例的附图，对本发明实施例的技术方案进行清楚、完整地描述。显然，所描述的实施例是本发明的一部分实施例，而不是全部的实施例。基于所描述的本发明的实施例，本领域普通技术人员在无需创造性劳动的前提下所获得的所有其他实施例，都属于本发明保护的范围。
37.如图1所示，本发明实施例提供了一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法，包括：
38.s1、建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解或近似最优解作为所述hhcrrp-npr的初始解，所述最优解或近似最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；
39.s2、分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；
40.s3、将所述初始解变换成自适应大邻域搜索算法alns的解的形式；
41.s4、设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；
42.s5、基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。
43.本发明实施例在尽量减少对提前预约的原患者影响的同时，吸纳尽可能多的原调度计划外需求，同时兼顾不同患者对于医护人员技能的个性化需求匹配，本发明实施例针对包含提前预约的原患者（以下简称原患者）和临时新增患者（以下简称新患者）两类患者群体的居家医疗服务问题场景，提出了一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法，考虑允许拒绝新患者的居家医疗服务车辆资源及护理人员重调度问题（home health care routing and rescheduling problem with new patients rejection ,hhcrrp-npr)包含原调度问题和重调度问题，其中，原调度问题根据原患者地理坐标欧氏空间位置、访问原患者时间窗和原患者对于医护人员技能的个性化要求，以最少医护人员指派人数、车辆路径总路程最短和原患者需求全覆盖三个原则生成原调度计划。重调度问题将新患者纳入新调度计划，允许拒绝服务新患者并设置单次拒绝成本；由于重调度改变了原调度计划，部分原患者的原定指派医护人员及原定服务开始/结束时间必然发生改变和扰动，本发明实施例中的重调度问题对上述扰动时间（扰动时间为重调度计划中原有工作提交日期相对原调度计划中相同工作提交时间的偏离值）设置限制，同时要求所有被服务患者的个性化需求必须被满足。本发明实施例以求解医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本四个目标函数值的帕累托最优值为目标。本发明实施例的hhcrrp-npr复杂度至少不低于传统车辆路径问题（vehicle routing problem ,vrp)，因此属于np全问题。
44.下面结合图2-图11，详细说明本发明实施例的一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法，包括：
45.s1、建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解作为所述hhcrrp-npr的初始解，所述最优解或近似最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；
46.可选地，所述s1中原调度问题的混合整数规划模型如下：
47.索引：
48.原患者结点索引族
49.居家医疗护理中心
50.中心和原患者结点之间的无向弧
51.由中心和所有原患者结点及其之间的无向弧构成的图
52.居家医疗人员索引
53.医疗服务种类索引
54.参数：
55.患者结点到的欧氏距离
56.患者结点到的旅行时间
57.居家医疗人员除去午休时间的工作时间
58.患者要求的服务时间窗
59.医疗人员在患者处的到达时间
60.医疗人员技能矩阵，若医疗人员具备技能则为1，否则为0
61.患者需求矩阵，若患者所需服务需要医疗人员具备技能则为1，否则为0
62.居家医疗服务的服务时间
[0063] 医疗人员的固定指派成本
[0064]
车辆单位距离旅行成本
[0065]
变量：
[0066]
医疗人员访问患者结束之后紧接着继续访问患者则为1，否则为0
[0067]
如果在调度计划中指派医疗人员则为1，否则为0
[0068]
模型：
[0069]
（1-1）
[0070]
（1-2）
[0071]
（1-3）
[0072]
（1-4）
[0073] （1-5）
[0074] （1-6）
[0075] （1-7）
[0076] （1-8）
[0077] （1-9）
[0078] （1-10）（1-11）
[0079] （1-12）
[0080] （1-13）
[0081]
（1-14）
[0082]
所述原调度问题的目标为确定最优的医疗人员与原患者指派方案及访问顺序，实现医疗人员指派成本和车辆总旅行成本的帕累托最优；
[0083]
约束条件中，约束(1-2)保证每位患者最多由一名医疗人员服务；约束(1-3)保证所有原患者均被服务，且医疗人员服务完各位原患者后离开该结点；约束(1-4)和(1-5)强制医疗人员必须从中心往返；约束(1-6)表示被指派医疗人员的技能高于患者要求水平；约束(1-7)
‑ꢀ
(1-10)为医疗人员服务时间窗和原患者柔性硬时间窗约束；约束(1-11)定义了考虑医疗人员在途时间和具体服务时间的原患者结点到达时间；约束(1-12)和(1-13)为子环路消除约束。
[0084]
s2、分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；
[0085]
可选地，所述s2中分析出的所述hhcrrp-npr的特性，具体包括：
[0086]
①ꢀ
原患者和新患者：
[0087]
所述hhcrrp-npr问题面向原患者和新患者两类患者群体，并针对两类患者执行不同的服务策略：原患者不可拒绝策略、新患者可拒绝策略以及跨级服务策略；
[0088]
其中，原患者不可拒绝策略：指重调度时必须服务所有原患者，但是允许一定扰动时间，在允许扰动时间范围内，推迟服务结束时间存在延迟服务惩罚成本（图2中（b）所示），对提前开始服务不设置惩罚（图2中（a）所示），服务结束时间在允许扰动时间范围外，违反时间窗，不允许（图2中（c）所示）；
[0089]
新患者可拒绝策略：指重调度时可选择服务或拒绝新患者，如果拒绝新患者则产生拒绝成本；
[0090]
跨级服务策略：对两类患者均执行跨级服务策略，具备多技能的医疗人员可为预约少技能的患者服务；
[0091]
②ꢀ
目标：
[0092]
所述hhcrrp-npr问题的目标为确定最优/近似最优的医疗人员与患者指派方案及访问顺序，实现医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本四项目标函数值的帕累托最优；
[0093]
③ꢀ
原患者柔性硬时间窗：
[0094]
柔性：指重调度计划中，原患者的原时间窗与最大允许扰动时间构成新时间窗，医疗人员服务开始或结束时间可以在此范围内超出原时间窗；
[0095]
硬时间窗：指医疗人员服务开始或结束时间不得超出新时间窗。
[0096]
可选地，所述s2中建立的所述hhcrrp-npr的混合整数规划模型如下：
[0097]
索引：
[0098] 原患者结点索引族
[0099]
新患者结点索引族
[0100]
居家医疗护理中心
[0101]
中心和原患者结点之间的无向弧
[0102]
中心和所有患者结点之间的无向弧
[0103]
由中心和所有原患者结点及其之间的无向弧构成的图
[0104]
由中心和所有患者结点及其之间的无向弧构成的图
[0105]
居家医疗人员索引
[0106]
医疗服务种类索引
[0107]
参数：
[0108]
重调度计划的任意可行解
[0109]
原调度计划的最优解或近似最优解
[0110]
患者结点到的欧氏距离
[0111]
患者结点到的旅行时间
[0112]
居家医疗人员除去午休时间的工作时间
[0113]
患者要求的服务时间窗
[0114]
医疗人员在患者处的到达时间
[0115]
医疗人员技能矩阵，若医疗人员具备技能则为1，否则为0
[0116]
患者需求矩阵，若患者所需服务需要医疗人员具备技能则为1，否则为0
[0117]
居家医疗服务的服务时间
[0118]
医疗人员的固定指派成本
[0119]
在原患者结点处推迟开始服务时间时的等待惩罚成本
[0120]
车辆单位距离旅行成本
[0121]
新患者的拒绝成本
[0122]
原患者的扰动时间
[0123]
最大允许扰动时间
[0124]
变量：
[0125]
医疗人员访问患者结束之后紧接着继续访问患者则为1，否则为0
[0126]
如果在调度计划中指派医疗人员则为1，否则为0
[0127]
如果在调度计划中拒绝服务新患者则为1，否则为0
[0128]
如果原患者在原时间窗被服务则为1，否则为0
[0129]
如果在原患者处服务结束时间晚于原时间窗最晚结束时间则为1，否则为0
[0130]
模型：
[0131] （2-1）
[0132] （2-2）
[0133] （2-3）
[0134] （2-4）
[0135] （2-5）
[0136] （2-6）
[0137] （2-7）
[0138] （2-8）
[0139] （2-9）
[0140] （2-10）
[0141] （2-11）
[0142] （2-12）
[0143] （2-13）
[0144] （2-14）
[0145] （2-15）（2-16）
[0146] （2-17）
[0147] （2-18） （2-19）
[0148]
约束条件中，约束(2-2)保证每位患者最多由一名医疗人员服务；约束(2-3)保证所有原患者均被服务，且医疗人员服务完各位原患者后离开该结点；约束(2-4)表示原患者只有按时被服务、在允许扰动时间内提前被服务、在允许扰动时间内推迟结束服务三种情况；约束(2-5)表示新患者只有得到服务和被拒绝服务两种情况；约束(2-6)和(2-7)强制医疗人员必须从中心往返；约束(2-8)表示被指派医疗人员的技能高于患者要求水平；约束(2-9)
‑ꢀ
(2-12)为医疗人员服务时间窗和原患者柔性硬时间窗约束；约束(2-13)
‑ꢀ
(2-15)为原患者扰动时间约束；约束(2-16)定义了考虑医疗人员在途时间和具体服务时间的患者
结点到达时间；约束(2-17)和(2-18)为子环路消除约束。
[0149]
s3、将所述初始解变换成自适应大邻域搜索算法alns的解的形式；
[0150]
不同于单医护人员类型的hhcrrp-npr问题，本发明实施例待解决问题考虑了具备不同技能的多种医护人员类型和跨级服务策略，因此不仅需要考虑医护人员在两种患者结点的先后访问顺序，还需要考虑各个患者对于不同类型医护人员的分配问题。因为本发明实施例待解决问题考虑患者的多元需求，所述初始解并不能直接用于自适应大邻域搜索算法alns作为初始解迭代：
[0151]
例如，考虑包含6名原患者和4名医护人员的hhcrrp-npr问题，假设原问题最优分配方案为将患者1、2分配给医护人员1，最优访问次序为2-1；将患者3、4分配给医护人员2，最优访问次序为3-4；将患者5和6分别分配给医护人员3和4。则gurobi中输出最优解的表现形式为：；剩余决策变量如等于0。
[0152]
显然，该解的数学形式表达并不能直接进入alns框架内进行邻域变换。另外，基于该表达形式的解无法有效对应患者所需技能和医护人员具备技能，如只能表达医护人员2服务患者3后立刻服务患者4，且医护人员2具备技能能够满足患者3和 4的需求；但是在alns算法迭代中，假如算子试图将患者3或4指派给其他医护人员，则因无法确定需求覆盖关系而无法进行。
[0153]
因此本发明实施例需将所述初始解变换成自适应大邻域搜索算法alns的解的形式，具体包括：
[0154]
对原患者实际结点进行变换，根据原患者实际结点到所需技能的映射关系，通过构建从所需技能到原患者虚拟结点的单射，将原患者实际结点转换为只对应单一技能需求的原患者虚拟结点；
[0155]
采用带分隔符的离散式编码方式，将所述初始解中的原患者-医疗人员分配方案，变换成原患者虚拟结点-医疗人员分配方案；
[0156]
采用带分隔符的离散式编码方式，将所述初始解中的每位医疗人员搭乘车辆的路径方案，变换成使用原患者虚拟结点表示的每位医疗人员搭乘车辆的路径方案。
[0157]
例如，考虑6名患者（包括原患者和新患者，本发明实施例需要将所有患者实际节点变换成患者虚拟节点）和4类医疗人员服务技能，假设患者1为单技能需求患者（需要技能1）；剩余5名患者均要求多项技能：患者2、3、4除技能1外，还分别需要技能2、3、4；患者5需要技能1、2、3；患者6需要全部技能。如图3所示，显然6个患者实际结点到4个需求技能点无法构成单射，即多个患者实际结点可能指向同一个所需技能点。如图4所示，通过构建患者虚拟结点，可建立4个所需技能到患者虚拟节点的单射关系，则将6个实际患者结点转换为14个患者虚拟结点：所需技能1对应所有6名患者，则构建虚拟节点1-6，虚拟结点1-6均只有所需技能点1映射其上；类似地，技能点2映射虚拟结点7-9，技能点3映射虚拟节点10-12，技能点4映射虚拟结点13和14（参见图4）。
[0158]
如图5所示，采用带分隔符的离散式编码方式，将所述初始解中的原患者-医疗人
员分配方案：，变换成原患者虚拟结点-医疗人员分配方案：。其中，元素1-14对应14个患者结点，元素15-18为分隔符，用以区分患者虚拟结点在不同医护人员上的分配，该解实际表示患者1和2分配给医护人员1，患者3和4分配给医护人员2，患者5分配给医护人员3，患者6分配给医护人员4。
[0159]
同上，采用带分隔符的离散式编码方式，将所述初始解中的每位医疗人员搭乘车辆的路径方案，变换成使用原患者虚拟结点表示的每位医疗人员搭乘车辆的路径方案。
[0160]
s4、设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；
[0161]
本发明实施例待解决问题不同于传统vrp，因允许拒绝新患者的特性，导致各可行解的长度（输出路径包含结点的数量）可能不一致，因此传统自适应大邻域搜索算法（adaptive large neighborhood search algorithm ,alns)的破坏+修复操作的算法逻辑不适用于该问题。此外，重调度问题的初始可行解为原调度问题的最优解或近似最优解，为了在后续迭代中生成包含新患者结点的可行解，应当优先对初始解进行结点插入操作。基于上述问题特性分析，本发明实施例将传统alns中的破坏和修复算子改设为新患者结点移除算子和新患者结点插入算子，仍然分别用和表示；并且首先执行新患者结点插入算子，再执行新患者结点移除算子，同时对新患者结点插入算子设定更多迭代次数，并且增加内部变换算子。
[0162]
可选地，所述s4中的新患者结点插入算子，为将当前解外的新患者结点引入的一类算子，具体包括：
[0163]
如图6所示，最短边插入算子：以概率t在最短边随机插入新患者结点，以概率1-t在当前解除最短边外的任意边上随机插入新患者结点，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点；
[0164]
如图7所示，加入扰动的最短边插入算子：对所述初始解的最短边长度加入随机值进行扰动，再以概率t选择扰动后的新最短边进行随机新患者结点的插入，以概率1-t在当前解除最短边外的任意边上随机插入新患者结点，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点；
[0165]
所述s4中的内部变换算子，为只通过当前解内部结点变换产生新解的一类算子，具体包括：
[0166]
如图8所示，2-opt算子：通过内部结点变换，将当前解中的两条边和替换为和；
[0167]
如图9所示，or-opt算子：将当前解中至多三个结点形成的结点链置换到其它位置；
[0168]
所述s4中的新患者结点移除算子，为可移除部分当前解中新患者结点后产生新解的一类算子，具体包括：
[0169]
如图10所示，最大生成距离移除算子：在当前解中找到产生最长相邻边的新患者结点，将其从当前解中移除，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点；
[0170]
如图11所示，加入扰动的最大生成距离移除算子：在当前解中找到产生最长相邻边的新患者结点，对其相临边加入随机值产生扰动，将扰动后产生最长相邻边的新患者结点从当前解中移除，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点。
[0171]
s5、基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。
[0172]
可选地，所述s5，具体包括：
[0173]
s51、设定固定参数，并结合所述sa框架metropolis准则，作为候选解的接受或拒绝规则，确定接受不优于当前解的劣解的概率；
[0174]
所述新患者结点插入算子集合、内部变换算子集合、新患者结点移除算子集合、内层最大迭代次数、外层最大迭代次数、新解优于最优解时获得分数、新解优于当前解时获得分数、接受不优于当前解的劣解时获得分数、挥发因子、噪音参数；
[0175]
s52、初始化可变参数：令内层迭代计数器初始值为0，外层迭代计数器初始值为1，初始化新患者结点插入算子概率，初始化内部变换算子概率，初始化新患者结点移除算子概率，初始化算子权值，初始化新患者结点插入算子分数、新患者结点移除算子分数、内部变换算子分数；
[0176]
s53、令当前解等于所述初始解，计算目标函数值；
[0177]
s54、选择新患者结点插入算子作用于，得到新解；使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反柔性硬时间窗的可行性验证，如果可行性验证通过，则进行下一步优劣性验证；优劣性验证中，比较和，如果，则接受新解，在具体算子处加分；如果，则接受新解，在具体算子处加分；否则以概率 接受新解，如接受新解，则在具体算子处加分；
[0178]
s55、选择内部变换算子作用于，得到新解；使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反柔性硬时间窗的可行性验证，如果可行性验证通过，则进行下一步优劣性验证；优劣性验证中，比较和，如果，则接受新解，在具体算子处加分；如果，则接受新解，在具体算子处加分；否则以概率接受新解，如接受新解，则在具体算子处加分；
[0179]
s56、选择新患者移除插入算子作用于，得到新解；使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反柔性硬时间窗的可行性验证，如果可行性验证通过，则进行下一步优劣性验证；优劣性验证中，比较和，如果，则接受新解, 在具体算子处加分；如果，则接受新解，在具体算子处加分；否则以概率接受新解，如接受新解，则在具体算子处加分；
[0180]
s57、重复s54至s56直到迭代次数达到内层最大迭代次数；为防止拥有较高分值的算子越来越倾向于始终被选择、较低分值算子倾向于被遗弃，从而导致算法陷入局部最优，在达到内层最大迭代次数时，重新初始化算子权值和分值，同时内层循环计数器归零，开始新一轮的内层迭代；
[0181]
s58、重复s57直至外层循环计数器达到最大值，此时算法达到终止条件，算法运行终止。
[0182]
可选地，所述s5中的使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，具体包括hhcrrp-npr问题混合整数规划模型的约束(2-9)-(2-15)。
[0183]
可选地，sa框架为：
[0184]
step1：确定初始温度，终止温度，降温速率，最大迭代次数；
[0185]
step2：比较新解和当前解的值，如果，则接受新解；反之，则根据metropolis准则来判断是否接受新解，即以的概率接受不优于当前解的新解，其中，为当前温度，由降温函数计算得到。
[0186]
设计总适应度函数计算目标函数值，即，其中各分项函数值根据公式(2-1)计算得到。
[0187]
所述hhcrrp-npr的近似最优解为使用患者虚拟节点表示的医疗人员-患者的分配方案（如图12所示）及每位医疗人员搭乘车辆的路径方案，可以将其进行解码：即去除分隔符，同时将患者虚拟结点还原为患者实际结点，得到以患者实际节点表示的医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。
[0188]
如图13所示，本发明实施例还提供了一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度装置，包括：
[0189]
初始解求解模块1310，用于建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解或近似最优解作为所述hhcrrp-npr的初始解，所述最优解或近似最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；
[0190]
模型建立模块1320，用于分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；
[0191]
初始解变换模块1330，用于将所述初始解变换成自适应大邻域搜索算法alns的解的形式；
[0192]
邻域变换算子设计模块1340，用于设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；
[0193]
近似最优解生成模块1350，用于基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。
[0194]
本发明实施例提供的一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度装置，其功能结构与本发明实施例提供的一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法相对应，在此不再赘述。
[0195]
图14是本发明实施例提供的一种电子设备1400的结构示意图，该电子设备1400可因配置或性能不同而产生比较大的差异，可以包括一个或一个以上处理器（central processing units，cpu）1401和一个或一个以上的存储器1402，其中，所述存储器1402中存储有至少一条指令，所述至少一条指令由所述处理器1401加载并执行以实现上述允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法的步骤。
[0196]
在示例性实施例中，还提供了一种计算机可读存储介质，例如包括指令的存储器，上述指令可由终端中的处理器执行以完成上述允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法。例如，所述计算机可读存储介质可以是rom、随机存取存储器（ram）、cd-rom、磁带、软盘和光数据存储设备等。
[0197]
本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件
来完成，也可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
[0198]
以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法，其特征在于，包括：s1、建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解作为所述hhcrrp-npr的初始解，所述最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；s2、分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；s3、将所述初始解变换成自适应大邻域搜索算法alns的解的形式；s4、设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；s5、基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。2.根据权利要求1所述的方法，其特征在于，所述s1中原调度问题的混合整数规划模型如下：索引：原患者结点索引族居家医疗护理中心中心和原患者结点之间的无向弧由中心和所有原患者结点及其之间的无向弧构成的图居家医疗人员索引医疗服务种类索引参数：患者结点到的欧氏距离患者结点到的旅行时间居家医疗人员除去午休时间的工作时间患者要求的服务时间窗医疗人员在患者处的到达时间医疗人员技能矩阵，若医疗人员具备技能则为1，否则为0
患者需求矩阵，若患者所需服务需要医疗人员具备技能则为1，否则为0居家医疗服务s的服务时间医疗人员i的固定指派成本车辆单位距离旅行成本变量：医疗人员访问患者结束之后紧接着继续访问患者则为1，否则为0如果在调度计划中指派医疗人员则为1，否则为0模型：（1-1）（1-2）（1-3）（1-4）（1-5）（1-6）（1-7）（1-8）（1-9）（1-10）（1-11）（1-12）（1-13）（1-14）所述原调度问题的目标为确定最优的医疗人员与原患者指派方案及访问顺序，实现医疗人员指派成本和车辆总旅行成本的帕累托最优；约束条件中，约束(1-2)保证每位患者最多由一名医疗人员服务；约束(1-3)保证所有原患者均被服务，且医疗人员服务完各位原患者后离开该结点；约束(1-4)和(1-5)强制医疗人员必须从中心往返；约束(1-6)表示被指派医疗人员的技能高于患者要求水平；约束(1-7)-(1-10)为医疗人员服务时间窗和原患者柔性硬时间窗约束；约束(1-11)定义了考虑医疗人员在途时间和具体服务时间的原患者结点到达时间；约束(1-12)和(1-13)为子环路消除约束。
3.根据权利要求1所述的方法，其特征在于，所述s2中分析出的所述hhcrrp-npr的特性，具体包括：
①
原患者和新患者：所述hhcrrp-npr问题面向原患者和新患者两类患者群体，并针对两类患者执行不同的服务策略：原患者不可拒绝策略、新患者可拒绝策略以及跨级服务策略；其中，原患者不可拒绝策略：指重调度时必须服务所有原患者，但是允许一定扰动时间，在允许扰动时间范围内，推迟服务结束时间存在延迟服务惩罚成本，对提前开始服务不设置惩罚，服务结束时间在允许扰动时间范围外，违反时间窗，不允许；新患者可拒绝策略：指重调度时可选择服务或拒绝新患者，如果拒绝新患者则产生拒绝成本；跨级服务策略：对两类患者均执行跨级服务策略，具备多技能的医疗人员可为预约少技能的患者服务；
②
目标：所述hhcrrp-npr问题的目标为确定最优/近似最优的医疗人员与患者指派方案及访问顺序，实现医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本四项目标函数值的帕累托最优；
③
原患者柔性硬时间窗：柔性：指重调度计划中，原患者的原时间窗与最大允许扰动时间构成新时间窗，医疗人员服务开始或结束时间可以在此范围内超出原时间窗；硬时间窗：指医疗人员服务开始或结束时间不得超出新时间窗。4.根据权利要求1所述的方法，其特征在于，所述s2中建立的所述hhcrrp-npr的混合整数规划模型如下：索引：原患者结点索引族新患者结点索引族居家医疗护理中心中心和原患者结点之间的无向弧中心和所有患者结点之间的无向弧由中心和所有原患者结点及其之间的无向弧构成的图由中心和所有患者结点及其之间的无向弧构成的图居家医疗人员索引医疗服务种类索引参数：重调度计划的任意可行解原调度计划的最优解或近似最优解患者结点到的欧氏距离
患者结点到的旅行时间居家医疗人员除去午休时间的工作时间患者要求的服务时间窗医疗人员在患者处的到达时间医疗人员技能矩阵，若医疗人员具备技能则为1，否则为0患者需求矩阵，若患者所需服务需要医疗人员具备技能则为1，否则为0居家医疗服务的服务时间医疗人员的固定指派成本在原患者结点处推迟开始服务时间时的等待惩罚成本车辆单位距离旅行成本新患者的拒绝成本原患者的扰动时间最大允许扰动时间变量：医疗人员访问患者结束之后紧接着继续访问患者则为1，否则为0如果在调度计划中指派医疗人员则为1，否则为0如果在调度计划中拒绝服务新患者则为1，否则为0如果原患者在原时间窗被服务则为1，否则为0如果在原患者处服务结束时间晚于原时间窗最晚结束时间则为1，否则为0模型：（2-1）（2-2）（2-3）（2-4）（2-5）（2-6）（2-7）
（2-8）（2-9） （2-10）（2-11）（2-12）（2-13）（2-14）（2-15）（2-16）（2-17）（2-18） （2-19）约束条件中，约束(2-2)保证每位患者最多由一名医疗人员服务；约束(2-3)保证所有原患者均被服务，且医疗人员服务完各位原患者后离开该结点；约束(2-4)表示原患者只有按时被服务、在允许扰动时间内提前被服务、在允许扰动时间内推迟结束服务三种情况；约束(2-5)表示新患者只有得到服务和被拒绝服务两种情况；约束(2-6)和(2-7)强制医疗人员必须从中心往返；约束(2-8)表示被指派医疗人员的技能高于患者要求水平；约束(2-9)
‑ꢀ
(2-12)为医疗人员服务时间窗和原患者柔性硬时间窗约束；约束(2-13)
‑ꢀ
(2-15)为原患者扰动时间约束；约束(2-16)定义了考虑医疗人员在途时间和具体服务时间的患者结点到达时间；约束(2-17)和(2-18)为子环路消除约束。5.根据权利要求1所述的方法，其特征在于，所述s3，具体包括：对原患者实际结点进行变换，根据原患者实际结点到所需技能的映射关系，通过构建从所需技能到原患者虚拟结点的单射，将原患者实际结点转换为只对应单一技能需求的原患者虚拟结点；采用带分隔符的离散式编码方式，将所述初始解中的原患者-医疗人员分配方案，变换成原患者虚拟结点-医疗人员分配方案；采用带分隔符的离散式编码方式，将所述初始解中的每位医疗人员搭乘车辆的路径方案，变换成使用原患者虚拟结点表示的每位医疗人员搭乘车辆的路径方案。6.根据权利要求5所述的方法，其特征在于，所述s4中的新患者结点插入算子，为将当前解外的新患者结点引入的一类算子，具体包括：最短边插入算子：以概率t在最短边随机插入新患者结点，以概率1-t在当前解除最短边外的任意边上随机插入新患者结点，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点；加入扰动的最短边插入算子：对所述初始解的最短边长度加入随机值进行扰动，再以概率t选择扰动后的新最短边进行随机新患者结点的插入，以概率1-t在当前解除最短边外
的任意边上随机插入新患者结点，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点；所述s4中的内部变换算子，为只通过当前解内部结点变换产生新解的一类算子，具体包括：2-opt算子：通过内部结点变换，将当前解中的两条边和替换为和；or-opt算子：将当前解中至多三个结点形成的结点链置换到其它位置；所述s4中的新患者结点移除算子，为可移除部分当前解中新患者结点后产生新解的一类算子，具体包括：最大生成距离移除算子：在当前解中找到产生最长相邻边的新患者结点，将其从当前解中移除，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点；加入扰动的最大生成距离移除算子：在当前解中找到产生最长相邻边的新患者结点，对其相临边加入随机值产生扰动，将扰动后产生最长相邻边的新患者结点从当前解中移除，所述新患者结点为根据新患者实际结点变换后的新患者虚拟结点。7.根据权利要求1所述的方法，其特征在于，所述s5，具体包括：s51、设定固定参数，并结合所述sa框架metropolis准则，作为候选解的接受或拒绝规则，确定接受不优于当前解的劣解的概率；所述新患者结点插入算子集合、内部变换算子集合、新患者结点移除算子集合、内层最大迭代次数、外层最大迭代次数、新解优于最优解时获得分数、新解优于当前解时获得分数、接受不优于当前解的劣解时获得分数、挥发因子、噪音参数；s52、初始化可变参数：令内层迭代计数器初始值为0，外层迭代计数器初始值为1，初始化新患者结点插入算子概率，初始化内部变换算子概率，初始化新患者结点移除算子概率，初始化算子权值，初始化新患者结点插入算子分数、新患者结点移除算子分数、内部变换算子分数；s53、令当前解等于所述初始解；s54、选择新患者结点插入算子作用于，得到新解；使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反柔性硬时间窗的可行性验证，如果可行性验证通过，则进行下一步优劣性验证；优劣性验证中，比较和，如果，则接受新解，在具体算子处加分；如果，则接受新解，在具体算子处加分；否则以概率接受新解，如接受新解，则在具体算子处加分 ；
s55、选择内部变换算子作用于，得到新解； 使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反柔性硬时间窗的可行性验证，如果可行性验证通过，则进行下一步优劣性验证；优劣性验证中，比较和，如果 ，则接受新解，在具体算子处加分；如果，则接受新解，在具体算子处加分；否则以概率接受新解，如接受新解，则在具体算子处加分；s56、选择新患者移除插入算子作用于，得到新解使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反柔性硬时间窗的可行性验证，如果可行性验证通过，则进行下一步优劣性验证；优劣性验证中，比较和，如果，则接受新解, 在具体算子处加分；如果，则接受新解，在具体算子处加分；否则以概率接受新解，如接受新解，则在具体算子处加分；s57、重复s54至s56直到迭代次数达到内层最大迭代次数；为防止拥有较高分值的算子越来越倾向于始终被选择、较低分值算子倾向于被遗弃，从而导致算法陷入局部最优，在达到内层最大迭代次数时，重新初始化算子权值和分值，同时内层循环计数器归零，开始新一轮的内层迭代；s58、重复s57直至外层循环计数器达到最大值，此时算法达到终止条件，算法运行终止。8.根据权利要求4所述的方法，其特征在于，所述s5中的使用所述hhcrrp-npr的混合整数规划模型中的约束，对所述邻域变换后得到的新解进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，具体包括hhcrrp-npr问题混合整数规划模型的约束(2-9)-(2-15)。9.一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度装置，其特征在于，包括：初始解求解模块，用于建立允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度问题hhcrrp-npr的原调度问题的混合整数规划模型，利用gurobi求解器求解所述原调度问题，得到所述原调度问题的最优解作为所述hhcrrp-npr的初始解，所述最优解包括：医疗人员-原患者分配方案和每位医疗人员搭乘车辆的路径方案；模型建立模块，用于分析出所述hhcrrp-npr的特性，建立所述hhcrrp-npr的混合整数规划模型；初始解变换模块，用于将所述初始解变换成自适应大邻域搜索算法alns的解的形式；邻域变换算子设计模块，用于设计适用于所述hhcrrp-npr的改进alns算法的邻域变换算子，所述邻域变换算子包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；近似最优解生成模块，用于基于改进的alns算法框架，结合模拟退火算法sa框架的metropolis准则，利用上述三类算子对所述初始解进行邻域变换，并使用所述hhcrrp-npr
的混合整数规划模型中的约束，对所述邻域变换后得到的新解，进行是否违反医疗人员服务时间窗和原患者柔性硬时间窗的可行性验证，迭代生成所述hhcrrp-npr的近似最优解，所述近似最优解为达到医疗人员指派成本、车辆总旅行成本、原患者等待成本、新患者拒绝成本的帕累托最优的医疗人员分配和车辆路径规划重调度方案，所述近似最优解包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。

技术总结
本发明公开一种允许拒绝新患者的居家医疗服务车辆及医疗人员的重调度方法和装置，包括：建立HHCRRP-NPR原调度问题的混合整数规划模型，求解得到最优解作为HHCRRP-NPR的初始解；建立HHCRRP-NPR的混合整数规划模型；将初始解变换成ALNS的解的形式；设计适用于HHCRRP-NPR的改进ALNS算法的邻域变换算子，包括：新患者结点插入算子、内部变换算子和新患者结点移除算子；基于改进的ALNS算法框架，结合SA框架，利用上述三类算子对初始解进行邻域变换，并使用HHCRRP-NPR的混合整数规划模型中的约束，对邻域变换后得到的新解，进行可行性验证，迭代生成近似最优解，包括：可服务的新患者名单、医疗人员-患者的分配方案及每位医疗人员搭乘车辆的路径方案。本发明能有效解决HHCRRP-NPR。NPR。NPR。


技术研发人员：毛照昉 潘乔 黄典 方侃
受保护的技术使用者：天津大学
技术研发日：2023.06.27
技术公布日：2023/8/5