A literature review on Home Healthcare Routing and Scheduling Problem

Abstract

The Home Healthcare Routing and Scheduling Problem (HHCRSP) involves some of the features of vehicle routing and nurse rostering problem. Home healthcare is a part of health services, which can be defined as providing the necessary services to the patients and their families within their familiar environments. Some of the issues such as aging population, increasing diseases, shortage of workforce, economic reasons, innovation in medical technologies, preferences etc. increase the importance and the need of Home healthcare. Furthermore, solution procedures for these routing and scheduling problems are varied according to the assumptions. In this review, the most common characteristics of the problem and an overview of recent works related to the HHCRSP are discussed.

Keywords

• Literature review,Home healthcare

References

1. Akjiratikarl, C., Yenradee, P., & Drake, P. R. (2007). PSO-based algorithm for home care worker scheduling in the UK. Computers & Industrial Engineering, 53(4), 559-583. doi:10.1016/j.cie.2007.06.002
2. Allaoua, H., Borne, S., Létocart, L., & Wolfler Calvo, R. (2013). A matheuristic approach for solving a home health care problem. Electronic Notes in Discrete Mathematics, 41, 471-478. doi:10.1016/j.endm.2013.05.127
3. Bachouch, R. B., Guinet, A., & Hajri-Gabouj, S. (2011). A Decision-Making Tool for Home Health Care Nurses’ Planning. Supply Chain Forum: An International Journal, 12(1), 14-20. doi:10.1080/16258312.2011.11517250
4. Bard, J. F., Shao, Y., & Jarrah, A. I. (2014). A sequential GRASP for the therapist routing and scheduling problem. Journal of Scheduling, 17(2), 109-133. doi:10.1007/s10951-013-0345-x
5. Bard, J. F., Shao, Y., Qi, X., & Jarrah, A. I. (2014). The traveling therapist scheduling problem. IIE Transactions, 46(7), 683-706. doi:10.1080/0740817X.2013.851434
6. Barrera, D., Velasco, N., & Amaya, C. A. (2012). A network-based approach to the multi-activity combined timetabling and crew scheduling problem: Workforce scheduling for public health policy implementation. Computers & Industrial Engineering, 63(4), 802-812. doi:http://dx.doi.org/10.1016/j.cie.2012.05.002
7. Begur, S. V., Miller, D. M., & Weaver, J. R. (1997). An Integrated Spatial DSS for Scheduling and Routing Home-Health-Care Nurses. Interfaces, 27(4), 35-48. doi:doi:10.1287/inte.27.4.35
8. Bennett-Milburn, A., & Spicer, J. (2013). Multi-objective home health nurse routing with remote monitoring devices. Int J Plan Sched, 1(4), 242-263.

