  Despite the rapid growth of the home care industry, research on the
scheduling and routing of home care visits in the presence of uncertainty is
still limited. This paper investigates a dynamic version of this problem in
which the number of referrals and their required number of visits are
uncertain. We develop a Markov decision process (MDP) model for the
single-nurse problem to minimize the expected weighted sum of the rejection,
diversion, overtime, and travel time costs. Since optimally solving the MDP is
intractable, we employ an approximate linear program (ALP) to obtain a feasible
policy. The typical ALP approach can only solve very small-scale instances of
the problem. We derive an intuitively explainable closed-form solution for the
optimal ALP parameters in a special case of the problem. Inspired by this form,
we provide two heuristic reduction techniques for the ALP model in the general
problem to solve large-scale instances in an acceptable time. Numerical results
show that the ALP policy outperforms a myopic policy that reflects current
practice, and is better than a scenario-based policy in most instances
considered.
