The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies

Publication: Research - peer-reviewConference article – Annual report year: 2012

View graph of relations

In the Home Care Crew Scheduling Problem a staff of home carers 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 home carers 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.
Original languageEnglish
JournalEuropean Journal of Operational Research
Issue number3
Pages (from-to)598-610
StatePublished - 2012


Conference23rd European Conference on Operational Research
Internet address
CitationsWeb of Science® Times Cited: No match on DOI


  • Home care, Crew scheduling, Vehicle routing, Generalised precedence constraints, Branch-and-price, Set partitioning
Download as:
Download as PDF
Select render style:
Download as HTML
Select render style:
Download as Word
Select render style:

ID: 7583285