一种基于遗传算法的社区空巢老人帮扶调度方法

技术领域

本发明涉及领域，尤其涉及一种基于遗传算法的社区空巢老人帮扶调度方法。

背景技术

当今社会逐渐步入老龄化，很多子女外出求学务工，对空巢老人帮扶、照料是一个社区的重要工作。社区工作人员或医护人员一般从服务中心出发，依次访问各个老年人居住点并返回护理中心，由于社区工作人员或医疗护理人数有限，加上上门路程消耗，以及到达后的服务时间消耗，社区工作人员或医疗护理人员往往面临工作量大、工作效率低等问题，导致服务质量降低，老年人满意度不高。

问题可以转化为单服务中心和多服务人员类型以及随机服务时间的带软时间窗的上门护理人员调度问题。居家养老医疗护理服务中面临的一个主要问题是在满足约束的情况下，要求合理安排服务人员及其访问客户的路线，使得完成服务任务的总成本最小，客户时间满意度最高。合理优化与调度护理人员的客户访问次序对于充分利用服务资源，提高客户满意度和服务质量具有重要的意义。

目前路径规划的应用场景非常广泛，而其中遗传算法作为该领域的一个重要解决方式也得到了广泛的研究和应用。在遗传算法路径规划的研究中经常只是求得对单一最优路径解决方案，但是却遗漏了在真实应用场景中往往不是只有路径这单一因素影响实际的路径规划问题，如本发明中的老人帮扶调度还需要考虑时间满意度因子、社区服务站的最大资源负载因子、社工速度因子的影响，传统意义上的遗传算法单一最小路径无法满足。

发明内容

(一)发明目的

为解决背景技术中存在的技术问题，本发明提出一种基于遗传算法的社区空巢老人帮扶调度方法。

(二)技术方案

为解决上述问题，本发明提出了一种基于遗传算法的社区空巢老人帮扶调度方法，包括以下步骤：

S1：开始；

S2：创建初始族群；对初始群体数据进行编码；

S3：评价，通过评价得分进行群体筛选；

S4：判断是否满足停止准则；若，满足停止准则，则过程结束；若，不满足停止准则，则进入S5；

S5：产生新族群；其中，S3中满足条件的个体基因得以保留，将保留下的基因进行交叉遗传和基因突变，得到一个新的群体；

S6：重复S3-S5，直到满足全局最优解的出现后，结束迭代；

其中，对新族群的评价公式为：

总权重＝(各个线路距离之和×线路权重)+(各个老人的满意度之和×满意度权重)+(超负载工作时间之和×超负荷工作惩罚权重)+(规划线路数量×线路数量权重)；

评价包括以下因素：

A：路程距离；

欧式距离，两点距离计算，计算公式为：

C＝sin(MLatA)×sin(MLatB)×cos(MLonA-MLonB)+cos(MLatA)×cos(MLatB)。

根据经纬度计算，计算公式为：

Distance＝R×Arccos(C)×π/180；

B：时间满意度；其中，综合考虑服务人员的出发时间，行进路程和对老人提供服务的时间；在综合考虑之后，预估出服务人员对老人提供服务的时间段以及对应的老人满意度；

C：增加权重调整因子；其中，增加对服务路径数量的权重以及对超出工作负载的惩罚权重，在最优的服务人员数量下，达到老人时间满意度度的条件下算出最优路径。

优选的，群体大小为200；迭代次数不超过30次；S5中，交叉概率为0.8；突变概率为0.001。

优选的，初始群体数据进行字符编码；

在一个体编码中，0：表示社区服务站；1-32：表示呼叫请求的社区老人；

在一个基因序列中，包括7个请求服务和3个社区服务工作人员，以从工作站0到达每个需要服务的老人家为一个编码，染色体编码是多条路径编码。

优选的，交叉遗传的算法如下：

S51:包括父代染色体1和父代染色体2；随机选择子路径，记录子路径个数n1；

S52：将选择的子路径前置；

S53：将未访问的节点按照其在父代染色体2中的顺序排列；

S54：将未访问节点多次随机插0打断为1-(n1-1)条子路径；

