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. 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 Research, 275, 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 Computation, 44, 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, p. 107255 (2021).
5. Palladino, L. "Public investment in home healthcare in the United States during the COVID-19 pandemic: A win-win strategy", Feminist Economics, 27, 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 Applications, 32, pp. 6185-6205 (2020).
7. Holly, R., Home Health Agencies Carving Out Bigger Role in US Economy, < https://homehealthcarenews. com/2020/11/home-health-agencies-carving-outbigger -role-in-us-economy> (2020).
8. 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 Applications, 102, pp. 218- 233 (2018).
9. Huang, S.S. and Hirth, R.A. "Quality rating and private-prices: Evidence from the nursing home industry", Journal of Health Economics, 50, pp. 59-70 (2016).
10. 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).
11. Begur, S.V., Miller, D.M., and Weaver, J.R. "An integrated spatial DSS for scheduling and routing home-health-care nurses", Interfaces, 27, pp. 35-48 (1997).
12. Braysy, 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).
13. Eveborn, P., Flisberg, P., and Ronnqvist, M. "Laps care-an operational system for staff planning of home care", European Journal of Operational Research, 171, pp. 962-976 (2006).
14. 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 Research, 13, pp. 164- 169 (2000).
15. Hindle, T., Hindle, G., and Spollen, M. "Travelrelated costs of population dispersion in the provision of domiciliary care to the elderly: A case study in english local authorities", Health Services Management Research, 22, pp. 27-32 (2009).
16. Braekers, K., Hartl, R.F., Parragh, S.N., et al. "A biobjective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience", European Journal of Operational Research, 248, pp. 428-443 (2016).
17. Misir, M., Smet, P., and Vanden Berghe, G. "An analysis of generalised heuristics for vehicle routing and personnel rostering problems", Journal of the Operational Research Society, 66, pp. 858-870 (2015).
18. Nickel, S., Schroder, M., and Steeg, J. "Mid-term and short-term planning support for home health care services", European Journal of Operational Research, 219, pp. 574-587 (2012).
19. Fernandez, A., Gregory, G., Hindle, A., et al. "A model for community nursing in a rural county", Journal of the Operational Research Society, 25, pp. 231-239 (1974).
20. Bredstrom, D. and Ronnqvist, M. "Combined vehicle routing and scheduling with temporal precedence and synchronization constraints", European Journal of Operational Research, 191, pp. 19-31 (2008).
21. Mankowska, D.S., Meisel, F., and Bierwirth, C. "The home health care routing and scheduling problem with interdependent services", Health Care Management Science, 17, pp. 15-30 (2014).
22. 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 Research, 36, pp. 1145-1157 (2009).
23. 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 Research, 219, pp. 598-610 (2012).
24. 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).
25. Hiermann, G., Prandtstetter, M., Rendl, A., et al. "Metaheuristics for solving a multimodal homehealthcare scheduling problem", Central European Journal of Operations Research, 23, pp. 89-113 (2015).
26. Cappanera, P., Scutella, M.G., Nervi, F., et al. "Demand uncertainty in robust Home Care optimization", Omega, 80, pp. 95-110 (2018).
27. Liu, M., Yang, D., Su, Q., et al. "Bi-objective approaches for home healthcare medical team planning and scheduling problem", Computational and Applied Mathematics, 37, pp. 4443-4474 (2018).
28. 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 Engineering, 115, pp. 151-166 (2018).
29. Demirbilek, M., Branke, J., and Strauss, A. "Dynamically accepting and scheduling patients for home healthcare", Health Care Management Science, 22, pp. 140-155 (2019).
30. Tanoumand, N. and Unluyurt, T. "An exact algorithm for the resource constrained home health care vehicle routing problem", Annals of Operations Research, 304, pp. 1-29 (2021).
31. Fikar, C. and Hirsch, P. "Home health care routing and scheduling: A review", Computers & Operations Research, 77, pp. 86-95 (2017).
32. 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 Society, 72, pp. 1960-1991 (2021).
33. Toth, P. and Vigo, D. "Models, relaxations and exact approaches for the capacitated vehicle routing problem", Discrete Applied Mathematics, 123, pp. 487-512 (2002).
34. Trautsamwieser, A., Gronalt, M., and Hirsch, P. "Securing home health care in times of natural disasters", OR Spectrum, 33, pp. 787-813 (2011).
35. Trautsamwieser, A. and Hirsch, P. "Optimization of daily scheduling for home health care services", Journal of Applied Operational Research, 3, pp. 124-136 (2011).
36. Clarke, G. and Wright, J.W. "Scheduling of vehicles from a central depot to a number of delivery points", Operations Research, 12, pp. 568-581 (1964).
37. Kirkpatrick, S., Gelatt, C.D., and Vecchi, M.P.  Optimization by simulated annealing", Science, 220, pp. 671-680 (1983).