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

Matias Sevel Rasmussen, Tor Fog Justesen, Anders Høeg Dohn, Jesper Larsen

    Research output: Contribution to journalConference articleResearchpeer-review


    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
    Publication statusPublished - 2012
    Event23rd European Conference on Operational Research - Bonn, Germany
    Duration: 5 Jul 20098 Jul 2009
    Conference number: 23


    Conference23rd European Conference on Operational Research
    Internet address


    • Home care
    • Crew scheduling
    • Vehicle routing
    • Generalised precedence constraints
    • Branch-and-price
    • Set partitioning

    Fingerprint Dive into the research topics of 'The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies'. Together they form a unique fingerprint.

    Cite this