S55：选择生产的子路径中代价最小的，添加到子染色体片段之后，形成完整的子染色体。

本发明中，对初始群体进行基因编目，通过评价得分进行群体筛选，满足条件的个体基因得以保留，将保留下的基因进行交叉遗传和基因突变，得到一个新的群体，迭代这个流程直到满足全局最优解的出现结束迭代。

本发明中，在对当下社区空巢老年人帮扶调方法中引入了带有时间满意度，服务人员最大工作时长等多因素下的调度规划解决方案；增加老人对被服务时间段内的满意度，同时是多路径而非单一路径调度会对大大增加算法的难度，就不能只简化求单一路径最优解方案，需要考虑服务人员在路程上和服务老人过程的时间消耗，预定到达时间，以及老人对时间满意度，以及社区服务站负载能力等多种因素。设计并优化算法对多种因素的权重平衡关系，最终在综合各个因素的情况下求得最优解。

附图说明

图1为本发明提出的基于遗传算法的社区空巢老人帮扶调度方法的流程图。

图2为本发明提出的基于遗传算法的社区空巢老人帮扶调度方法中字符编码的示意图。

图3为本发明提出的基于遗传算法的社区空巢老人帮扶调度方法中交叉遗传的算法流程图。

图4为本发明提出的基于遗传算法的社区空巢老人帮扶调度方法中染色体突变示意图。

图5为本发明提出的基于遗传算法的社区空巢老人帮扶调度方法中客户满意度示意图。

图6为本发明提出的基于遗传算法的社区空巢老人帮扶调度方法中的一个实施例的示意图。

具体实施方式

为使本发明的目的、技术方案和优点更加清楚明了，下面结合具体实施方式并参照附图，对本发明进一步详细说明。应该理解，这些描述只是示例性的，而并非要限制本发明的范围。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本发明的概念。

如图1和图5所示，本发明提出的一种基于遗传算法的社区空巢老人帮扶调度方法，包括以下步骤：

S1：开始；

S2：创建初始族群；对初始群体数据进行编码；

S3：评价，通过评价得分进行群体筛选；

S4：判断是否满足停止准则；若，满足停止准则，则过程结束；若，不满足停止准则，则进入S5；

S5：产生新族群；其中，S3中满足条件的个体基因得以保留，将保留下的基因进行交叉遗传和基因突变，得到一个新的群体；

S6：重复S3-S5，直到满足全局最优解的出现后，结束迭代；

其中，对新族群的评价公式为：

总权重＝(各个线路距离之和×线路权重)+(各个老人的满意度之和×满意度权重)+(超负载工作时间之和×超负荷工作惩罚权重)+(规划线路数量×线路数量权重)；

评价包括以下因素：

A：路程距离；

欧式距离，两点距离计算，计算公式为：

C＝sin(MLatA)×sin(MLatB)×cos(MLonA-MLonB)+cos(MLatA)×cos(MLatB)。

根据经纬度计算，计算公式为：

Distance＝R×Arccos(C)×π/180；

B：时间满意度；其中，综合考虑服务人员的出发时间，行进路程和对老人提供服务的时间；在综合考虑之后，预估出服务人员对老人提供服务的时间段以及对应的老人满意度；

C：增加权重调整因子；其中，增加对服务路径数量的权重以及对超出工作负载的惩罚权重，在最优的服务人员数量下，达到老人时间满意度度的条件下算出最优路径。

本发明中，对初始群体进行基因编目，通过评价得分进行群体筛选，满足条件的个体基因得以保留，将保留下的基因进行交叉遗传和基因突变，得到一个新的群体，迭代这个流程直到满足全局最优解的出现结束迭代。

本发明中，在对当下社区空巢老年人帮扶调方法中引入了带有时间满意度，服务人员最大工作时长等多因素下的调度规划解决方案；增加老人对被服务时间段内的满意度，同时是多路径而非单一路径调度会对大大增加算法的难度，就不能只简化求单一路径最优解方案，需要考虑服务人员在路程上和服务老人过程的时间消耗，预定到达时间，以及老人对时间满意度，以及社区服务站负载能力等多种因素。设计并优化算法对多种因素的权重平衡关系，最终在综合各个因素的情况下求得最优解。

