广西师范大学学报（自然科学版） ›› 2021, Vol. 39 ›› Issue (3): 27-39.doi: 10.16088/j.issn.1001-6600.2020061703

• • 上一篇    下一篇

基于均值漂移和遗传算法的护工调度算法

胡竣涛1, 时小虎2, 马德印1,3*   

  1. 1.长春工业大学 计算机科学与工程学院, 吉林 长春 130012;
    2.吉林大学 计算机科学与技术学院, 吉林 长春 130012;
    3.吉林大学 商学院, 吉林 长春 130012
  • 收稿日期:2020-06-17 修回日期:2020-10-23 发布日期:2021-05-13
  • 通讯作者: 马德印(1978—),男,长春工业大学讲师,博士。E-mail: madeyin@mail.ccut.edu.cn
  • 基金资助:
    国家自然科学基金(61972174); 吉林省教育厅社会科学项目(JJKH20190210SK); 吉林省科技厅科技发展计划项目(20200101146FG)

Nursing Workers Scheduling Based on Mean Shift and Genetic Algorithm

HU Juntao1, SHI Xiaohu2, MA Deyin1,3*   

  1. 1. School of Computer Science and Engineering, Changchun University of Technology, Changchun Jilin 130012, China;
    2. College of Computer Science and Technology, Jilin University, Changchun Jilin 130012, China;
    3. Business School, Jilin University, Changchun Jilin 130012, China
  • Received:2020-06-17 Revised:2020-10-23 Published:2021-05-13

PDF (PC)

221

摘要： 随着中国人口老龄化的加剧,居家养老服务需求迅速增加。在一些大型社区中,由于对居家养老业务的需求量庞大,护工的调度问题变得愈发重要。但目前仅有少量文献对此进行研究,且都是基于已知护工数量的前提,无法为服务中心招收各等级护工数量提供参考。本文提出一种基于均值漂移聚类和遗传算法的护工调度算法,在完成所有老人护理任务的前提下进行护工的合理调配。算法首先将老人按照位置及所需护工等级进行聚类,以减少计算规模;然后采用遗传算法,使用实数编码方式和精英保留策略,对护工的服务路径进行规划,提高效率;最后将文中提出的算法应用于实际数据。实验结果表明,对老人进行聚类后再采用遗传算法能有效地降低成本、减少路径规划所需的时间。通过分析结果中所需不同等级的护工数量,给出了所需各等级护工数量与服务老人数量之间比例关系的建议。

关键词: 均值漂移, 遗传算法, 护工调度, 多路径规划

Abstract: With the intensification of China’s aging population, home health care services have been required increasingly. In some large communities, due to the huge demand for home health care services, the scheduling of nursing workers has been regarded as something more important. However, this issue is only addressed in a few studies based on the premise of the known number of nursing workers, through which a reference for the service center to recruit the number of nursing workers of different levels cannot be provided. A caregiver scheduling algorithm, which is based on mean shift clustering and genetic algorithm, is proposed in this paper. And reasonable allocation of caregivers is made under the condition of completing all the elderly nursing tasks. In this algorithm, the elderly are clustered first according to the required caregiver grade and position to reduce the calculation scale; then genetic algorithms, real-number coding and elite retention strategies are all used to plan the service path of the caregiver to improve efficiency. Finally, the algorithm proposed in this paper is applied to real data. The results that the cost and the time required for path planning after clustering the elderly can be reduced effectively by the genetic algorithm is shown in this experiment. Through the analysis of the number of different levels of nursing workers required in the results, some suggestions are provided on the proportional relationship between the number of nursing workers required in each level and the number of the elderly served.

Key words: mean shift, genetic algorithm, nursing workers scheduling, multipath planning

中图分类号: 

  • TP301.6