9. Bennett, A. R., & Erera, A. L. (2011). Dynamic periodic fixed appointment scheduling for home health. IIE Transactions on Healthcare Systems Engineering, 1(1), 6-19. doi:10.1080/19488300.2010.549818
10. Bertels, S., & Fahle, T. (2006). A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Computers & Operations Research, 33(10), 2866-2890. doi:http://dx.doi.org/10.1016/j.cor.2005.01.015
11. Borsani, V., Matta, A., Beschi, G., & Sommaruga, F. (2006, Oct. 2006). A Home Care Scheduling Model For Human Resources. Paper presented at the 2006 International Conference on Service Systems and Service Management.
12. Bowers, J., Cheyne, H., Mould, G., & Page, M. (2015). Continuity of care in community midwifery. Health Care Management Science, 18(2), 195-204. doi:10.1007/s10729-014-9285-z
13. Braekers, K., Hartl, R. F., Parragh, S. N., & Tricoire, F. (2016). A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience. European Journal of Operational Research, 248(2), 428-443. doi:http://dx.doi.org/10.1016/j.ejor.2015.07.028
14. Bräysy, O., Dullaert, W., & Nakari, P. (2009). The potential of optimization in communal routing problems: case studies from Finland. Journal of Transport Geography, 17(6), 484-490. doi:http://dx.doi.org/10.1016/j.jtrangeo.2008.10.003
15. Bräysy, O., & Gendreau, M. (2005a). Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms. Transportation Science, 39(1), 104-118. doi:10.1287/trsc.1030.0056
16. Bräysy, O., & Gendreau, M. (2005b). Vehicle Routing Problem with Time Windows, Part II: Metaheuristics. Transportation Science, 39(1), 119-139. doi:10.1287/trsc.1030.0057
17. Bredström, D., & Rönnqvist, M. (2008). Combined vehicle routing and scheduling with temporal precedence and synchronization constraints. European Journal of Operational Research, 191(1), 19-31. doi:10.1016/j.ejor.2007.07.033
18. Cappanera, P., & Scutellà, M. G. (2013). Home Care optimization: impact of pattern generation policies on scheduling and routing decisions. Electronic Notes in Discrete Mathematics, 41, 53-60. doi:10.1016/j.endm.2013.05.075
19. Cappanera, P., & Scutellà, M. G. (2015). Joint Assignment, Scheduling, and Routing Models to Home Care Optimization: A Pattern-Based Approach. Transportation Science, 49(4), 830-852. doi:doi:10.1287/trsc.2014.0548
20. Carello, G., & Lanzarone, E. (2014). A cardinality-constrained robust model for the assignment problem in Home Care services. European Journal of Operational Research, 236(2), 748-762. doi:http://dx.doi.org/10.1016/j.ejor.2014.01.009
21. Castillo-Salazar, J. A., Landa-Silva, D., & Qu, R. (2014). Workforce scheduling and routing problems: literature survey and computational study. Annals of Operations Research, 1-29. doi:10.1007/s10479-014-1687-2
22. Cattafi, M., Herrero, R., Gavanelli, M., Nonato, M., Malucelli, F., & Ramos, J. J. (2012). Improving Quality and Efficiency in Home Health Care: an application of Constraint Logic Programming for the Ferrara NHS unit. Paper presented at the Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). http://drops.dagstuhl.de/opus/volltexte/2012/3641/
23. CDC. (2017). Home Health Care. Retrieved from https://www.cdc.gov/nchs/fastats/home-health-care.htm
24. Cheng, E., & Rich, J. L. (1998). A home health care routing and scheduling problem.
25. Cissé, M., Yalçındağ, S., Kergosien, Y., Şahin, E., Lenté, C., & Matta, A. (2017). OR problems related to Home Health Care: A review of relevant routing and scheduling problems. Operations Research for Health Care. doi:http://dx.doi.org/10.1016/j.orhc.2017.06.001
26. Colombo, F., ., & et al. Help Wanted? : OECD Publishing.
27. Coppi, A., Detti, P., & Raffaelli, J. (2013). A planning and routing model for patient transportation in health care. Electronic Notes in Discrete Mathematics, 41, 125-132. doi:10.1016/j.endm.2013.05.084
28. De Angelis, V. (1998). Planning Home Assistance for AIDS Patients in the City of Rome, Italy. Interfaces, 28(3), 75-83. doi:doi:10.1287/inte.28.3.75
29. Di Gaspero, L., & Urli, T. (2014). A CP/LNS Approach for Multi-day Homecare Scheduling Problems. In M. Blesa, et al. (Eds.), Hybrid Metaheuristics (Vol. 8457, pp. 1-15): Springer International Publishing.
30. Di Mascolo, M., Espinouse, M.-L., & Ozkan, C. E. (2014). Synchronization Between Human Resources in Home Health Care Context. In A. Matta, et al. (Eds.), Proceedings of the International Conference on Health Care Systems Engineering (pp. 73-86). Cham: Springer International Publishing.
31. Dohn, A., Kolind, E., & Clausen, J. (2009). The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Computers & Operations Research, 36(4), 1145-1157. doi:http://dx.doi.org/10.1016/j.cor.2007.12.011
32. Elbenania, B., Ferland, J. A., & Gascon, V. (2008). Mathematical Programming Approach for Routing Home Care Nurses. Paper presented at the Industrial Engineering and Engineering Management, 2008. IEEM 2008.
33. Ellenbecker, C. H., Samia, L., Cushman, M. J., & Alster, K. (2008). Chapter 13-Patient Safety and Quality in Home Health Care. In R. G. Hughes (Ed.), Patient Safety and Quality: An Evidence-Based Handbook for Nurses. Rockville Agency for Healthcare Research and Quality.
34. Erdem, M., & Bulkan, S. (2017). A Two-Stage Solution Approach For The Large-Scale Home Healthcare Routing And Scheduling Problem. The South African Journal of Industrial Engineering, 28 (4), xxx-xxx.
35. Eurostat. (2017). Population structure and ageing Retrieved from http://ec.europa.eu/eurostat/statistics-explained/index.php/Population_structure_and_ageing
36. Eveborn, P., Flisberg, P., & Rönnqvist, M. (2006). Laps Care—an operational system for staff planning of home care. European Journal of Operational Research, 171(3), 962-976. doi:10.1016/j.ejor.2005.01.011
37. Fernandez, A., Gregory, G., Hindle, A., & Lee, C. A. (1974). A Model for Community Nursing in a Rural County. Journal of the Operational Research Society, 25(2), 231-239. doi:10.1057/jors.1974.40
38. Fikar, C., & Hirsch, P. (2015). A matheuristic for routing real-world home service transport systems facilitating walking. Journal of Cleaner Production, 105, 300-310. doi:10.1016/j.jclepro.2014.07.013
39. Fikar, C., & Hirsch, P. (2017). Home health care routing and scheduling: A review. Computers & Operations Research, 77, 86-95. doi:http://dx.doi.org/10.1016/j.cor.2016.07.019
40. Gamst, M., & Jensen, T. S. (2012). A branch-and-price algorithm for the long-term home care scheduling problem. In D. Klatte, et al. (Eds.), Operations Research Proceedings 2011 (pp. 483-488): Springer Berlin Heidelberg.
41. Hertz, A., & Lahrichi, N. (2009). A patient assignment algorithm for home care services. Journal of the Operational Research Society, 60(4), 481-495. doi:10.1057/palgrave.jors.2602574
42. Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., & Raidl, G. (2015). Metaheuristics for solving a multimodal home-healthcare scheduling problem. Central European Journal of Operations Research, 23(1), 89-113. doi:10.1007/s10100-013-0305-8
43. Hindle, T., Hindle, A., & Spollen, M. (2000). Resource Allocation Modelling for Home-Based Health and Social Care Services in Areas Having Differential Population Density Levels: A Case Study in Northern Ireland Health Serv Manage Res, 13(3), 164-169. doi:10.1177/095148480001300304
44. Hindle, T., Hindle, G., & Spollen, M. (2009). Travel-related costs of population dispersion in the provision of domiciliary care to the elderly: a case study in English Local Authorities Health Serv Manage Res, 22(1), 27-32. doi:10.1258/hsmr.2008.008012
45. Issaoui, B., Zidi, I., Marcon, E., & Ghedira, K. (2015). New Multi-Objective Approach for the Home Care Service Problem Based on Scheduling Algorithms and Variable Neighborhood Descent. Electronic Notes in Discrete Mathematics, 47, 181-188. doi:10.1016/j.endm.2014.11.024
46. Karabağ, H. (2007). Evde Sağlik Bakim Hizmetlerinin Türkiye’de Uygulanabilirliğine İlişkin Hekimlerin Görüşleri Ve Kardiyoloji Hastalari İçin Hastane Destekli Evde Bakim Hizmetleri Modeli Önerisi. (Master Thesis), Gazi University, Ankara.
47. Kergosien, Y., Lenté, C., & Billaut, J.-C. (2009). Home health care problem: An extended multiple Traveling Salesman Problem. Paper presented at the Proceedings of the 4th Multidisciplinary International Scheduling Conference: Theory and Applications (MISTA 2009), Dublin, Ireland.
48. Kergosien, Y., Ruiz, A., & Soriano, P. (2014). A Routing Problem for Medical Test Sample Collection in Home Health Care Services. In A. Matta, et al. (Eds.), Proceedings of the International Conference on Health Care Systems Engineering (pp. 29-46). Cham: Springer International Publishing.
49. Koeleman, P. M., Bhulai, S., & van Meersbergen, M. (2012). Optimal patient and personnel scheduling policies for care-at-home service facilities. European Journal of Operational Research, 219(3), 557-563. doi:10.1016/j.ejor.2011.10.046
50. Lanzarone, E., & Matta, A. (2014). Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care. Operations Research for Health Care, 3(2), 48-58. doi:http://dx.doi.org/10.1016/j.orhc.2014.01.003
51. Liu, R., Xie, X., Augusto, V., & Rodriguez, C. (2013). Heuristic algorithms for a vehicle routing problem with simultaneous delivery and pickup and time windows in home health care. European Journal of Operational Research, 230(3), 475-486. doi:10.1016/j.ejor.2013.04.044
52. Mankowska, D. S., Meisel, F., & Bierwirth, C. (2014). The home health care routing and scheduling problem with interdependent services. Health Care Management Science, 17(1), 15-30. doi:10.1007/s10729-013-9243-1
53. Marak, C. (2016). Benefits of Home Care. Retrieved from http://www.homehealthcareagencies.com/resources/benefits-of-home-care/
54. Matta, A., Chahed, S., Sahin, E., & Dallery, Y. (2014). Modelling home care organisations from an operations management perspective. Flexible Services and Manufacturing Journal, 26(3), 295-319. doi:10.1007/s10696-012-9157-0
55. Maya Duque, P. A., Castro, M., Sörensen, K., & Goos, P. (2015). Home care service planning. The case of Landelijke Thuiszorg. European Journal of Operational Research, 243(1), 292-301. doi:10.1016/j.ejor.2014.11.008
56. Medicine, U. S. N. L. o. (2017). Home Care Services Retrieved from https://medlineplus.gov/homecareservices.html
57. Milburn, A. B. (2012). Operations Research Applications in Home Healthcare. In R. Hall (Ed.), Handbook of Healthcare System Scheduling (pp. 281-302). Boston, MA: Springer US.
58. Mısır, M., Smet, P., & Vanden Berghe, G. (2015). An analysis of generalised heuristics for vehicle routing and personnel rostering problems. Journal of the Operational Research Society, 66(5), 858-870. doi:10.1057/jors.2014.11
59. Misir, M., Verbeeck, K., De Causmaecker, P., & Berghe, G. V. (2010, 18-23 July 2010). Hyper-heuristics with a dynamic heuristic set for the home care scheduling problem. Paper presented at the Evolutionary Computation (CEC), 2010 IEEE Congress on.
60. Mutingi, M., & Mbohwa, C. (2014). Home Healthcare Staff Scheduling: A Clustering Particle Swarm Optimization Approach. Paper presented at the International Conference on Industrial Engineering and Operations Management, Bali, Indonesia,.
61. Nickel, S., Schröder, M., & Steeg, J. (2012). Mid-term and short-term planning support for home health care services. European Journal of Operational Research, 219(3), 574-587. doi:10.1016/j.ejor.2011.10.042
62. Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1-11. doi:https://doi.org/10.1016/j.ejor.2012.08.015
63. R&M. (2017). Europe Home Healthcare and Residential Nursing Care Services Market Report 2017. Retrieved from https://www.researchandmarkets.com/research/xjwcsf/europe_home
64. Ramos, A. F. T., Lizarazo, E. H. A.-., Rubiano, L. S. R.-., & Araújo, C. L. Q. (2014). Mathematical Model for the Home Health Care routing and scheduling problem with multiple treatment and time windows. Paper presented at the Mathematical Methods in Science and Engineering, Athens.
65. Rasmussen, M. S., Justesen, T., Dohn, A., & Larsen, J. (2012). The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies. European Journal of Operational Research, 219(3), 598-610. doi:10.1016/j.ejor.2011.10.048
66. Redjem, R., Kharraja, S., & Marcon, E. (2011). Collaborative model for planning and scheduling caregivers’ activities in homecare. IFAC World Congress, Volume 18, 2877-2882. doi:10.3182/20110828-6-IT-1002.01043
67. Redjem, R., & Marcon, E. (2016). Operations management in the home care services: a heuristic for the caregivers’ routing problem. Flexible Services and Manufacturing Journal, 28(1), 280-303. doi:10.1007/s10696-015-9220-8
68. Rendl, A., Prandtstetter, M., Hiermann, G., Puchinger, J., & Raidl, G. (2012). Hybrid Heuristics for Multimodal Homecare Scheduling. In N. Beldiceanu, et al. (Eds.), Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems (Vol. 7298, pp. 339-355): Springer Berlin Heidelberg.
69. Rest, K.-D., & Hirsch, P. (2016). Daily scheduling of home health care services using time-dependent public transport. Flexible Services and Manufacturing Journal, 28(3), 495-525. doi:10.1007/s10696-015-9227-1
70. Rodriguez, C., Garaix, T., Xie, X., & Augusto, V. (2015). Staff dimensioning in homecare services with uncertain demands. International Journal of Production Research, 53(24), 7396-7410. doi:10.1080/00207543.2015.1081427
71. Shao, Y., Bard, J. F., & Jarrah, A. I. (2012). The therapist routing and scheduling problem. IIE Transactions, 44(10), 868-893. doi:10.1080/0740817X.2012.665202
72. Statista. (2015). Number of home health agencies in the U.S. 1967-2015. Retrieved from https://www.statista.com/statistics/195318/number-of-medicare-home-health-agencies-in-the-us/
73. Steeg, J., & Schröder, M. (2008). A Hybrid Approach to Solve the Periodic Home Health Care Problem. In J. Kalcsics & S. Nickel (Eds.), Operations Research Proceedings 2007 (Vol. 2007, pp. 297-302): Springer Berlin Heidelberg.
74. Trautsamwieser, A., Gronalt, M., & Hirsch, P. (2011). Securing home health care in times of natural disasters. OR Spectrum, 33(3), 787-813. doi:10.1007/s00291-011-0253-4
75. Trautsamwieser, A., & Hirsch, P. (2011). Optimization of daily scheduling for home health care services. Journal of Applied Operational Research, 3, 124-136.
76. Trautsamwieser, A., & Hirsch, P. (2014). A Branch-Price-and-Cut approach for solving the medium-term home health care planning problem. Networks, 64(3), 143-159. doi:10.1002/net.21566
77. UK. (2017). Overtime: your rights. Retrieved from https://www.gov.uk/overtime-your-rights.
78. UN. (2015). World Population Ageing 2015 Retrieved from http://www.un.org/en/development/desa/population/publications/pdf/ageing/WPA2015_Report.pdf
79. Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). Heuristics for multi-attribute vehicle routing problems: A survey and synthesis. European Journal of Operational Research, 231(1), 1-21. doi:https://doi.org/10.1016/j.ejor.2013.02.053
80. Wirnitzer, J., Heckmann, I., Meyer, A., & Nickel, S. (2016). Patient-based nurse rostering in home care. Operations Research for Health Care, 8, 91-102. doi:http://dx.doi.org/10.1016/j.orhc.2015.08.005
81. Yalçındağ, S., Cappanera, P., Grazia Scutellà, M., Şahin, E., & Matta, A. (2016). Pattern-based decompositions for human resource planning in home health care services. Computers & Operations Research, 73, 12-26. doi:http://dx.doi.org/10.1016/j.cor.2016.02.011
82. Yalçındağ, S., Matta, A., Şahin, E., & Shanthikumar, J. G. (2016). The patient assignment problem in home health care: using a data-driven method to estimate the travel times of care givers. Flexible Services and Manufacturing Journal, 28(1), 304-335. doi:10.1007/s10696-015-9222-6
83. Yuan, B., Liu, R., & Jiang, Z. (2015). A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements. International Journal of Production Research, 53(24), 7450-7464. doi:10.1080/00207543.2015.1082041
84. Yuan, Z., & Fügenschuh, A. (2015). Home Health Care Scheduling A Case Study. Paper presented at the MISTA.