Optimization of the Stochastic Home Health Care Routing and Scheduling Problem with Multiple Hard Time Windows

Document Type : GOL20

Authors

SI2M Laboratory INSEA, Rabat, Morocco

Abstract

Home health care (HHC) aims to assist patients at home and to help them to live with greater independence, avoiding hospitalization or admission to care institutions. The patients should be visited within their availability periods. Unfortunately, the uncertainties related to the traveling and caring times would sometimes violate these time windows constraints, which will qualify the service as poor or even risky. This work addresses the home health care routing and scheduling problem (HHCRSP) with multiple hard/fixed time windows as well as stochastic travel and service times. A two-stage stochastic programming model recourse (SPR model) is proposed to deal with the uncertainty. The recourse is to skip patients if their availability periods will be violated. The objective is to minimize caregivers’ traveling cost and the average number of unvisited patients. Monte Carlo simulation is embedded into the genetic algorithm (GA) to solve the SPR model. The results highlight the efficiency of the GA, show the complexity of the SPR model, and indicate the advantage of using multiple time windows.

Keywords

References

Bazirha, M., Kadrani, A., Benmansour, R., (2020a). Daily scheduling and routing of home health care with multiple availability periods of patients. In Variable Neighborhood Search. ICVNS 2019. Lecture Notes in Computer Science, Springer International Publishing, Cham, pp. 178–193.
Bazirha, M., Kadrani, A., Benmansour, R., (2020b). Scheduling optimization of the home health care problem with stochastic travel and care times. In 2020 5th International Conference on Logistics Operations Management (GOL), IEEE. pp. 1–8.
Bazirha, M., Kadrani, A., Benmansour, R., (2021). Stochastic home health care routing and scheduling problem with multiple synchronized services. Annals of Operations Research, pp. 1–29.
Ben-Tal, A., El Ghaoui, L., Nemirovski, A., (2009). Robust optimization. Vol. 28. Princeton University Press.
Bernard, D.G., (1955). Linear programming under uncertainty. Management Science, Vol. 1, pp. 97–206.
Bertsimas, D., Brown, D.B., Caramanis, C., (2011). Theory and applications of robust optimization. SIAM review, Vol. 53, pp. 464–501.
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, Vol. 248, pp. 428–443.
Braysy, O., Gendreau, M., (2005). Vehicle routing problem with time windows, part I: Route construction and local search algorithms. Transportation science, Vol. 39, pp. 104–118.
Burke, E.K., De Causmaecker, P., Berghe, G.V., Van Landeghem, H., (2004). The state of the art of nurse rostering. Journal of scheduling, Vol. 7, pp. 441–499.
Cappanera, P., Scutellà, M.G., (2021). Addressing consistency and demand uncertainty in the home care planning problem. Flexible Services and Manufacturing Journal, pp. 1–39.
Cappanera, P., Scutellà, M.G., Nervi, F., Galli, L., (2018). Demand uncertainty in robust home care optimization. Omega, Vol.80, pp. 95–110.
Charnes, A., Cooper, W.W., (1959). Chance-constrained programming. Management science, Vol. 6, pp. 73–79.
Cissé, M., Yalçındağ, S., Kergosien, Y., Şahin, E., Lenté, C., and Matta, A., (2017). Or problems related to home health care: A review of relevant routing and scheduling problems. Operations Research for Health Care, Vol. 13, pp. 1–22.
Decerle, J., Grunder, O., El Hassani, A.H., Barakat, O., (2019). A memetic algorithm for multi-objective optimization of the home health care problem. Swarm and evolutionary computation, Vol. 44, pp. 712–727.
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, Vol. 243, pp. 292–301.
Errico, F., Desaulniers, G., Gendreau, M., Rei, W., Rousseau, L.M., (2016). A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times. European Journal of Operational Research, Vol. 249, pp. 55–66.
Fathollahi-Fard, A.M., Ahmadi, A., Goodarzian, F., Cheikhrouhou, N., (2020). A bi-objective home healthcare routing and scheduling problem considering patients’ satisfaction in a fuzzy environment. Applied soft computing, Vol. 93, pp.  106385.
Gendreau, M., Laporte, G., Séguin, R., (1996). Stochastic vehicle routing. European Journal of Operational Research, Vol. 88, pp. 3–12.
Glover, F., (1986). Future paths for integer programming and links to artificial intelligence. Computers & operations research, Vol. 13, pp. 533–549.
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, Vol. 23, pp. 89–113.
Holland, J.H., (1992). Genetic algorithms. Scientific American, Vol. 267, pp. 66–73.
Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P., (1983). Optimization by simulated annealing. Science, Vol.  220, pp. 671–680.
Laporte, G., Louveaux, F., Mercure, H., (1992). The vehicle routing problem with stochastic travel times. Transportation science, Vol. 26, pp. 161–170.
Li, X., Tian, P., Leung, S.C., (2010). Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm. International Journal of Production Economics, Vol. 125, pp. 137–145.
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, Vol. 55, pp. 558–575.
Luo, Z., Qin, H., Zhang, D., Lim, A., (2016). Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost. Transportation Research Part E: Logistics and Transportation Review, Vol. 85, pp. 69–89.
Mankowska, D.S., Meisel, F., Bierwirth, C., (2014). The home health care routing and scheduling problem with interdependent services. Health care management science, Vol. 17, pp. 15–30.
Marinaki, M., Marinakis, Y., (2016). A glowworm swarm optimization algorithm for the vehicle routing problem with stochastic demands. Expert Systems with Applications, Vol. 46, pp. 145–163.
Mendoza, J.E., Rousseau, L.M., Villegas, J.G., (2016). A hybrid metaheuristic for the vehicle routing problem with stochastic demand and duration constraints. Journal of Heuristics, Vol. 22, pp. 539–566.
Mladenovic, N., Hansen, P., (1997). Variable neighborhood search. Computers & operations research, Vol. 24, pp. 1097–1100.
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, Vol. 219, pp. 598–610.
Redjem, R., Marcon, E., (2016). Operations management in the home care services: a heuristic for the caregivers’ routing problem. Flexible Services and Manufacturing Journal, Vol. 28, pp. 280–303.
Rest, K.D., Hirsch, P., (2016). Daily scheduling of home health care services using time-dependent public transport. Flexible Services and Manufacturing Journal, Vol. 28, pp. 495–525.
Saffarian, M., Barzinpour, F., Eghbali, M.A., (2015). A robust programming approach to bi-objective optimization model in the disaster relief logistics response phase. International Journal of Supply and Operations Management, Vol. 2, pp. 595–616.
Shahnejat-Bushehri, S., Tavakkoli-Moghaddam, R., Boronoos, M., Ghasemkhani, A., (2021). A robust home health care routing-scheduling problem with temporal dependencies under uncertainty. Expert Systems with Applications, Vol. 182, pp. 115209.
Shi, Y., Boudouh, T., Grunder, O., (2019). A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transportation Research Part E: Logistics and Transportation Review, Vol. 128, pp. 52–95.
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, Vol. 102, pp. 218–233.
Solomon, M.M., Desrosiers, J., (1988). Survey paper—time window constrained routing and scheduling problems. Transportation Science, Vol. 22, pp. 1–13.
Tarricone, R., Tsouros, A.D., (2008). Home care in Europe: the solid facts. WHO Regional Office Europe.
Tas, D., Dellaert, N., van Woensel, T., De Kok, T., (2014a). The time-dependent vehicle routing problem with soft time windows and stochastic travel times. Transportation Research Part C: Emerging Technologies, Vol. 48, pp. 66–83.
Tas, D., Gendreau, M., Dellaert, N., Van Woensel, T., De Kok, A., (2014b). Vehicle routing with soft time windows and stochastic travel times: A column generation and branch-and-price solution approach. European Journal of Operational Research, Vol. 236, pp. 789–799.
Yuan, B., Liu, R., Jiang, Z., (2015). A branch-and-price algorithm for the home health care scheduling and routing problem with stochastic service times and skill requirements. International Journal of Production Research, Vol. 53, pp. 7450–7464.
International Journal of Supply and Operations Management
Volume 9, Issue 2
May 2022
Pages 235-250

Files

Share

How to cite

Statistics