Home healthcare routing and scheduling problem under uncertainty considering patients' preferences and service desirability

Document Type : Article


Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran


Home Health Care (HHC) is characterized as preparing medical and paramedical services for patients at their place of residence. In the HHC industry, it is imperative for decision-makers to appoint nurses to patients and plan visiting patterns to confront with conflicting objectives and boost service quality. This study offers important insights into Home Health Care Routing and Scheduling Problem (HHCRSP) by dealing with three patient-oriented objectives. Moreover, the proposed model accounts for real-life constraints such as emergency patients, nurses’ proficiency and patients’ preferences. Owing to the multi-objective nature of the model, the Augmented Epsilon Constraint approach and Fuzzy Goal Programming are used for trading off the objectives. Further, getting as close as possible to the real-world problems, some parameters are considered uncertain and consequently a robust approach along with three dissimilar uncertainty sets are used to control uncertainty. Numerical results demonstrate that, regardless of the type of the uncertainty set, increasing control parameters make objective values farther than ideal ones, and the comparison performed among the sets also highlights the stringency of the Box space. A unique indicator, presented to validate the robust approaches, features all sets are almost the same in terms of equal optimality and feasibility criteria.


1. Mankowska, D.S., Meisel, F., and Bierwirth, C. "The home health care routing and scheduling problem with interdependent services", Health Care Manag. Sci., 17(1), pp. 15-30 (Mar. 2014). DOI: 10.1007/s10729-013-9243-1.
2. Super, N. "Who will be there to give care? The growing gap between caregiver supply and demand", Natl. Heal. Policy Forum Georg. Washingt. Univ. Washington, DC (2002).
3. Lindahl, B., Liden, E., and Lindblad, B.M. "A meta-synthesis describing the relationships between patients, informal caregivers and health professionals in home-care settings", J. Clin. Nurs., 20(3-4), pp. 454-463 (2011). DOI: https://doi.org/10.1111/j.1365- 2702.2009.03008.x.
4. Hariz, H.A., Donmez, C.C ., and Sennaroglu, B. "Siting of a central healthcare waste incinerator using GIS-based multi-criteria decision analysis", J. Clean. Prod., 166, pp. 1031-1042 (2017). DOI: https://doi.org/10.1016/j.jclepro.2017.08.091.
5. Matta, A., Chahed, S., Sahin, E., et al. "Modelling home care organisations from an operations management perspective", Flex. Serv. Manuf. J., 26, pp. 295- 319 (Aug. 2012). DOI : 10.1007/s10696-012-9157-0.
6. NAHC, Home Care Profit Margins Update. Washington, DC: National Association for Home Care & Hospice (2006).
7. Fernandez, A., Gregory, G., Hindle, A., et al. "A model for community nursing in a rural county", Oper. Res. Q., 25(2), pp. 231-239 (Jun. 1974). DOI: 10.1057/jors.1974.40.
8. Rasmussen, M.S., Justesen, T., Dohn, A., et al. "The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies", Eur. J. Oper. Res., 219(3), pp. 598-610 (Jun. 2012). DOI: 10.1016/j.ejor.2011.10.048.
9. Fikar, C. and Hirsch, P. "Home health care routing and scheduling: A review", Comput. Oper. Res., 77, pp. 86-95 (2017). DOI: 10.1016/j.cor.2016.07.019.
10. Hiermann, G., Prandtstetter, M., Rendl, A., et al. "Metaheuristics for solving a multimodal homehealthcare scheduling problem", Cent. Eur. J. Oper. Res., 23(1), pp. 89-113 (Mar. 2015). DOI: 10.1007/s10100-013-0305-8.
11. Allaoua, H., Borne, S., Letocart, L., et al. "A matheuristic approach for solving a home health care problem", Electron. Notes Discret. Math., 41, pp. 471-478 (Jun. 2013). DOI: 10.1016/j.endm.2013.05.127.
12. Dohn, A., Kolind, E., and Clausen, J. "The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach", Comput. Oper. Res., 36(4), pp. 1145-1157 (Apr. 2009). DOI: 10.1016/j.cor.2007.12.011.
13. Mutingi, M. and Mbohwa, C. "Multi-objective homecare worker scheduling: A fuzzy simulated evolution algorithm approach", IIE Trans. Healthc. Syst. Eng., 4(4), pp. 209-216 (Oct. 2014). DOI: 10.1080/19488300.2014.966213.
14. Trautsamwieser, A., Gronalt, M., and Hirsch, P. "Securing home health care in times of natural disasters", OR Spectr., 33(3), pp. 787-813 (Jul. 2011). DOI: 10.1007/s00291-011-0253-4.
15. Trautsamwieser, A. and Hirsch, P. "Optimization of daily scheduling for home health care services", J. Appl. Oper. Res., 3(3), pp. 124-136 (2011).
16. Bertels, S. and Fahle, T. "A hybrid setup for a hybrid scenario: Combining heuristics for the home health care problem", Comput. Oper. Res., 33(10), pp. 2866- 2890 (Oct. 2006). DOI: 10.1016/j.cor.2005.01.015.
17. Eveborn, P., Flisberg, P., and Ronnqvist, M. "Laps Care-an operational system for staff planning of home care", In European Journal of Operational Research, 171(3), pp. 962-976 (Jun. 2006). DOI: 10.1016/j.ejor.2005.01.011.
18. Fikar, C. and Hirsch, P. "A matheuristic for routing real-world home service transport systems facilitating walking", J. Clean. Prod., 105, pp. 300-310 (Oct. 2015). DOI: 10.1016/j.jclepro.2014.07.013.
19. Bard, J.F., Shao, Y., Qi, X., et al. "The traveling therapist scheduling problem", IIE Trans. Institute Ind. Eng., 46(7), pp. 683-706 (Jul. 2014). DOI: 10.1080/0740817X.2013.851434.
20. Riazi, S., Wigstrom, O., Bengtsson, K., et al. "A column generation-based gossip algorithm for home healthcare routing and scheduling problems", IEEE Trans. Autom. Sci. Eng., 16(1), pp. 127|137 (Jan. 2019). DOI: 10.1109/TASE.2018.2874392.
21. Misir, M., Smet, P., and Vanden Berghe, G. "An analysis of generalised heuristics for vehicle routing and personnel rostering problems", J. Oper. Res. Soc., 66(5), pp. 858-870 (May 2015). DOI: 10.1057/jors.2014.11.
22. Shi, Y., Boudouh, T., and 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, pp. 52-95 (Aug. 2019). DOI: 10.1016/j.tre.2019.05.015.
23. 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", Eur. J. Oper. Res., 248(2), pp. 428-443 (2016). DOI: 10.1016/j.ejor.2015.07.028.
24. Nickel, S., Schroder, M., and Steeg, J. "Mid-term and short-term planning support for home health care services", Eur. J. Oper. Res., 219(3), pp. 574-587 (Jun. 2012). DOI: 10.1016/j.ejor.2011.10.042.
25. Decerle, J., Grunder, O., Hajjam El Hassani, A., et al. "A hybrid memetic-ant colony optimization algorithm for the home health care problem with time window, synchronization and working time balancing", Swarm Evol. Comput., 46, pp. 171-183 (May 2019). DOI: 10.1016/j.swevo.2019.02.009.
26. Liu, R., Tao, Y., and Xie, X. "An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits", Comput. Oper. Res., 101, pp. 250-262 (Jan. 2019). DOI: 10.1016/j.cor.2018.08.002.
27. Ben Bachouch, R., Guinet, A., and Hajri-Gabouj, S. "A decision-making tool for home health care nurses' planning", Supply Chain Forum An Int. J., 12(1), pp. 14-20 (Jan. 2011). DOI: 10.1080/16258312.2011.11517250.
28. Shao, Y., Bard, J.F., and Jarrah, A.I "The therapist routing and scheduling problem", IIE Trans., 44(10), pp. 868-893 (Oct. 2012). DOI: 10.1080/0740817X. 2012.665202.
29. Kallehauge, B., Larsen, J., Madsen, O.B.G., et al., Vehicle Routing Problem with Time Windows, In Column Generation, New York: Springer-Verlag, pp. 67- 98 (2005).
30. Rubin, P.A. and Narasimhan, R. "Fuzzy goal programming with nested priorities", Fuzzy Sets Syst., 14(2), pp. 115-129 (Nov. 1984). DOI: 10.1016/0165- 0114(84)90095-2.
31. Mavrotas, G. "Effective implementation of the "Constraint method in multi-objective mathematical programming problems", Appl. Math. Comput., 213(2), pp. 455-465 (Jul. 2009). DOI: 10.1016/j.amc.2009.03.037.
32. Ben-Tal, A., El Ghaoui, L., and Nemirovski, A.S., Robust Optimization, Princeton University Press (2009).
33. Soyster, A.L. "Technical Note-convex programming with set-inclusive constraints and applications to inexact linear programming", Oper. Res., 21(5), pp. 1154- 1157 (Oct. 1973). DOI: 10.1287/opre.21.5.1154.
34. Li, Z., Ding, R., and Floudas, C.A. "A comparative theoretical and computational study on robust counterpart optimization: I. robust linear optimization and robust mixed integer linear optimization", Ind. Eng. Chem. Res., 50(18), pp. 10567-10603 (Sep. 2011).DOI: 10.1021/ie200150p.
35. Bertsimas, D. and Sim, M. "The Price of robustness", Operations Research, 52(1), pp. 35-53 (2004). DOI: 10.1287/opre.1030.0065.
36. Ben-Tal, A., EI Ghaoui, L., and Nemirovski, A., Robust Optimization, Princeton University Press (2009).