A novel and efficient exact technique for integrated staffing, assignment, routing, and scheduling of home care services under uncertainty

Bahman Naderi, Mehmet A. Begen, Gregory S. Zaric and Vahid Roshanaei

Omega, 2023, vol. 116, issue C

Abstract: We model and solve integrated multi-period staffing, assignment, routing, and scheduling of caregivers for home care services and obtain insights for the case under uncertainty. The goal is to construct a weekly schedule that adheres to related operational considerations and determines optimal staffing of caregivers by minimizing caregivers’ fixed- and overtime costs. For tractability, we incorporate a priori-generated visit pattern—an existing practical approach that deals effectively with hard assignment decisions. First, we propose a novel mixed-integer program (MIP) for the nominal (deterministic) problem. We then incorporate uncertainty in service and travel times and develop a robust counterpart by hybridizing interval and polyhedral uncertainty sets. Second, we show that there is a special mathematical structure within the model that allows us to develop a novel logic-based Benders branching-decomposition algorithm that systematically delays the resolution of difficult routing/ scheduling problems and efficiently solves both the nominal and robust MIP models, i.e., our solution approach for the deterministic case allowed us to solve the robust model. Using a benchmark and newly generated instances from the literature, we show that CPLEX can solve our nominal model with average optimality gap of 56%. On the other hand, our new exact technique can solve our nominal model to an average optimality gap of 5%. Third, we provide practical insights into (i) the price of robustness and (ii) the impacts of nurse flexibility and overtime. The average total cost does not increase beyond 18% than the nominal solution and the cost-savings of nurse flexibility is about 19% on average and higher than overtime’s. We also demonstrate that nurse flexibility impact is high and comparable in both cases, deterministic and stochastic.

Keywords: Combinatorial optimization; Home health care planning and scheduling; Multiple periods; Logic-based benders; New exact branching-decomposition (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048322002110
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jomega:v:116:y:2023:i:c:s0305048322002110

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2022.102805

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().