Abstract
Due to the geographically dispersed locations of their clients, home health care providers have to perform a complex routing and scheduling task. Besides the well-researched routing problem, the adherence to legal and organizational working regulations is a basis for application in practice. These requirements are already widely incorporated in the nurse rostering problem for stationary institutions, but also have to be considered while generating routes for home care providers. We introduce new and adapted working regulations to the home health care problem. The mixed-integer formulation is adaptable to the requirements of different providers. Our numerical results show that an exact solution approach is noncompetitive with respect to computing time in most cases. We therefore propose a heuristic approach based on an adaptive large neighborhood search to cope with the complexity of the problem. The numerical results are computed on generated but realistic instances as well as on data sets provided in previous publications. The results show that the heuristic achieves good results in comparison to the mixed-integer program in only a portion of the computation time. Additional to a numerical analysis, we investigate the influence of the working regulations on the solutions which indicates the importance of modeling working regulations. If the regulations are neglected, a high number of violations are caused.
Similar content being viewed by others
Notes
Available online at http://hhc.guericke.org.
The authors thank Patrick Hirsch and Andrea Trautsamwieser for providing their test instances, their help in understanding the data format and especially Patrick Hirsch for discussing details of the problem setting.
References
Ansótegui C, Sellmann M, Tierney K (2009) A gender-based genetic algorithm for the automatic configuration of algorithms. In: Gent IP (ed) Principles and practice of constraint programming—CP 2009. Lecture notes in computer science, vol 5732. Springer, pp 142–157
Bard JF, Shao Y, Jarrah AI (2014) A sequential grasp for the therapist routing and scheduling problem. J Sched 17(2):109–133
Bartodziej P, Derigs U, Vogel U (2010) On the potentials of parallelizing large neighbourhood search for rich vehicle routing problems. In: Blum C, Battiti R (eds) Learning and intelligent optimization. Lecture notes in comput science, vol 6073. Springer, pp 216–219
Bäumelt Z, Šucha P, Hanzálek Z (2010a) An evolutionary algorithm in a multistage approach for an employee rostering problem with a high diversity of shifts. In: McCollum B, Burke EK, White G (eds) PATAT 2010—Proceedings of the 8th international conference on the practice and theory of automated timetabling, pp 97–112
Bäumelt Z, Waszniowski L, Šucha P, Hanzálek Z (2010b) Integrated vehicle routing and rostering for the home health care services. In: Testi A, Tànfani E, Ivaldi E, Carello G, Aringhieri R, Fragnelli v (eds) Proceedings of the XXXVI international orahs conference on operations research for patient centered health care delivery, FrancoAngeli, pp 267–275
Begur SV, Miller DM, Weaver JR (1997) An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces 27(4):35–48
Bennett AR, Erera AL (2011) Dynamic periodic fixed appointment scheduling for home health. IIE Trans Healthc Syst Eng 1(1):6–19
Borsani V, Matta A, Beschi G, Sommaruga F (2006) A home care scheduling model for human resources. In: IEEE 2006 international conference on service systems and service management, vol 1, pp 449–454
Cappanera P, Scutellà MG (2013) Home care optimization: impact of pattern generation policies on scheduling and routing decisions. Electron Notes Discret Math 41:53–60
Cappanera P, Scutellà MG (2014) Joint assignment, scheduling, and routing models to home care optimization: a pattern-based approach. Transp Sci 49(4):830–852
Desaulniers G, Madsen OB, Ropke S (2014) Chapter 5: The vehicle routing problem with time windows. In: Toth P, Vigo D (eds) Vehicle routing. Society for Industrial and Applied Mathematics, Philadelphia, pp 119–159
Di Gaspero L, Urli T (2014) A CP/LNS approach for multi-day homecare scheduling problems. In: Hybrid metaheuristics. Lecture notes in computer science, vol 8457, pp 1–15
European Commission Economic and Financial Affairs (2015) The 2015 ageing report: Economic and Budgetary Projections for the 28 EU Member States (2013–2060), European Economy Main series, vol 3|2015. Publications Office of the European Union, Luxembourg
Gamst M, Sejr Jensen T (2011) A branch-and-price algorithm for the long-term home care scheduling problem. In: Klatte D, Lüthi HJ, Schmedders K (eds) Operations research proceedings. Springer, Berlin, pp 483–488
Grabbe Y, Nolting HD, Loos S, Krämer K (2006) DAK-BGW Gesundsheitsreport 2006 Ambulante Pflege: Arbeitsbedingungen und Gesundheit in ambulanten Pflegediensten. DAK Zentrale and Berufsgenossenschaft für Gesundheitsdienst und Wohlfahrtspflege
Gutiérrez EV, Gutiérrez V, Vidal CJ (2013) Home health care logistics management: framework and research perspectives. Int J Ind Eng Manag 4(3):173–182
International Labour Organization (2012) ILO working conditions laws database. http://www.ilo.org/dyn/travail
Ioannou G, Kritikos M, Prastacos G (2001) A greedy look-ahead heuristic for the vehicle routing problem with time windows. J Oper Res Soc 52(5):523–537
Lanzarone E, Matta A (2014) Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care. Oper Res Health Care 3(2):48–58
Milburn AB (2012) Operations research applications in home healthcare. In: Hall R (ed) Handbook of healthcare system scheduling. International series in operations research and management science, vol 168. Springer, Boston, pp 281–302
Nickel S, Schröder M, Steeg J (2012) Mid-term and short-term planning support for home health care services. Eur J Oper Res 219(3):574–587
Pisinger D, Ropke S (2010) Large neighborhood search. In: Gendreau M, Potvin JY (eds) Handbook of Metaheuristics, International Series in operations research and management, vol 146. Springer, Berlin, pp 399–419
Rest KD, Hirsch P (2015) Supporting urban home health care in daily business and times of disasters. IFAC-PapersOnLine 48(3):686–691
Ropke S, Pisinger D (2006) An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transp Sci 40(4):455–472
Sahin E, Matta A (2014) A contribution to operations management-related issues and models for home care structures. Int J Logist Res Appl 18(4):355–385
Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M, Puget JF (eds) Principles and practice of constraint programming-CP98. Lecture notes in computer scicence, vol 1520. Springer, pp 417–431
Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35(2):254–265
Tarricone R, Tsouros AD (2008) The solid facts: home care in Europe. World Health Organization–Regional Office Europe. http://www.euro.who.int/__data/assets/pdf_file/0005/96467/E91884.pdf
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
Trautsamwieser A, Gronalt M, Hirsch P (2011) Securing home health care in times of natural disasters. OR Spectr 33(3):787–813
Wirnitzer J, Heckmann I, Meyer A, Nickel S (2015) Patient-based nurse rostering in home care. Oper Res Health Care 8:91–102
Yuan Z, Fügenschuh A (2015) Home health care scheduling: A case study. In: Hanzálek Z, Kendall G, McCollum B, Šůcha P (eds) Proceedings of the 7th multidisciplinary international conference on scheduling: theory and applications (MISTA), pp 555–569
Acknowledgements
The authors thank Kevin Tierney for his useful comments on this work and his support using the algorithm configurator GGA and the anonymous reviewers for their valuable comments to improve this publication.
Author information
Authors and Affiliations
Corresponding author
Electronic supplementary material
Below is the link to the electronic supplementary material.
Rights and permissions
About this article
Cite this article
Guericke, D., Suhl, L. The home health care problem with working regulations. OR Spectrum 39, 977–1010 (2017). https://doi.org/10.1007/s00291-017-0481-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00291-017-0481-3