社区居家养老服务的预约调度与路径规划问题研究:基于改善蚁群算法
|
摘要
随着中国人口进一步老龄化,养老行业受到各界越来越多的重视.中国的养老行业具有与其他国家不同的特点,表现为需要服务的老年人多且分布密集,一般以社区的形式集中在某个范围之内.这篇文章面向中国特色大型社区的居家养老服务领域,研究如何根据老人的预约来规划护工的路径并优化工作日程调度.本文根据三种护工技能水平和老人需求的组合,假设老人接受服务的时长服从正态分布,并通过设置不同的均值和方差值,研究了需求波动对算法和机构决策的影响.实际业务中老人一般会向机构事先提出预约,因此通过设置不同的时间窗对预约进行了数学描述,并分析了不同的预约类型和不同长短的预约时段对问题规划的影响.作者改善了原始蚁群算法的转移概率函数,使用多个实例对算法进行了测试分析,结果显示,计算机代替人工进行规划和调度将大幅节省决策者的时间成本.
With the Chinese population ageing, home-health-care industrials become more and more important. Characteristics of HHC in China differs from other countries, such as the intensive distribution of senior people, whose residence centralizes in community. This thesis' s problem was based on the field of home health care in huge communities in China, studying how to decline caregivers' moving distance and optimize the daily worksheets. According to three combinations of nurses' skill levels and customers' demands, service time of elders were assumed to obey normal distributions with different mean values and variances so as to analyze the impact from fluctuation of demands on algorithm and decision-making. In real business elders generally make appointments in advance, and appointments are descripted mathematically by time-windows. The impact of different types of appointments and appointments with different intervals were analyzed. The authors optimize the function of transition-probability-calculating in original ant-colony algorithm, using multiple instances to test the algorithm. The result shows that with replacing manual work, computer and algorithm shapely cut down the time cost of decision-making.
With the Chinese population ageing, home-health-care industrials become more and more important. Characteristics of HHC in China differs from other countries, such as the intensive distribution of senior people, whose residence centralizes in community. This thesis' s problem was based on the field of home health care in huge communities in China, studying how to decline caregivers' moving distance and optimize the daily worksheets. According to three combinations of nurses' skill levels and customers' demands, service time of elders were assumed to obey normal distributions with different mean values and variances so as to analyze the impact from fluctuation of demands on algorithm and decision-making. In real business elders generally make appointments in advance, and appointments are descripted mathematically by time-windows. The impact of different types of appointments and appointments with different intervals were analyzed. The authors optimize the function of transition-probability-calculating in original ant-colony algorithm, using multiple instances to test the algorithm. The result shows that with replacing manual work, computer and algorithm shapely cut down the time cost of decision-making.
引文
[1] Begur S V, Miller D M, Weaver J R. An integrated spatial DSS for scheduling and touting home-health-care nurses[J]. Interfaces, 1997, 27(4):35-48.
[2] Cheng E, Rich J L. A home health care routing and scheduling problem[R]. Rice University, 1998.
[3] Trautsamwieser A, Hirsch P. Optimization of daily scheduling for home health care services[J]. Journal of Applied Operational Research, 2011, 3(3):124-136.
[4] Coppi A, Detti P, Raffaelli J. A planning and routing model for patient transportation in health care[J]. Electronic Notes in Discrete Mathematics, 2013, 41:125-132.
[5] Allaoua H, Borne S, Letocart L, et al. A matheuristic approach for solving a home health care problem[J].Electronic Notes in Discrete Mathematics, 2013, 41(41):471-478.
[6] Kergosien Y, Lente C, Billaut J C. Home health care problem:An extended multiple Traveling Salesman Problem[C]//Proceedings of the 4th Multidisciplinary International Scheduling Conference:Theory and Applications,2009:85-92.
[7] Gayraud F, Deroussi L, Grangeon N, et al. A new mathematical formulation for the home health care problem[J].Procedia Technology, 2013, 9:1041-1047.
[8] Eveborn P, Flisberg P, Ronnqvist M. LAPS CARE—An operational system for staff planning of home care[J].European Journal of Operational Research, 2006, 171(3):962-976.
[9] Hertz A, Lahrichi N. A patient assignment algorithm for home care services[J]. Journal of the Operational Research Society, 2009, 60(4):481-495.
[10] Bertels S, Fahle T. A hybrid setup for a hybrid scenario:Combining heuristics for the home health care problem[J].Computers&Operations Research, 2006, 33(10):2866-2890.
[11] Fikar C, Hirsch P. Home health care routing and scheduling:A review[J]. Computers&Operations Research,2017, 77:86-95.
[12]张芙蓉.我国社区居家养老服务研究综述[J].黑河学刊,2016(2):182-183.Zhang F R. Community home health care services survey of China[J]. Heihe Journal, 2016(2):182-183.
[13]张波.我国居家养老模式研究综述与展望[J].四川理工学院院报(社会科学版),2013, 28(4):6-10.Zhang B. A review and prospect of the researches on home-care for the aged in China[J]. Journal of Sichuan University of Science&Engineering(Social Sciences Edition), 2013, 28(4):6-10.
[14] Zhan Y, Wang Z, Wan G. Home care routing and appointment scheduling with stochastic service durations[J].Social Science Electronic Publishing, 2015. DOI:10.2139/ssrn.2668769.
[15] Yuan B, Liu R, Jiang Z. A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements[J]. International Journal of Production Research, 2015,53(24):7450-7464.
[16] Liu R, Xie X, Garaix T. Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics[J]. Omega, 2014, 47(3):17-32.
[17] Rasmussen M S. The home care crew scheduling problem:Preference-based visit clustering and temporal dependencies[J]. European Journal of Operational Research, 2012, 219(3):598-610.
[18] Dorigo M, Stiitzle T. Ant colony optimization:Overview and recent advances[M]//Handbook of Metaheuristics,Springer US, 2010:227-263.
[19] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]//European Conference on Artificial Life, Paris, France, 1991:134-142.
[20] Liu R, Xie X, Augusto V, et al. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care[J]. European Journal of Operational Research, 2013, 230(3):475-486.
[21] Steeg J, Schroder M. A hybrid approach to solve the periodic home health care problem[M]//Operations Research Proceedings 2007, Springer Berlin Heidelberg, 2008:297-302.
[22] Cheng C B, Mao C P. A modified ant colony system for solving the travelling salesman problem with time windows[J]. Mathematical&Computer Modelling, 2007, 46(9):1225-1235.
[23] Necula R, Breaban M, Raschip M. Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem[C]//International Conference on Hybrid Artificial Intelligence Systems, 2015:257-268.
[2] Cheng E, Rich J L. A home health care routing and scheduling problem[R]. Rice University, 1998.
[3] Trautsamwieser A, Hirsch P. Optimization of daily scheduling for home health care services[J]. Journal of Applied Operational Research, 2011, 3(3):124-136.
[4] Coppi A, Detti P, Raffaelli J. A planning and routing model for patient transportation in health care[J]. Electronic Notes in Discrete Mathematics, 2013, 41:125-132.
[5] Allaoua H, Borne S, Letocart L, et al. A matheuristic approach for solving a home health care problem[J].Electronic Notes in Discrete Mathematics, 2013, 41(41):471-478.
[6] Kergosien Y, Lente C, Billaut J C. Home health care problem:An extended multiple Traveling Salesman Problem[C]//Proceedings of the 4th Multidisciplinary International Scheduling Conference:Theory and Applications,2009:85-92.
[7] Gayraud F, Deroussi L, Grangeon N, et al. A new mathematical formulation for the home health care problem[J].Procedia Technology, 2013, 9:1041-1047.
[8] Eveborn P, Flisberg P, Ronnqvist M. LAPS CARE—An operational system for staff planning of home care[J].European Journal of Operational Research, 2006, 171(3):962-976.
[9] Hertz A, Lahrichi N. A patient assignment algorithm for home care services[J]. Journal of the Operational Research Society, 2009, 60(4):481-495.
[10] Bertels S, Fahle T. A hybrid setup for a hybrid scenario:Combining heuristics for the home health care problem[J].Computers&Operations Research, 2006, 33(10):2866-2890.
[11] Fikar C, Hirsch P. Home health care routing and scheduling:A review[J]. Computers&Operations Research,2017, 77:86-95.
[12]张芙蓉.我国社区居家养老服务研究综述[J].黑河学刊,2016(2):182-183.Zhang F R. Community home health care services survey of China[J]. Heihe Journal, 2016(2):182-183.
[13]张波.我国居家养老模式研究综述与展望[J].四川理工学院院报(社会科学版),2013, 28(4):6-10.Zhang B. A review and prospect of the researches on home-care for the aged in China[J]. Journal of Sichuan University of Science&Engineering(Social Sciences Edition), 2013, 28(4):6-10.
[14] Zhan Y, Wang Z, Wan G. Home care routing and appointment scheduling with stochastic service durations[J].Social Science Electronic Publishing, 2015. DOI:10.2139/ssrn.2668769.
[15] Yuan B, Liu R, Jiang Z. A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements[J]. International Journal of Production Research, 2015,53(24):7450-7464.
[16] Liu R, Xie X, Garaix T. Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics[J]. Omega, 2014, 47(3):17-32.
[17] Rasmussen M S. The home care crew scheduling problem:Preference-based visit clustering and temporal dependencies[J]. European Journal of Operational Research, 2012, 219(3):598-610.
[18] Dorigo M, Stiitzle T. Ant colony optimization:Overview and recent advances[M]//Handbook of Metaheuristics,Springer US, 2010:227-263.
[19] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[C]//European Conference on Artificial Life, Paris, France, 1991:134-142.
[20] Liu R, Xie X, Augusto V, et al. Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care[J]. European Journal of Operational Research, 2013, 230(3):475-486.
[21] Steeg J, Schroder M. A hybrid approach to solve the periodic home health care problem[M]//Operations Research Proceedings 2007, Springer Berlin Heidelberg, 2008:297-302.
[22] Cheng C B, Mao C P. A modified ant colony system for solving the travelling salesman problem with time windows[J]. Mathematical&Computer Modelling, 2007, 46(9):1225-1235.
[23] Necula R, Breaban M, Raschip M. Performance evaluation of ant colony systems for the single-depot multiple traveling salesman problem[C]//International Conference on Hybrid Artificial Intelligence Systems, 2015:257-268.