A Hybrid Approach to Solve the Periodic Home Health Care Problem
Home health care (HHC) services provide nursing assistance to the elderly with the advantage of allowing them to continue living at their homes. Usually a HHC service has a fleet of vehicles that are used by nurses to get to the patients, where they have
- PDF / 169,968 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 156 Views
duction Home Health Care (HHC) services are becoming increasingly important. Their patients receive medical treatments at home. Therefore a HHC service provider has a fleet of vehicles used by nurses to travel to the patients. Usually, there are various shifts that can differ in the set of nurses available and jobs required. A periodic aspect is also involved, since the jobs need to be performed repeatedly during the schedule. In practice, the HHC problem is solved manually by a senior nurse, who often spends a whole day creating next week’s schedule. From a mathematical point of view, this problem is of special interest, because it involves two NP-hard subproblems: the nurse rostering
298
J¨org Steeg and Michael Schr¨ oder
problem (NRP) and the vehicle routing problem (VRP). The former arises from the fact that each nurse is only available for some of the shifts. Furthermore, their working times are usually restricted to a maximum number of hours a week. The VRP is also part of the planning problem, since travel distances should be minimized. It is periodic and has time windows. The time windows arise from the patients’ preference to be treated at certain times. Hence, the HHC problem encapsulates a periodic vehicle routing problem with time windows (PVRPTW). Only limited research has been conducted into the Home Health Care problem. It seems to have been first described by Cheng and Rich [2]. In their paper, they tackle the problem with two MIP formulations and a two-phase construction heuristic. A more recent article by Bertels and Fahle [1] combines constraint programming (CP) with meta-heuristics to solve the HHC problem. Finally, a paper by Eveborn, Flisberg, and R¨ onnqvist [4] models the Home Health Care problem for a single day as a set partitioning problem. This paper is organized as follows: section 2 presents our model, while section 3 presents the hybrid constraint programming – large neighborhood search approach. We conclude by presenting first computational results.
2 A Model for Home Health Care Planning In this section, we present our new model for the Home Health Care problem, which combines a Nurse Rostering problem with a Periodic Vehicle Routing problem. Usually, the literature considers the problems separately, or Home Health Care problems with a single shift only. In general, the problem consists mainly of two elements: jobs and nurses. The task is to assign to each job a nurse such that the assignment is feasible. This takes place in a planning horizon consisting of S shifts. Each shift has a time window [0..H]. A job in the planning horizon represents a task at a patient’s home. Different jobs can affect the same patient. A job j is characterized by a hard time window [hbsj ..hbej ] and a processing time ptj . Furthermore, it has a frequency fj , which states how many times the job must be processed during the planning horizon. The shifts in which the job has to=be performed are > given by a set of possible shift combinations Rj = Rj,1 , . . . , Rj,Kj . The sets Rj,l are subsets of shifts, and
Data Loading...
