Home health care structures provide care for the elderly, people with disabilities as well as patients with chronic conditions. Since there has been an increase in demand, organizations providing home health care are eager to optimize their activities. In addition, the increase in patient numbers has led organizations to expand their geographical reach. As a result, home health care structures tend to be located in different offices to limit their travel time and, consequently, caregivers employed by these various structures must be assigned to one of the offices so they start and end their workday at their associated office. Unlike the existing literature where an upstream assignment of caregivers is performed to become a parameter of the model, the assignment of caregivers to offices is solved during the resolution of the problem in order to obtain the best possible combinations. Thus, we suggest a mixed-integer programming model of the multi-depot home health care assignment, routing, and scheduling problem without prior assignment of caregivers to the home health care offices. In addition, we propose an original matheuristic-based approach with different assignment strategies to assign visits and caregivers to the home health care offices in order to solve the problem. The experiments are conducted on a set of 56 heterogeneous instances of various sizes. Results are compared with best solutions obtained by a commercial solver, and with a lower bound obtained by Lagrangian relaxation. The results highlight the efficiency of the matheuristic-based approach since it provides a low deviation ratio with a faster computational time.
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2020057
Keywords: Home health care, matheuristic, multi-depot, assignment, Lagrangian relaxation
@article{RO_2021__55_S1_S1013_0,
author = {Decerle, J\'er\'emy and Grunder, Olivier and El Hassani, Amir Hajjam and Barakat, Oussama},
title = {A matheuristic-based approach for the multi-depot home health care assignment, routing and scheduling problem},
journal = {RAIRO. Operations Research},
pages = {S1013--S1036},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
doi = {10.1051/ro/2020057},
mrnumber = {4223145},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020057/}
}
TY - JOUR AU - Decerle, Jérémy AU - Grunder, Olivier AU - El Hassani, Amir Hajjam AU - Barakat, Oussama TI - A matheuristic-based approach for the multi-depot home health care assignment, routing and scheduling problem JO - RAIRO. Operations Research PY - 2021 SP - S1013 EP - S1036 VL - 55 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020057/ DO - 10.1051/ro/2020057 LA - en ID - RO_2021__55_S1_S1013_0 ER -
%0 Journal Article %A Decerle, Jérémy %A Grunder, Olivier %A El Hassani, Amir Hajjam %A Barakat, Oussama %T A matheuristic-based approach for the multi-depot home health care assignment, routing and scheduling problem %J RAIRO. Operations Research %D 2021 %P S1013-S1036 %V 55 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020057/ %R 10.1051/ro/2020057 %G en %F RO_2021__55_S1_S1013_0
Decerle, Jérémy; Grunder, Olivier; El Hassani, Amir Hajjam; Barakat, Oussama. A matheuristic-based approach for the multi-depot home health care assignment, routing and scheduling problem. RAIRO. Operations Research, Tome 55 (2021), pp. S1013-S1036. doi: 10.1051/ro/2020057
and , Cyclic preference scheduling of nurses using a Lagrangian-based heuristic. J. Scheduling 10 (2007) 5–23. | MR | Zbl | DOI
, and , Weekly scheduling models for traveling therapists. Socio Econ. Planning Sci. 47 (2013) 191–204. | DOI
, and , An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces 27 (1997) 35–48. | DOI
, Les services de soins infirmiers à domicile en 2008. Études et résultats 739 (2010).
, , and , A bi-objective home care scheduling problem: analyzing the trade-off between costs and client inconvenience. Eur. J. Oper. Res. 248 (2016) 428–443. | MR | DOI
, , and , Tackling large-scale home health care delivery problem with uncertainty. In: International Conference on Automated Planning and Scheduling (ICAPS-17). Pittsburgh, PE (2017).
and , A home health care routing and scheduling problem. Technical report CAAM TR98-04, Rice University, Houston, TX (1998). http://citeseerx.ist.psu.edu/viewdoc/summary.
, , , , and , Or problems related to home health care: a review of relevant routing and scheduling problems. Oper. Res. Health Care 13–14 (2017) 1–22.
, , and , A two-phases matheuristic for the home care routing and scheduling problem. 8th IFAC Conference on Manufacturing Modelling, Management and Control MIM 2016. IFAC-PapersOnLine 49 (2016) 1484–1489.
, , and , A memetic algorithm for a home health care routing and scheduling problem. Oper. Res. Health Care 16 (2018) 59–71. | DOI
, and , Lagrangian relaxation methods for solving the minimum fleet size multiple traveling salesman problem with time windows. Manage. Sci. 34 (1988) 1005–1022. | MR | Zbl | DOI
, and , Synchronization between human resources in home health care context, edited by , , , and . In: Proceedings of the International Conference on Health Care Systems Engineering. Springer, New York, NY (2014) 73–86. | DOI
, and , Real-time scheduling optimization considering the unexpected events in home health care. J. Comb. Optim. 37 (2019) 196–220. | MR | DOI
, , and , Home care service planning. The case of Landelijke Thuiszorg. Eur. J. Oper. Res. 243 (2015) 292–301. | DOI
, and , Caregivers’ assignment problem in home health care structures. In: Proceedings of 2013 International Conference on Industrial Engineering and Systems Management (IESM) (2013) 1–8.
, and , Laps care – an operational system for staff planning of home care. Eur. J. Oper. Res. 171 (2006) 962–976. | Zbl | DOI
and , Home health care routing and scheduling: a review. Comput. Oper. Res. 77 (2017) 86–95. | MR | DOI
, The Lagrangian relaxation method for solving integer programming problems. Manage. Sci. 27 (1981) 1–18. | MR | Zbl | DOI
Optimization, Gurobi optimizer reference manual (2016). http://www.gurobi.com.
, and , Validation of subgradient optimization. Math. Program. 6 (1974) 62–88. | MR | Zbl | DOI
and , Robust nurse-to-patient assignment in home care services to minimize overtimes under continuity of care. Oper. Res. Health Care 3 (2014) 48–58. | DOI
, and , An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and synchronized visits. Comput. Oper. Res. 101 (2019) 250–262. | MR | DOI
, and , The home health care routing and scheduling problem with interdependent services. Health Care Manage. Sci. 17 (2014) 15–30. | DOI
, and , Mid-term and short-term planning support for home health care services. Eur. J. Oper. Res. 219 (2012) 574–587. | Zbl | DOI
and , Solving routing problems with pairwise synchronization constraints. Cent. Eur. J. Oper. Res. 26 (2018) 443–464. | MR | DOI
, , and , The home care crew scheduling problem: preference-based visit clustering and temporal dependencies. Eur. J. Oper. Res. 219 (2012) 598–610. | Zbl | DOI
, , and , Staff dimensioning in homecare services with uncertain demands. Int. J. Prod. Res. 53 (2015) 7396–7410. | DOI
, and , A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transp. Res. E: Logist. Transp. Rev. 128 (2019) 52–95. | DOI
, Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35 (1987) 254–265. | MR | Zbl | DOI
and , The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA (2001) 363.
, and , Securing home health care in times of natural disasters. OR Spect. 33 (2011) 787–813. | MR | Zbl | DOI
and , Toward 2020: visions for nursing setting the stage for the future. Can. Nurse 102 (2006) 22.
, , and , The patient assignment problem in home health care: using a data-driven method to estimate the travel times of care givers. Flexible Serv. Manuf. J. 28 (2016) 304–335. | DOI
Cité par Sources :
