The Home Care Crew Scheduling Problem: Preference-Based Visit Clustering and Temporal Dependencies

Matias Sevel Rasmussen, Tor Justesen, Anders Dohn, Jesper Larsen

    Research output: Book/ReportReport

    875 Downloads (Pure)


    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.
    Original languageEnglish
    Place of PublicationKgs. Lyngby
    PublisherDTU Management
    Number of pages27
    ISBN (Print)978-87-90855-80-2
    Publication statusPublished - 2010
    SeriesDTU Management 2010


    • 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


    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