Jointly rostering, routing, and rerostering for home health care services: A harmony search approach with genetic, saturation, inheritance, and immigrant schemes

Highlights

• We are the first to consider jointly rostering, routing, and rerostering for home health care services.

• Concurrently optimizing both rostering/rerostering and routing, different from separately optimizing them previously.

• The proposed harmony search algorithm is improved by genetic, saturation, inheritance, and immigrant schemes.

• Rostering additionally considers nurse preferences to increase nurse satisfaction.

• The algorithm can immediately address rerostering to respond to occurrence of sudden incidents.

Abstract

In home health care (HHC) services, nurses or professional caregivers are dispatched to patients’ homes to provide medical care services, such that each patient can stay at home to be treated periodically. The HHC problem consists of the nurse rostering problem (NRP) and the vehicle routing problem with time windows (VRPTW), both of which are NP-hard problems, which are harder or equal to the hardest problem in the NP (nondeterministic polynomial time) problem class and generally cannot be solved efficiently. To the best of our knowledge, the previous algorithmic approaches were designed to separately address NRP and VRPTW of the HHC problem. However, NRP and VRPTW of the HHC problem are intercorrelated, and their respective optimal objectives may be in conflict with each other in many cases. Additionally, the problem generally involves too many constraints to be solved, and most previous works did not address occurrence of sudden incidents in HHC services (e.g., a nurse or a patient suddenly requests for a leave, and a patient suddenly changes the time slot to be treated) such that the original nurse roster could become infeasible. Under constraints of nurse qualifications, working laws, nurse preferences, and vehicle routing, the first model considers nurse rostering and vehicle routing concurrently to minimize total costs of nurse overtime and vehicle routing. The second model extends the first model with rerostering caused by occurrence of sudden incidents. Harmony search algorithm (HSA) has been shown to perform better in solving NRPs than conventional metaheuristics, and hence this work proposes an improved HSA with genetic and saturation schemes, in which the solution representation is designed to concurrently determine nurse rostering and vehicle routing. For the second rerostering model, inheritance and immigrant schemes are added to the HSA to adapt to the change caused by occurrence of sudden incidents. Experimental results show that the proposed HSA performs well and can adapt to the change caused by sudden incidents.

Introduction

In the home health care (HHC) service, nurses (or professional caregivers) are dispatched to patients’ (or caretakers’) homes to provide medical treatments or assistance periodically. The home health care problem (HHCP) (Cheng & Rich, 1998) involves the problem of planning nurses’ duty rosters (i.e., nurse rostering problem; NRP) (Bagheri, Devin, & Izanloo, 2016) and the problem of allocating nurses to different vehicle routes to meet each patient’s time window (i.e., vehicle routing problem with time windows; VRPTW) (Wang, Li, & Hu, 2015). A detailed survey on HHCPs can be found in (Fikar & Hirsch, 2017).

To the best of our knowledge, all the previous works on HHCPs separately addressed VRPTW and NRP of the HHCP. However, VRPTW and NRP of the HHCP are intercorrelated with each other. Additionally, it is crucial to design a nurse roster to decrease nurses’ dissatisfaction with fairness and justice of the roster, and further to increase quality of service and decrease medical expenses as well as risks of occupational hazards (Clark et al., 2007, Hallah and Alkhabbaz, 2013). With advance in technologies, lots of medical facilities are equipped with wireless mobile communications and the Internet of things (Bennett-Milburn and Spicer, 2013, Marcelli et al., 2007). With these facilities, hospitals can keep control of patients’ conditions. Once a patient has a sudden incident at home, the hospital is able to remotely obtain first-hand information through medical facilities at home, and dispatch nurses to provide immediate services. Such a sudden patient insertion leads to necessity of in-time rerostering.

This work investigates the problem that jointly considers rostering, routing, and rerostering for HHC services (R³HHCS), including the following two models. Given information on patients and considering hard and soft constraints in the HHC service, the first model concurrently determines nurse rostering and vehicle routing to patients’ homes, with objective of minimizing total costs of nurse overtime and vehicle routing, different from previous works that separately addressed NRP and VRPTW. Given a solution including nurse rostering and vehicle routing for the first model, the second model considers nurse rerostering caused by occurrence of sudden incidents in practice. Thus, this rerostering model determines a new solution that minimizes not only the objective of the first model but also the difference between the original and the new solutions, because nurses (e.g., those with plans for days-off) would prefer a new solution with not much difference from the original solution.

The HHCP has been shown to be NP-hard (Steeg, 2008), because it includes two NP-hard problems (i.e., NRP and VRPTW), which are harder or equal to the hardest problem in the NP (nondeterministic polynomial time) problem class, and generally cannot be solved efficiently (i.e., in deterministic polynomial time). Hence, it is suitable for applying metaheuristics to solve the HHCP. Hadwan, Ayob, Sabar, and Qu (2013) showed that their proposed harmony search algorithm (HSA) performs better than the genetic algorithm (GA) in solving the NRP. Additionally, Frosolini, Braglia, and Zammori (2010) proposed a modified harmony search (MHS) algorithm with genetic and saturation schemes for a manufacturing scheduling problem that performs better than the GA and the conventional HSA. For handling dynamics of the concerned problems, this work considers an inheritance scheme to decrease the difference between original and new rosters, and an immigrant scheme (Cheng & Yang, 2010) to increase diversify of the solutions produced. That is, this work proposes an improved HSA with genetic, saturation, inheritance, and immigrant schemes for the R³HHCS.