We study the integration of multi-period assignment, routing, and scheduling of care workers for home health care services. In such a context, it is important to ensure service consistency, where a designated care worker must visit each patient at a specific time and in a consistent manner based on an established route and schedule. The challenge in maintaining service consistency and quality lies in the fact that a care agency must determine consistent and efficient schedules of visits to patient locations for multiple care workers despite uncertainty in travel and service times. To this end, we extend the home health care routing and scheduling problem (HHCRSP) presented in the literature and introduce a stochastic optimization model to incorporate service level constraints under stochastic travel and service times. We propose the solution framework based on two representations: a discrete scenario set and an extreme value theory-based (EVT-based) approximation. To tackle instances of practical size, we employ branch-and-check (B&Ch), a variant of the logic-based Benders decomposition (LBBD) method, where the subproblem is efficiently solved using constraint programming (CP). The results show that the stochastic approaches, especially with the EVT-based approximation model, can efficiently handle practical benchmark instances while producing schedules with significantly higher service levels than the deterministic approach. We also demonstrate the effectiveness of scenario-based and EVT-based models under different types of uncertainty.
Published October 2023 , 19 pages
G2345.pdf (700 KB)