3 Presentations

• 
  10:30 AM - 11:00 AM

  A general heuristic for Home Health Care Routing Problem

  • Mohamed Cissé, presenter, Université de Tours
  • Yannick Kergosien, Université de Tours
  • Christophe Lenté, Université de Tours
  • Patrick Soriano, CIRRELT - HEC Montréal

  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
  qualification requirements.
  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

  • Jacqueline Wirnitzer, presenter, FZI Research Center for Information Technology
  • Anne Meyer, FZI Research Center for Information Technology
  • Stefan Nickel, Karlsruhe Institute of Technology

  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

  • Li Kang, Shanghai Jiao Tong University
  • Andrea Matta, presenter, Shanghai Jiao Tong University

  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.