Home Health Care Scheduling and Routing with Temporal Dependencies and Continuity of Care

Document Type : Research Paper


Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran


Due to facing an acute shortage of beds in hospitals, the danger of getting involved in hospital infections and high-cost hospitals care, the Home Health Care industry has encountered high demands in recent years. Different stakeholders with various interests are involved in home health care that makes the process of planning and scheduling of nurses, who offered services, challenging. This paper, therefore, focuses on scheduling and routing nurses traveled to the patient’s home by considering the main features of the problem such as Continuity of Care and temporal dependencies. A new formulation for adjusting the time distance between two consecutive jobs performed by a nurse is presented. A feasible solution has to consider nurse and patient’s preferences, time windows for jobs, nurse’s qualification, and waiting time. A genetic algorithm is proposed to solve the problem. The computational results show the efficiency of the proposed algorithm, especially for large-size instances. Finally, the effect of the nurse’s dispatching policy on the objective function, waiting, and traveling times is examined.


                [1]        Tarricone, R., and Tsours, A. D. (2008). The solid facts: Home care in Europa. Milan: World Health Organization.
                [2]        Fikar, C., & Hirsch, P. (2017). Home health care routing and scheduling: A review. Computers & Operations Research, 77, 86-95.
                [3]        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, 13, 1-22
                [4]        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.
                [5]        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.
                [6]        Trautsamwieser, A., Gronalt, M., & Hirsch, P. (2011). Securing home health care in times of natural disasters. OR spectrum, 33(3), 787-813.
                [7]        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.
                [8]        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.
                [9]        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.
              [10]      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.
              [11]      Liu, R., Yuan, B., & Jiang, Z. (2017). Mathematical model and exact algorithm for the home care worker scheduling and routing problem with lunch break requirements. International Journal of Production Research, 55(2), 558-575.
              [12]      Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., & Raidl, G. R. (2015). Metaheuristics for solving a multimodal home-healthcare scheduling problem. Central European Journal of Operations Research, 23(1), 89-113.
              [13]      Decerle, J., Grunder, O., El Hassani, A. H., & Barakat, O. (2018). A memetic algorithm for a home health care routing and scheduling problem. Operations research for health care, 16, 59-71.
              [14]      Fikar, C., & Hirsch, P. (2015). A matheuristic for routing real-world home service transport systems facilitating walking. Journal of Cleaner Production, 105, 300-310.
              [15]      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.
              [16]      Decerle, J., Grunder, O., El Hassani, A. H., & Barakat, O. (2019). A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window, synchronization and working time balancing. Swarm and Evolutionary Computation, 46, 171-183.
              [17]      Euchi, J., Zidi, S., & Laouamer, L. (2020). A hybrid approach to solve the vehicle routing problem with time windows and synchronized visits in-home health care. Arabian journal for science and engineering, 45(12), 10637-10652.
              [18]      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.
              [19]      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.
              [20]      Cappanera, P., Scutellà, M. G., Nervi, F., & Galli, L. (2018). Demand uncertainty in robust Home Care optimization. Omega, 80, 95-110.
              [21]      Duque, P. M., 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.
              [22]      Carello, G., and 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.
              [23]      Carello, G., Lanzarone, E., & Mattia, S. (2018). Trade-off between stakeholders’ goals in the home care nurse-to-patient assignment problem. Operations research for health care, 16, 29-40.
              [24]      Grenouilleau, F., Lahrichi, N., & Rousseau, L. M. (2020). New decomposition methods for home care scheduling with predefined visits. Computers & Operations Research, 115, 104855.
              [25]      Drexl, M. (2012). Synchronization in vehicle routing—a survey of VRPs with multiple synchronization constraints. Transportation Science, 46(3), 297-316.
              [26]      Haggerty, J. L., Reid, R. J., Freeman, G. K., Starfield, B. H., Adair, C. E., & McKendry, R. (2003). Continuity of care: a multidisciplinary review. Bmj, 327(7425), 1219-1221.
              [27]      Shi, Y., Boudouh, T., & Grunder, O. (2017). A hybrid genetic algorithm for a home health care routing problem with time window and fuzzy demand. Expert Systems with Applications, 72, 160-176
              [28]      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.
              [29]      Algethami, H., Martínez-Gavara, A., & Landa-Silva, D. (2019). Adaptive multiple crossover genetic algorithm to solve workforce scheduling and routing problem. Journal of Heuristics, 25(4-5), 753-792
              [30]      Algethami, H., Landa-Silva, D., & Martinez-Gavara, A. (2017). Selecting genetic operators to maximise preference satisfaction in a workforce scheduling and routing problem.
              [31]      Sazvar, Z., Mirzapour Al-e-Hashem, S. M. J., Govindan, K., & Bahli, B. (2016). A novel mathematical model for a multi-period, multi-product optimal ordering problem considering expiry dates in a FEFO system. Transportation Research Part E: Logistics and Transportation Review, 93, 232-261.
              [32]      Navazi, F., Sazvar, Z., Tavakoli-moghadam, R. (2021), A sustainable closed-loop location-routing-inventory problem for perishable products, Scientia Iranica. In press.
              [33]      Bachouch, R. B., Guinet, A., and Hajri-Gabouj, S. (2011, January). A decision-making tool for home health care nurses’ planning. In Supply Chain Forum: an International Journal (Vol. 12, No. 1, pp. 14-20). Taylor & Francis.
              [34]      Hertz, A., & Lahrichi, N. (2009). A patient assignment algorithm for home care services. Journal of the Operational Research Society, 60(4), 481-495.
              [35]      Trautsamwieser, A., Gronalt, M., & Hirsch, P. (2011). Securing home health care in times of natural disasters. OR spectrum, 33(3), 787-813.
              [36]      Trautsamwieser, A., & Hirsch, P. (2011). Optimization of daily scheduling for home health care services. Journal of Applied Operational Research, 3(3), 124-136.
              [37]      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.
              [38]      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.
              [39]      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.
              [40]      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.
              [41]      Guericke, D., & Suhl, L. (2017). The home health care problem with working regulations. OR Spectrum, 39(4), 977-1010.
              [42]      Liu, R., Yuan, B., & Jiang, Z. (2018). A branch-and-price algorithm for the home-caregiver scheduling and routing problem with stochastic travel and service times. Flexible Services and Manufacturing Journal, 1-23.
              [43]      Shi, Y., Boudouh, T., Grunder, O., & Wang, D. (2018). Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care. Expert Systems with Applications, 102, 218-233.
              [44]      Du, G., Zheng, L., & Ouyang, X. (2019). Real-time scheduling optimization considering the unexpected events in home health care. Journal of Combinatorial Optimization, 37(1), 196-220.
              [45]      Grenouilleau, F., Legrain, A., Lahrichi, N., & Rousseau, L. M. (2019). A set partitioning heuristic for the home health care routing and scheduling problem. European Journal of Operational Research, 275(1), 295-303.