10:30 AM - 11:00 AM
A general heuristic for Home Health Care Routing Problem
Home Health Care Routing Problem (HHCRP) consists in designing routes followed by a team of care
workers to provide services needed by patients. This problem
is an extension of Vehicle Routing Problem with some additional constraints stemmed from the context
of home care.
Based on a recent literature review,
we first proposed a model as generic as possible for HHCRP.
Therefore, the model can take into account many constraints such as:
time windows, temporal dependencies, continuity of care,
qualification requirements, breaks.
To solve the problem, we developped a three phase heuristic algorithm using callbacks procedures that
allow to reconsider decisions taken during a previous phase.
The first phase determines the day in which each service will be provided,
while guaranteeing possible delays imposed between some services.
The second phase aims to assign care worker to services of each patient
maintaining continuity of care and balancing workload.
In the last phase, all routes of care workers is designed following the pervious decisions and
minimizing total routing cost while respecting temporal dependencies and
The proposed decomposition aims to reduce the complexity of the problem.
In order to improve resulting solution, callbacks procedures are developped
in order to reconsider the decisions taken before.
These callbacks procedures consist in moving services from a route to another,
from a day to another or prohibiting some decisions (e.g. care worker assignments) in order to explore new solution space.
Finally, computational results are presented to evaluate the efficiency of
the proposed heuristic. The results will be compared to optimal solution on small instances
and using CPLEX solver. Others tests will be performed in order to compare us
to results of benchmarks of the literature.
11:00 AM - 11:30 AM
Continuity of Care in Mid-Term Home Care Rostering for a German Home Care Provider
Continuity of care from the perspective of patients improves the quality of home care services evidentially. The nurse rostering decisions of a home care provider typically do not only include the assignment of shifts to nurses but also the assignment of nurses to patients requiring service within these shifts. Hence, it is an important goal of rostering in the context of home care to assign as few nurses as possible to each patient.
In this talk we present the monthly nurse rostering planning setup of our project partner, a leading German home care provider. The planning task is currently executed manually, even though it is extremely complex: Amongst others, legal and internal working time restrictions, availabilities of full and part time nurses, different required qualification levels and a broad set of different weekly visit frequencies (1 up to 21) have to be considered.
We elaborate a basic mathematical model (MIP) for the mid-term home care rostering problem (HCR) that meets all requirements of our project partner incorporating the assignment of nurses to weekly recurring tours (master tours). Based upon that basis we propose different extensions and reformulations: First, we evaluate the impact of different continuity measures and show on a real instance that continuity of care can be improved considerably compared to the manual solution. Second, we test different reformulations of the models, such as a network flow formulation, with regard to performance improvements. Finally, we show the effect of extending the models to incorporate continuity of care over a long-term horizon. All experiments are based on realistic instances derived from real planning data.
11:30 AM - 12:00 PM
A Lexicographic Model to Optimize Workload and Overlapping of Visits in the Home Health Care Assignment Problem
In this paper, we focus on avoid overlapping of visits under the same utilization level for assigning problem with time window in home health care services. There are two objectives solved in a lexicographic model. Firstly we balance the utilization of operators and then we avoid overlapping of visits. The operators’ busy state is calculated with a probabilistic approach. Mathematical models are developed by taking into account: time window of both patients and service skills; skill compatibilities between patients and operators; multiple time planning periods; continuity of care; operators’ capacity restrictions. Numerical results based on both realistic problem instances and generated test instances inspired by realistic settings are presented. Results obtained show that we can avoid overlapping of visits significantly at equal utilization level with our model.