在一个可选的实施例中，群体大小为200；迭代次数不超过30次；S5中，交叉概率为0.8(群体中有80％的个体进行交叉生成新一代个体)；突变概率为0.001(群体中有0.1％的个体发生基因突变)。其中，个体属性：经度longitude，纬度latitude，呼叫时间time，服务时长duration。服务资源：每人每天最大工作时长。

如图2所示：

在一个可选的实施例中，初始群体数据进行编码为有二进制编码或浮点编码。

在一个可选的实施例中，初始群体数据进行字符编码；

在一个体编码中，0：表示社区服务站；1-32：表示呼叫请求的社区老人；

在一个基因序列中，包括7个请求服务和3个社区服务工作人员，以从工作站0到达每个需要服务的老人家为一个编码，染色体编码是多条路径编码。

如图3所示：

在一个可选的实施例中，交叉遗传的算法如下：

S51:包括父代染色体1和父代染色体2；随机选择子路径，记录子路径个数n1；

S52：将选择的子路径前置；

S53：将未访问的节点按照其在父代染色体2中的顺序排列；

S54：将未访问节点多次随机插0打断为1-(n1-1)条子路径；

S55：选择生产的子路径中代价最小的，添加到子染色体片段之后，形成完整的子染色体。

需要说明的是：常用的交叉算法是单点交叉，即在基因序列上某点后面的基因全部交叉，这种方式不能最大保留原有父代优良基因，同时基因改变程度大，会很快达到局部最优解。本发明中。保留了一个完整路径基因不变，剩余父代基因重新排列后，将不同的基因编码用父2代替，这样虽然迭代次数增加，但可以保证全局最优解。

需要说明的是：传统的遗传算法的突变是对随机选中的某个基因进行突变，没有注意到原有基因的序列。

本发明对基因突变算法进行了优化。在突变后再次保留了原有的序列对，这样的突变导致生成的新的染色体看似同源染色体变动较大，但实则是是最大程度保留了序列对。

如图4所示：在染色体1的某子线路中发生突变，假设i＝2,j＝5则突变后该子线路发生了变化。原有基因编码5，9发生了对调，但为了保证原有的序列对，5跟6，9跟3序列对的出现，再次进行了调整最后突变。

在一个可选的实施例中，当社区空巢老人发起请求时，将老人的经纬度标注在地图上展示接到请求后调用本调度方法计算求出最优路线和各个路线的负载情况，如图6所示；最终根据遗传算法的执行情况绘制出完整的路线图。

综上，本发明是在遗传算法的基础上，加入了老人时间满意度、服务人员最大工作负载、线路距离等变量因子影响下求出路径规划的最优解，与传统的商旅路径问题的本质区别是不仅仅是单一最短路径的计算问题。

本发明具有以下优点：

一：优化了遗传算法对初始群组的编码方式，不像传统的线路规划问题只考虑规划单一线路，而是考虑实际服务人员的工作时长，规划最合理的线路数量同时考虑每条线路负载均衡问题。

二：线路交叉遗传的时候进行了合理的规划，在保证线路多样性的同时又使子线路继承了父辈线路的优越性，避免了无效的交叉，虽然可能会增加计算迭代次数，但在保障全局解上有优势。

三：线路突变算法思想为保障基因突变保留基因序列对不变，做了相邻基因序列对不变的优化，以最大程度保留优秀基因，防止突变突兀现象。

四：群体选择中的评价算法公式中用到线路距离因子、时间满意度因子、社区服务站负载因子、线路数量等多变量因子和权重参数来评价筛选下一代群体。

应当理解的是，本发明的上述具体实施方式仅仅用于示例性说明或解释本发明的原理，而不构成对本发明的限制。因此，在不偏离本发明的精神和范围的情况下所做的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。此外，本发明所附权利要求旨在涵盖落入所附权利要求范围和边界、或者这种范围和边界的等同形式内的全部变化和修改例。