Multi-period home health care routing and scheduling problem with the medical grouping of patients

Document Type : Article


Department of Industrial Engineering, Amirkabir University of Technology, 424 Hafez Avenue, Tehran, Iran


Home health care service has significant importance in modern societies. In most of the active institutions in this field, the traditional procedure is used for planning and managing health personnel and determining patient visit sequence. This procedure usually causes an increase in costs and reduces patients’ satisfaction. This paper, for the first time, groups the patients in a model according to the level of emergency and discriminating in their examination. Considering dependency and independence of patient visits to each other, assuming multi-depot and multi-period issues are attractive aspects of the proposed model. The model is solved with GAMS software for small scale and two variable neighborhood search algorithm and simulated annealing algorithm are used to solve large scale problems and their performances are compared. The results indicate minimizing total cost and also increasing patients` satisfaction by the proposed model.


  1. References

    1. European Commission. “Europe’s demographic future: Facts and figures on challenges and opportunities”, (2007), ISBN978-92-79-07043-3.
    2. Grenouilleau, F., Legrain, A., Lahrichi, N. et al. “A set partitioning heuristic for the home health care routing and scheduling problem”. European Journal of Operational Research275, pp.295-303 (2019).
    3. Decerle, J., Grunder, O., El Hassani, A.H. et al. “A memetic algorithm for multi-objective optimization of the home health care problem”. Swarm and evolutionary computation44, pp.712-727 (2019).
    4. Di Mascolo, M., Martinez, C. and Espinouse, M.L. “Routing and scheduling in home health care: A literature survey and bibliometric analysis”. Computers & Industrial Engineering, 158, pp.107255 (2021).
    5. Palladino, L. “Public Investment in Home Healthcare in the United States During the COVID-19 Pandemic: A Win-Win Strategy”. Feminist Economics27, pp.436-452 (2021).
    6. Fathollahi-Fard, A.M., Hajiaghaei-Keshteli, M. and Mirjalili, S. “A set of efficient heuristics for a home healthcare problem”. Neural Computing and Applications32, pp.6185-6205 (2020).
    7. Holly, R. “Home Health Agencies Carving Out Bigger Role in US Economy",<> (2020).


    1. Shi, Y., Boudouh, T., Grunder, O. et al. “Modeling and solving simultaneous delivery and pick-up problem with stochastic travel and service times in home health care”. Expert Systems with Applications102, pp.218-233 (2018).
    2. Huang, S.S. and Hirth, R.A. “Quality rating and private-prices: Evidence from the nursing home industry”. Journal of health economics50, pp.59-70 (2016).
    3. Bachouch, R.B., Guinet, A. and Hajri-Gabouj, S. “A decision-making tool for home health care nurses’ planning”. In Supply Chain Forum: An International Journal, 12, pp. 14-20 (2011).
    4. Begur, S.V., Miller, D.M. and Weaver, J.R. “An integrated spatial DSS for scheduling and routing home-health-care nurses”. Interfaces27, pp.35-48 (1997).
    5. Bräysy, O., Gendreau, M., Hasle, G. et al. “A survey of heuristics for the vehicle routing problem part II: Demand side extensions”, Working paper, SINTEF ICT, Norway (2008).
    6. Eveborn, P., Flisberg, P. and Rönnqvist, M. “Laps Care—an operational system for staff planning of home care”. European journal of operational research171,962-976 (2006).
    7. Hindle, T., Hindle, A. and Spollen, M. “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 services management research13, pp.164-169 (2000).
    8. Hindle, T., Hindle, G. and Spollen, M. “Travel-related costs of population dispersion in the provision of domiciliary care to the elderly: a case study in English Local Authorities”. Health services management research22, pp.27-32 (2009).
    9. Braekers, K., Hartl, R.F., Parragh, S.N. et al. “A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience”. European Journal of Operational Research248,428-443 (2016).
    10. Mısır, M., Smet, P. and Vanden Berghe, G. “An analysis of generalised heuristics for vehicle routing and personnel rostering problems”. Journal of the Operational Research Society66, pp.858-870 (2015).
    11. Nickel, S., Schröder, M. and Steeg, J. “Mid-term and short-term planning support for home health care services”. European Journal of Operational Research219, pp.574-587 (2012).
    12. Fernandez, A., Gregory, G., Hindle, A. et al. “A model for community nursing in a rural county”. Journal of the Operational Research Society25, pp.231-239 (1974).
    13. Bredström, D. and Rönnqvist, M. “Combined vehicle routing and scheduling with temporal precedence and synchronization constraints”. European journal of operational research191, pp.19-31 (2008).
    14. Mankowska, D.S., Meisel, F. and Bierwirth, C. “The home health care routing and scheduling problem with interdependent services”. Health care management science17, pp.15-30 (2014).
    15. Dohn, A., Kolind, E. and Clausen, J. “The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach”. Computers & Operations Research36, pp.1145-1157 (2009).
    16. Rasmussen, M.S., Justesen, T., Dohn, A. et al. “The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies”. European Journal of Operational Research219, pp.598-610 (2012).
    17. Nowak, M., Hewitt, M. and Nataraj, N. “Planning strategies for home health care delivery”. Technical report, Loyola University Chicago, Information Systems and Operations Management, (2013).
    18. Hiermann, G., Prandtstetter, M., Rendl, A., et al. “Metaheuristics for solving a multimodal home-healthcare scheduling problem”. Central European Journal of Operations Research23, pp.89-113 (2015).
    19. Cappanera, P., Scutellà, M.G., Nervi, F. et al. “Demand uncertainty in robust Home Care optimization”. Omega80, pp.95-110 (2018).
    20. Liu, M., Yang, D., Su, Q. et al. “Bi-objective approaches for home healthcare medical team planning and scheduling problem”. Computational and Applied Mathematics37, pp.4443-4474 (2018).
    21. Lin, C.C., Hung, L.P., Liu, W.Y. et al. “Jointly rostering, routing, and rerostering for home health care services: A harmony search approach with genetic, saturation, inheritance, and immigrant schemes”. Computers & Industrial Engineering115, pp.151-166 (2018).
    22. Demirbilek, M., Branke, J. and Strauss, A. “Dynamically accepting and scheduling patients for home healthcare”. Health care management science22, pp.140-155 (2019).
    23. Tanoumand, N. and Ünlüyurt, T. “An exact algorithm for the resource constrained home health care vehicle routing problem”. Annals of Operations Research, 304, pp.1-29 (2021).
    24. Fikar, C. and Hirsch, P. “Home health care routing and scheduling: A review”. Computers & Operations Research77, pp.86-95 (2017).
    25. Grieco, L., Utley, M. and Crowe, S. “Operational research applied to decisions in home health care: A systematic literature review”. Journal of the Operational Research Society72,1960-1991 (2021).
    26. Toth, P. and Vigo, D. “Models, relaxations and exact approaches for the capacitated vehicle routing problem”. Discrete Applied Mathematics123, pp.487-512 (2002).
    27. Trautsamwieser, A., Gronalt, M. and Hirsch, P. “Securing home health care in times of natural disasters”. OR spectrum33, pp.787-813 (2011).
    28. Trautsamwieser, A. and Hirsch, P. “Optimization of daily scheduling for home health care services”. Journal of applied operational research3, pp.124-136 (2011).
    29. Clarke, G. and Wright, J.W. “Scheduling of vehicles from a central depot to a number of delivery points”. Operations research12, pp.568-581 (1964).
    30. Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. “Optimization by simulated annealing”. science220, pp.671-680 (1983).