[1]GOTO A, NAKAMURA H. A study on appropriate road spacing for the functionally hierarchical network planning[J]. Transportation Research Procedia, 2017, 25:3817-3825. DOI:10.1016/j.trpro.2017.05.266.
[2]ZHENG L, HE Z M, LIANG W. VRP problem solving based on adaptive dynamic search ant colony algorithm[J]. Journal of Physics:Conference Series, 2020, 1487:012030. DOI:10.1088/1742-6596/1487/1/012030.
[3]BORYCZKAOU, SZWARC K. Selected variants of a Memetic Algorithm for JSP: a comparative study[J]. International Journal of Production Research, 2019, 57(22):7142-7157. DOI:10.1080/00207543.2019.1581385.
[4]冯翔, 马美怡, 施尹, 等. 基于社会群体搜索算法的机器人路径规划[J]. 计算机研究与发展, 2013, 50(12):2543-2553.
[5]叶苗, 王宇平, 魏静萱. 基于多移动节点和遗传算法的传感器网络覆盖修复策略[J]. 通信学报, 2014, 35(12):45-52, 61.
[6]朱杰, 张培斯, 张询影, 等. 基于改进蚁群算法的多时间窗车辆路径问题[J]. 计算机技术与发展, 2019, 29(1):102-105. DOI:10.3969/j.issn.1673-629X.2019.01.021.
[7]魏唯, 欧阳丹彤, 吕帅, 等. 动态不确定环境下多目标路径规划方法[J]. 计算机学报, 2011, 34(5):836-846. DOI:10.3724/SP.J.1016.2011.00836
[8]蔺一帅, 李青山, 陆鹏浩, 等. 智能仓储货位规划与AGV路径规划协同优化算法[J]. 软件学报, 2020, 31(9):2770-2784. DOI:10.13328/j.cnki.jos.005944.
[9]中国老龄协会. 老龄产业有望成为经济发展新增长点:《需求侧视角下老年人消费及需求意愿研究报告》在京发布[EB/OL]. (2019-04-16)[2020-10-18]. http://www.cncaprc.gov.cn/llxw/188883.jhtml.
[10]BEGUR S V, MILLER D M, WEAVER J R. An integrated spatial DSS for scheduling and routing home-health-care nurses[J]. INFORMS Journal on Applied Analytics, 1997, 27(4):35-48. DOI:10.1287/inte.27.4.35.
[11]SHI Y, BOUDOUH T, GRUNDER O. A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand[J]. Expert Systems with Applications, 2017, 72:160-176. DOI:10.1016/j.eswa.2016.12.013.
[12]DECERLE J, GRUNDER O,HAJJAM EL HASSANI A, et al. A memetic algorithm for a home health care routing and scheduling problem[J]. Operations Research for Health Care, 2018, 16:59-71. DOI:10.1016/j.orhc.2018.01.004.
[13]资元星. 居家养老预约调度与路径规划问题研究综述[J]. 经营与管理, 2019(1):143-145. DOI:10.16517/j.cnki.cn12-1034/f.2019.01.043.
[14]杨欣潼, 张婷, 白丽平, 等. 社区居家养老服务的预约调度与路径规划问题研究:基于改善蚁群算法[J]. 系统工程理论与实践, 2019, 39(5):1212-1224. DOI:10.12011/1000-6788-2017-1328-13.
[15]卢慧芳.广州市养老机构护理分级的现况研究[D]. 广州:南方医科大学,2007.
[16]HUANG Z Y, LIN S, LONG L L, et al. Predicting the morbidity of chronic obstructive pulmonary disease based on multiple locally weighted linear regression model with K-means clustering[J]. International Journal of Medical Informatics, 2020, 139:104141. DOI:10.1016/j.ijmedinf.2020.104141.
[17]ISWANTO I A, CHOA T W, LI B. Object tracking based on meanshift and particle-kalman filter algorithm with multi features[J]. Procedia Computer Science, 2019, 157:521-529. DOI:10.1016/j.procs.2019.09.009.
[18]卜秋瑾, 段隆振, 段文影. 结合遗传k均值改进的密度峰值聚类算法[J]. 计算机工程与设计, 2020, 41(4):1012-1016. DOI:10.16208/j.issn1000-7024.2020.04.019.
[19]D’URSO P, VITALE V. A robust hierarchical clustering for georeferenced data[J]. Spatial Statistics, 2020, 35:100407. DOI:10.1016/j.spasta.2020.100407.
[20]TANG F Q, WANG C N, SU J X, et al. Spectral clustering-based community detection using graph distance and node attributes[J]. Computational Statistics, 2020, 35(1):69-94. DOI:10.1007/s00180-019-00909-8.
[21]王爽, 夏玉, 焦李成. 基于均值漂移的自适应纹理图像分割方法[J]. 软件学报, 2010, 21(6):1451-1461. DOI:10.3724/SP.J.1001.2010.03723.
[22]云廷进, 郭永彩, 高潮. 基于粒子Mean Shift迁移的红外人体目标跟踪算法[J]. 计算机学报, 2009, 32(6):1222-1228. DOI:10.3724/SP.J.1016.2009.01222.
[23]戚荣志, 王志坚, 黄宜华, 等. 基于Spark的并行化组合测试用例集生成方法[J]. 计算机学报, 2018, 41(6):1064-1079. DOI:10.11897/SP.J.1016.2018.01284.
[24]何远, 张玉清, 张光华. 基于黑盒遗传算法的Android驱动漏洞挖掘[J]. 计算机学报, 2017, 40(5):1031-1043. DOI:10.11897/SP.J.1016.2017.01031.
[25]梁晓萍, 罗晓曙. 基于遗传自适应的维纳滤波图像去模糊算法[J]. 广西师范大学学报(自然科学版), 2017, 35(4):17-23. DOI:10.16088/j.issn.1001-6600.2017.04.003.
[26]刘焕淋, 李瑞艳, 孔德谦, 等. 基于多目标遗传算法优化弹性光网络的多路径保护机制[J]. 电子与信息学报, 2016, 38(9):2261-2267.
[27]许伦辉, 黄宝山, 钟海兴. AGV系统路径规划时间窗模型及算法[J]. 广西师范大学学报(自然科学版), 2019, 37(3):1-8. DOI:10.16088/j.issn.1001-6600.2019.03.001.
[1] 许伦辉, 曹宇超, 林培群. 基于融合免疫优化和遗传算法的多应急物资中心选址与调度[J]. 广西师范大学学报（自然科学版）, 2020, 38(6): 1-13.
[2] 叶青, 黄强, 聂斌, 李欢. 一种自适应的高维离群点识别方法[J]. 广西师范大学学报（自然科学版）, 2020, 38(2): 107-114.
[3] 张灿龙, 苏建才, 李志欣, 王智文. 基于AdaBoost置信图的红外与可见光目标跟踪[J]. 广西师范大学学报（自然科学版）, 2018, 36(4): 42-50.
[4] 梁晓萍,罗晓曙. 基于遗传自适应的维纳滤波图像去模糊算法[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 17-23.
[5] 蔡冰, 张灿龙, 李志欣. 基于联合直方图的红外与可见光目标融合跟踪[J]. 广西师范大学学报（自然科学版）, 2017, 35(3): 37-44.
[6] 刘伟铭, 李荣荣, 王超, 黄玲. 高速公路通行卡调拨问题的遗传算法[J]. 广西师范大学学报（自然科学版）, 2016, 34(1): 1-8.
[7] 刘宏, 王其涛, 夏未君. 基于量子遗传算法的WSN三维定位方法[J]. 广西师范大学学报（自然科学版）, 2015, 33(4): 49-54.
[8] 乐美龙, 高金敏. 轮辐式航线网络下机型分配与舱位控制的协同优化研究[J]. 广西师范大学学报（自然科学版）, 2014, 32(3): 33-40.
[9] 赵新超, 吴召军. 求解背包问题的多位极贪婪遗传算法[J]. 广西师范大学学报（自然科学版）, 2013, 31(4): 41-47.
[10] 曹永春, 邵亚斌, 田双亮, 蔡正琦. 一种基于免疫遗传算法的聚类方法[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 59-64.
[11] 蒋晓峰, 许伦辉, 朱悦. 基于SVM短时交通流量预测[J]. 广西师范大学学报（自然科学版）, 2012, 30(4): 13-17.
[12] 严晓明, 郑之. 基于混合仿生算法的SVM参数优化[J]. 广西师范大学学报（自然科学版）, 2011, 29(2): 114-118.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 庄枫红, 马姜明, 张雅君, 苏静, 于方明. 中华水韭对不同光照条件的生理生态响应[J]. 广西师范大学学报（自然科学版）, 2018, 36(3): 93 -100 .
[2] 张茹, 张蓓, 任鸿瑞. 山西轩岗矿区耕地流失时空特征及其影响因子研究[J]. 广西师范大学学报（自然科学版）, 2018, 36(3): 121 -132 .
[3] 王梦飞, 黄松. 广西西江经济带的城市旅游经济空间关联研究[J]. 广西师范大学学报（自然科学版）, 2018, 36(3): 144 -150 .
[4] 滕志军, 吕金玲, 郭力文, 许媛媛. 基于改进粒子群算法的无线传感器网络覆盖策略[J]. 广西师范大学学报（自然科学版）, 2018, 36(3): 9 -16 .
[5] 冯修, 马楠楠, 职红涛, 韩双乔, 张翔. 重金属捕集剂UDTC对低浓度镉废水的处理研究[J]. 广西师范大学学报（自然科学版）, 2018, 36(3): 63 -67 .
[6] 林越,刘廷章,陈一凡,金勇,梁立新. 基于AP-HMM混合模型的充电桩故障诊断[J]. 广西师范大学学报（自然科学版）, 2018, 36(1): 25 -33 .
[7] 黄兵方,闻炳海,邱文,赵琬玲,陈燕雁. 基于晶格Boltzmann方法的接触角实时测量研究[J]. 广西师范大学学报（自然科学版）, 2018, 36(1): 34 -43 .
[8] 呼文军,马忠军,马梅. 领导—跟随多智能体系统在分布式自适应控制下的滞后一致性[J]. 广西师范大学学报（自然科学版）, 2018, 36(1): 70 -75 .
[9] 梁艳,周德雄,薛佳津,刘晓波,李俊,杨瑞云. 中药血散薯中非生物碱类化学成分研究[J]. 广西师范大学学报（自然科学版）, 2018, 36(1): 95 -98 .
[10] 谢静,唐贺,林万华,孙华英,吴桂生,和晓明,邓科,罗怀容. 小鼠杏仁中央核逆向投射的研究[J]. 广西师范大学学报（自然科学版）, 2018, 36(1): 149 -157 .
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发