Multimodal Home Healthcare Scheduling using a novel CP-VND-DP Approach

Activity: Talk or presentation / LecturePresentation at a scientific conference / workshop


Healthcare services, especially home healthcare services (HHC), are of great signi cance in today's western world, where the average age is steadily increasing. HHC services are particularly popular, since patients prefer being nursed at home than at retirement homes. However, nding a good schedule is challenging: { Nurses need to arrive at the patients' homes in certain time windows, { Each service requires a quali cation that the nurse must hold (e.g. a nurse for cleaning may not perform a medical service) { The schedule should meet preferences of patients, nurses and employer { All legal and contractual issues (such as su cient resting periods) should be satis ed We consider a real-world setting, where the objective is to nd a schedule with minimal travel time (to reduce operational costs), such that all patients are assigned a nurse, satisfying as many side constraints from the above as possi- ble. Our goal is to construct a exible framework that generates e cient nurse schedules for di erent home care companies. Real-world HHC problems are challenging for many reasons. First, the HHC problem constitutes a combination of two NP-hard problems: vehicle routing with time windows [4, 5] and nurse rostering [6]. Therefore, we need to em- ploy a heuristic approach since exact solving methods can typically only tackle small instances. Second, real-world instances include many side constraints that vary greatly between di erent service providers (e.g. di erent nurse contracts). Hence we require a exible solving architecture, where constraints can be easily added/removed. Third, to provide accurate schedules, it is crucial to use accu- rate travel time estimations, regarding di erent modes of transport. Therefore, we include travel time estimations from a large set of historical data for di erent transport modes (car, public transport, bike, foot) into our system.
Period23 May 201127 May 2011
Event title8th International Conference on Integration of Artificial Intelligence and Operations Research Techniques in Constraint Programming for Combinatorial Optimization Problems CPAIOR2011
Event typeOther
Degree of RecognitionInternational

Research Field

  • Former Research Field - Mobility Systems