Periodic home healthcare routing with stochastic patients : imitation learning enriched decision-making

Home healthcare (HHC) is gaining popularity as a means of alleviating pressure
on healthcare systems and improving patient well-being. However, effective HHC
operations require optimized resource utilization, a challenge complicated by in-
herent uncertainty and dynamism. Although deterministic variants of the home
healthcare routing and scheduling problem have been extensively studied, this
is not yet the case of stochastic and dynamic versions, which are particularly
challenging [Khorasanian et al., 2024].
Aiming to address this gap, our work analyzes the problem of a home health-
care provider (HHCP) making daily decisions regarding the acceptance of new
patient requests that arrive dynamically over the planning horizon. The HHCP
also has to assign the first visit of each accepted patient to a day. It is assumed
that every patient needs at least one visit and a specific periodicity of care, but
the total number of visits that a patient will effectively require is not known with
certainty. The HHCP must commit to serving accepted patients during their
whole episode of care, while creating routes for the available caregivers in order
to cover the visits planned for the current day. In case of excessive workload
due to poor planning decisions, the HHCP can call on external nurses as daily
recourse actions.
The objective of the HHCP is to accept as many patient requests as possible
and to minimize its total operating cost, including routing and outsourcing costs,
over the planning horizon.
We model this problem as a Markov decision process and propose a solution approach that integrates machine learning techniques with traditional combinatorial
optimization algorithms. This hybrid approach aims to tackle the stochasticity
inherent in the patients arrival process and their care durations using a neural
network (NN).
The NN will be trained on "perfect information" solutions in an imitation
learning fashion [Dalle et al., 2022, Baty et al., 2024]. This training dataset is
composed of solutions to the static and deterministic version of the problem of
interest, obtained from historical data. This problem variant is a periodic home
healthcare routing problem, and can therefore be solved using an adaptation of
the tabu search algorithm proposed by Cordeau et al. [Cordeau et al., 1997] for
the periodic vehicle routing problem. The expertise gained by the neural network
is then embedded into the same tabu search algorithm, which will be employed on
a rolling-horizon basis in order to develop a decision-making process for stochastic
and dynamic instances.