Dynamic Home Care Routing and Scheduling with Uncertain Number of Visits per Referral.

This article focuses on developing and evaluating a Markov decision process (MDP) model for the dynamic home care routing and scheduling problem (HRSP) with uncertain daily referrals and stochastic numbers of visits per referral. To address the computational complexity of solving the MDP optimally, the authors propose an approximate linear program (ALP) approach, including a closed-form solution for a special case and two heuristic reduction techniques to enable tractable solutions for large-scale instances. Numerical experiments demonstrate that the ALP policy generally outperforms a myopic policy representing current practice and a scenario-based policy, particularly in complex settings involving multiple service types, overtime, and visit uncertainty. The ALP policy exhibits consistent decision patterns, such as accepting all referrals within an inner radius of the nurse's depot and rejecting those beyond an outer radius, and assigning accepted referrals to either the earliest or latest allowable visit day. The study suggests future research directions including extensions to multiple nurses, incorporation of time windows, and fairness considerations in service allocation.