Abstract
The home health care routing and scheduling problem (HHCRSP) is an extension of the vehicle routing problem with time windows (VRPTW). It consists of providing services operations at patients’ homes in case of aging or disabling disease. In this paper, we address the HHCRSP with multiple availability periods of patients, which are considered as soft/flexible time windows. A mathematical model is proposed to define a daily planning by minimizing the total penalized earliness and tardiness of service operations, and caregivers’ total waiting time. Taking into account requested services of patients, qualifications and time windows of caregivers, patients’ preferences expressed as multiple availability periods. The model is implemented and tested using CPLEX IBM. To deal with large instances a general variable neighborhood search (GVNS) based heuristic is proposed, implemented and tested using the language C++. Computational results show that the proposed heuristic could find a good solution in a very short computational time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Akjiratikarl, C., Yenradee, P., Drake, P.R.: Pso-based algorithm for home care worker scheduling in the UK. Comput. Ind. Eng. 53(4), 559–583 (2007)
Bard, J.F., Shao, Y., Jarrah, A.I.: A sequential grasp for the therapist routing and scheduling problem. J. Sched. 17(2), 109–133 (2014)
Belhaiza, S., Hansen, P., Laporte, G.: A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows. Comput. Oper. Res. 52, 269–281 (2014)
Bertels, S., Fahle, T.: A hybrid setup for a hybrid scenario: combining heuristics for the home health care problem. Comput. Oper. Res. 33(10), 2866–2890 (2006)
Bräysy, O., Gendreau, M.: Vehicle routing problem with time windows, Part I: route construction and local search algorithms. Transp. Sci. 39(1), 104–118 (2005)
Burke, E.K., De Causmaecker, P., Berghe, G.V., Van Landeghem, H.: The state of the art of nurse rostering. J. Sched. 7(6), 441–499 (2004)
Cissé, M., Yalçındağ, S., Kergosien, Y., Şahin, E., Lenté, C., Matta, A.: Or problems related to home health care: a review of relevant routing and scheduling problems. Oper. Res. Health Care 13, 1–22 (2017)
Decerle, J., Grunder, O., El Hassani, A.H., Barakat, O.: A memetic algorithm for a home health care routing and scheduling problem. Oper. Res. Health Care 16, 59–71 (2018)
Di Mascolo, M., Espinouse, M.L., El Hajri, Z.: Planning in home health care structures: a literature review. IFAC-PapersOnLine 50(1), 4654–4659 (2017)
Fikar, C., Hirsch, P.: Home health care routing and scheduling: a review. Comput. Oper. Res. 77, 86–95 (2017)
Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533–549 (1986)
Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., Raidl, G.R.: Metaheuristics for solving a multimodal home-healthcare scheduling problem. CEJOR 23(1), 89–113 (2013). https://doi.org/10.1007/s10100-013-0305-8
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–680 (1983)
Liu, R., Yuan, B., Jiang, Z.: Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements. Int. J. Prod. Res. 55(2), 558–575 (2017)
Liu, R., Yuan, B., Jiang, Z.: A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times. Flexible Serv. Manuf. J. 31(4), 989–1011 (2018). https://doi.org/10.1007/s10696-018-9328-8
Mankowska, D.S., Meisel, F., Bierwirth, C.: The home health care routing and scheduling problem with interdependent services. Health Care Manage. Sci. 17(1), 15–30 (2013). https://doi.org/10.1007/s10729-013-9243-1
Mladenović, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097–1100 (1997)
Nickel, S., Schröder, M., Steeg, J.: Mid-term and short-term planning support for home health care services. Eur. J. Oper. Res. 219(3), 574–587 (2012)
Rasmussen, M.S., Justesen, T., Dohn, A., Larsen, J.: The home care crew scheduling problem: preference-based visit clustering and temporal dependencies. Eur. J. Oper. Res. 219(3), 598–610 (2012)
Redjem, R., Marcon, E.: Operations management in the home care services: a heuristic for the caregivers’ routing problem. Flex. Serv. Manuf. J. 28(1–2), 280–303 (2016)
Rest, K.-D., Hirsch, P.: Daily scheduling of home health care services using time-dependent public transport. Flex. Serv. Manuf. J. 28(3), 495–525 (2015). https://doi.org/10.1007/s10696-015-9227-1
Shi, Y., Boudouh, T., Grunder, O.: A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transp. Res. Part E: Logist. Transp. Rev. 128, 52–95 (2019)
Solomon, M.M., Desrosiers, J.: Survey paper–time window constrained routing and scheduling problems. Transp. Sci. 22(1), 1–13 (1988). https://doi.org/10.1287/trsc.22.1.1
Trautsamwieser, A., Hirsch, P.: Optimization of daily scheduling for home health care services. J. Appl. Oper. Res. 3(3), 124–136 (2011)
Tricoire, F., Romauch, M., Doerner, K.F., Hartl, R.F.: Heuristics for the multi-period orienteering problem with multiple time windows. Comput. Oper. Res. 37(2), 351–367 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Bazirha, M., Kadrani, A., Benmansour, R. (2020). Daily Scheduling and Routing of Home Health Care with Multiple Availability Periods of Patients. In: Benmansour, R., Sifaleras, A., Mladenović, N. (eds) Variable Neighborhood Search. ICVNS 2019. Lecture Notes in Computer Science(), vol 12010. Springer, Cham. https://doi.org/10.1007/978-3-030-44932-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-44932-2_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-44931-5
Online ISBN: 978-3-030-44932-2
eBook Packages: Computer ScienceComputer Science (R0)