Dynamic scheduling of home care patients to medical providers

Home care provides personalized medical care and social support to patients within their own homes. Our work proposes a dynamic scheduling framework to assist in the assignment of health practitioners (HPs) to patients who arrive stochastically over time and are heterogeneous with respect to their health requirements, service duration, and region of residence. We model the decision of which patients to assign to HPs as a discrete‐time, rolling‐horizon, infinite‐stage Markov decision process. Due to the curse of dimensionality and the combinatorial structure associated with an HP's travel, we propose an approximate dynamic programming (ADP) approach based on a one‐step policy improvement heuristic. Four policies are investigated: The first two prioritize HP fairness by balancing service and travel times, respectively, while the other two are based on fluid approximations of the system. We show that the first fluid model is optimal if the number of patient arrivals is sufficiently large while the second performs better experimentally; both approaches leverage pricing and decomposition strategies. We compare our framework to more commonly implemented policies—constrained versions of the classical vehicle routing problem—in a simulation study using data collected from a Canadian home care provider. We show that, in contrast to these approaches, by accounting for future uncertainty, substantial cost savings can be obtained while a fewer number of referrals are rejected. We also find that well‐performing policies assign patients to HPs operating within a small set of adjacent regions while considering the number of periods that a patient requires care for. Otherwise, HP workload may not be appropriately balanced over the long‐term even if travel time is minimized.