1 Operations Research, Department of Management Engineering, Technical University of Denmark2 Department of Management Engineering, Technical University of Denmark3 unknown
Preference-Based Visit Clustering and Temporal Dependencies
In the Home Care Crew Scheduling Problem a staff of caretakers has to be assigned a number of visits to patients' homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to caretakers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits. We model the problem as a set partitioning problem with side constraints and develop an exact branch-and-price solution algorithm, as this method has previously given solid results for classical vehicle routing problems. Temporal dependencies are modelled as generalised precedence constraints and enforced through the branching. We introduce a novel visit clustering approach based on the soft preference constraints. The algorithm is tested both on real-life problem instances and on generated test instances inspired by realistic settings. The use of the specialised branching scheme on real-life problems is novel. The visit clustering decreases run times significantly, and only gives a loss of quality for few instances. Furthermore, the visit clustering allows us to find solutions to larger problem instances, which cannot be solved to optimality.
Set partitioning; Crew scheduling; Routing; Home health care; Visit clustering; Generalised precedence constraints; Temporal dependencies; Integer programming; Real-life application; Dantzig-Wolfe decomposition; Temporal dependency; Scheduling; Health care; Preferences; Clustering; Column generation; Vehicle routing with time windows; Branch-and-price; Home care; Vehicle routing; Synchronisation