Routing science in home care: balance travel and continuity

Why Swedish home-care routing explodes combinatorially, why brute-force or purely human planning cannot cope, and how CAIRE's planner-guided model combines human-crafted slingor with solver-generated alternatives for review.

Home-care routing is not a logistics afterthought. It is a fusion of VRPTW, crew scheduling, workforce assignment, and multi-objective optimization. Even a modest daily schedule with 350 visits and 28 caregivers already creates (350!) 28 permutations before labor law and continuity are applied.

CAIRE's architecture combines the tacit expertise of municipal planners with constraint-based candidate search. Planners pin visits that need stability; the solver compares the remaining assignments and travel options, and the planner reviews legality and KPI tradeoffs before publishing.

Example: 350 Visits, 28 Caregivers (07–22, >10 visits per shift)

The daily home-care scheduling problem can be understood in three nested layers:

With 350 visits and 28 caregivers , the total number of ways to:

350! × C(377,27) ≈ 10 753

Explanation: The binomial coefficient C(377,27) counts the ways to partition 350 visits among 28 caregivers (using 27 dividers among 377 total positions). The factorial 350! counts all possible orderings of the visits. Together, this represents every possible assignment and route ordering.

This number is 673 orders of magnitude larger than the number of atoms in the observable universe (≈10⁸⁰).

• assign each visit to a caregiver
• order the visits within each caregiver's route

Inside the astronomical solution space, only a microscopic subset of schedules is actually feasible , i.e., they satisfy:

Mathematically: The feasible region is a tiny, fragmented, high-dimensional subset of the giant search space.

• Swedish labor law (rest periods, breaks, weekly rest, maximum hours)
• Union and municipal requirements
• Time windows (earliest/latest, soft/hard)
• Travel times & geography
• Client–caregiver continuity
• Skills and certification requirements
• Reasonable workload & unused time
• Coordination of breaks and lunch periods

Inside the configured feasible region, each run scores candidates using:

arg min f (travel, continuity, overtime, fairness, stability, utilization)

Explanation: "arg min" identifies the lowest configured score among the candidates evaluated in that run. The function f combines travel time, continuity deviations, overtime, fairness, schedule changes, and utilization according to the configured weights. The score supports comparison; it does not prove that every possible schedule was evaluated or promise a particular operational outcome.

A planning run can therefore present:

• a subset of candidate schedules that pass the configured hard-constraint checks, and
• their measured scores and tradeoffs for planner comparison.

Home care is non-stationary.

Every small event shifts the feasible region:

Each change moves the feasible region to a new part of the solution space.

This means the previous candidate may no longer match the current inputs and needs to be evaluated again.

• a caregiver becomes sick
• a visit takes 7 minutes longer
• traffic increases
• a new client is added
• a client cancels
• continuity requires a specific match
• availability changes
• legal rules collide with schedule delays

A slinga is a static weekly pattern created by humans.

So the moment a single disruption occurs:

Manual replanning becomes harder as each changed input creates a new multi-constraint, NP-hard planning problem.

• the slinga leaves the feasible region
• it becomes invalid
• replanning is required

Given:

• the gigantic search space (~10⁷⁵³)
• the microscopic feasible region
• the constantly moving constraints
• the fragility of slingor
• the need to reassess a plan after inputs change

a practical planner-guided workflow is:

→ encode tacit knowledge, continuity, geography, relationships → define baseline structure

• → encode tacit knowledge, continuity, geography, relationships
• → define baseline structure

This workflow combines stable human structures with systematic candidate comparison and planner review.

• → compares many alternatives against the configured constraints
• → tracks moving feasibility
• → evaluates configured legal rules and flags violations for review
• → measures changes to pinned and stable assignments
• → surfaces disruption tradeoffs for the planner
• → produces a new candidate when the planner starts a run after inputs change

A single day with 350 visits and 28 caregivers produces (350!) 28 route permutations. Adding Swedish labor contracts, sick leave, and continuity transforms the feasible region into billions of isolated pockets.

Continuity layer: Each client-to-caregiver promise adds a bipartite constraint; breaking one ripples across the entire day. Breaks & fairness: Paid vs unpaid breaks plus fairness windows create temporal holes that humans fill by intuition but solvers can evaluate systematically. Disruptions: Every sick leave instance converts the deterministic problem into a stochastic VRPTW, proven PSPACE-hard. TSP VRPTW HHCRSP Multi-objective

• Continuity layer: Each client-to-caregiver promise adds a bipartite constraint; breaking one ripples across the entire day.
• Breaks & fairness: Paid vs unpaid breaks plus fairness windows create temporal holes that humans fill by intuition but solvers can evaluate systematically.
• Disruptions: Every sick leave instance converts the deterministic problem into a stochastic VRPTW, proven PSPACE-hard.

Normalized to Karlstad pilot (Q3 2025), anonymized service areas.

Let H be the human feasible region (pinned slingor, tacit geography, politics) and S the candidates a solver can compare using configured rules and KPI tradeoffs. Their intersection H ∩ S gives the planner relevant alternatives to review.

Human planners: Understand building access, qualitative promises, and acceptable disruption patterns. Solver adapter: Evaluates configured constraints, fairness measures, and alternatives for the current planning run. Planner-guided result: Planners pin visits that need stability, choose which remaining visits may move, and review every proposed change before publishing. Scenario Human-only Solver-only Hybrid Weekly slingor Stable relationships, manually assessed travel Configured constraints without tacit context Pinned relationships with reviewed tradeoffs New clients Manual placement and conflict checks Ignores tacit promises Candidate compared and approved by a planner Mid-day sick leave Manual swaps, overtime risk May reshuffle pinned visits Planner compares new-run candidates against configured pins

• Human planners: Understand building access, qualitative promises, and acceptable disruption patterns.
• Solver adapter: Evaluates configured constraints, fairness measures, and alternatives for the current planning run.
• Planner-guided result: Planners pin visits that need stability, choose which remaining visits may move, and review every proposed change before publishing.

flowchart TD A[Human planners define slingor] -->|Pinned constraints| B[CAIRE knowledge graph] B --> C[Solver adapter constraint evaluation] C -->|Candidate deltas| D[Diff view & KPIs] D -->|Approve| E[Published schedule] E -->|Execution feedback| B D -->|Reject| F[Manual edit sandbox] sequenceDiagram participant Planner participant CAIRE participant Solver participant Field Planner->>CAIRE: Pin slingor & soft limits CAIRE->>Solver: Provide constraints + history Solver-->>CAIRE: Scored candidate + score deltas CAIRE-->>Planner: Diff view + explainability Planner->>CAIRE: Approve hybrid plan CAIRE->>Field: Publish & monitor execution Rasmussen et al. 2022 Eveborn et al. 2006 Solomon 1987 Deb 2001 (MOO)

Home-care scheduling is not one optimization problem. It is a composition of six NP-hard problems , each already difficult on its own. Together, they create a problem of extreme combinatorial difficulty.

Find the shortest route visiting a set of locations once. Complexity grows as N! . For caregivers: "in which order should I visit these 14–25 clients?" Even 25! ≈ 1.55 × 10²⁵ permutations → intractable.

Assign multiple routes to multiple workers. Score workload and travel, evaluate shift bounds, and represent spatial fragmentation. Home care uses VRP with Time Windows (VRPTW) , one of the most challenging variants in operations research.

Determine which caregivers work which shifts with labor law, union rules, breaks, maximum weekly hours, rest periods, and weekend fairness. Crew scheduling alone is NP-hard.

Match the right caregiver to each visit. Constraints include skills, certifications, continuity ("same caregiver as usual"), geographic zones, and cultural preferences. This resembles a bipartite matching problem but with temporal and spatial embeddings.

Each visit has earliest start, latest start, optional soft windows, and duration. Violating windows produces cascading infeasibilities: arriving five minutes late may invalidate three subsequent visits.

Home care optimizes many contradictory objectives: travel time, continuity, fairness, overtime, idle time, distance, zoning, emergency capacity, and stability. No scalar function can perfectly represent all trade-offs.

Logistics companies (e.g., UPS, DHL) solve routing problems, but home care introduces unique factors that make it exponentially more complex:

Home care is not "delivery routing with people." It is a multi-layered human-service optimization problem.

Human planners are exceptionally skilled at:

• Understanding client relationships
• Encoding tacit rules ("she prefers Anna on Tuesdays")
• Geographic intuition ("that elevator is always slow")
• Maintaining stable weekly patterns

But humans cannot:

• Systematically compare many possible schedules
• Systematically score travel-time tradeoffs
• Reassess a plan after inputs change
• Balance fairness scores mathematically
• Compute cascading time window effects

A human planner can consider a limited number of local swaps at once. A solver supports systematic comparison across a broader candidate set.

Solvers are exceptional at:

• Large-neighborhood search
• Constraint satisfaction
• Configured candidate scoring
• Mathematical fairness
• Recomputation after changed inputs

But solvers cannot:

• Understand patient relationships
• Interpret contextual history
• Reason about unstructured qualitative constraints
• Encode tacit local knowledge
• Assess political or emotional implications of caregiver assignment

The solver's feasible region S does not fully overlap with the human feasible region H . Their intersection H ∩ S identifies candidates that still require planner review.

CAIRE's scheduling architecture combines human and machine strengths in three phases:

Humans define stable baselines Continuity and qualitative constraints embedded Solver evaluates configured legal and feasibility constraints for planner review

• Humans define stable baselines
• Continuity and qualitative constraints embedded
• Solver evaluates configured legal and feasibility constraints for planner review

Compares alternatives against configured constraints Scores travel against configured weights Scores workload against configured weights Reports hard- and soft-time-window results Includes new clients supplied as planning inputs Evaluates configured lunch and overtime constraints

• Compares alternatives against configured constraints
• Scores travel against configured weights
• Scores workload against configured weights
• Reports hard- and soft-time-window results
• Includes new clients supplied as planning inputs
• Evaluates configured lunch and overtime constraints

Review these tradeoffs: stable patterns, continuity, travel, service time, workload, and unassigned visits for the current planning run.

• When disruptions occur (sickness, delays, cancellations, urgent add-ons)
• A new run produces candidates for the remaining visits
• Compares changes against the human-designed structure

Peer-reviewed studies describe the problem class and established optimization methods. They do not establish a generic customer outcome for Caire:

Client-facing time and paid shift time Travel time and waiting time Continuity per client Overtime and other hard constraints Unassigned visits and their reasons

• Client-facing time and paid shift time
• Travel time and waiting time
• Continuity per client
• Overtime and other hard constraints
• Unassigned visits and their reasons

Rasmussen et al. (2022). Home Care Scheduling Problem – A Review. Eveborn et al. (2006). Optimization of Home Care Planning and Scheduling. Solomon (1987). VRPTW Algorithms. Ernst et al. (2004). Scheduling and Rostering Review. Deb (2001). Multi-Objective Optimization.

• Rasmussen et al. (2022). Home Care Scheduling Problem – A Review.
• Eveborn et al. (2006). Optimization of Home Care Planning and Scheduling.
• Solomon (1987). VRPTW Algorithms.
• Ernst et al. (2004). Scheduling and Rostering Review.
• Deb (2001). Multi-Objective Optimization.

Run alternatives from the same frozen source snapshot and compare:

• Client-facing time and paid shift time
• Travel time and waiting time
• Continuity per client
• Overtime and unassigned visits

Interpret each comparison in the context of the operation's own data, constraints, and planning period:

• Compare like-for-like source snapshots
• Keep hard constraints fixed across alternatives
• Review tradeoffs before publishing
• Record the measured result for the current run

Important: Caire does not promise a generic effect. The operation's own data and constraints determine the result, and a planner reviews every candidate before publication.

Scalability and solve time should be verified for the current operation:

The research provides background for evaluation; customer-specific claims require results measured on the customer's own planning data.

• Test the operation's current visit and employee volume
• Use the configured service areas and planning period
• Include the operation's actual constraints
• Report solve time together with solution quality

When evaluating solver adapters for home-care scheduling, consider the operation's own planning data, constraints, and review workflow:

Look for: Travel comparison: Compare candidates against the same frozen source snapshot Balanced workload distribution: No caregiver should be systematically over- or under-loaded On-time arrival rates: Measure each candidate against the same source schedule Continuity and travel: Compare both measures and their tradeoff for the current run

• Travel comparison: Compare candidates against the same frozen source snapshot
• Balanced workload distribution: No caregiver should be systematically over- or under-loaded
• On-time arrival rates: Measure each candidate against the same source schedule
• Continuity and travel: Compare both measures and their tradeoff for the current run

The engine should handle:

Measure the solve time and solution quality for each run, then let the planner review the candidate before publishing.

• New visits dropped during the day
• Cancellations or overruns of visit durations
• Priority visits added as new planning inputs
• Caregiver absences or delays

During evaluation, test: The operation's current visit volume The operation's current employee and service-area scope Complex constraints and multi-day scheduling Multi-objective optimization with multiple competing goals

• The operation's current visit volume
• The operation's current employee and service-area scope
• Complex constraints and multi-day scheduling
• Multi-objective optimization with multiple competing goals

Home care requires more than basic routing. Key capabilities include:

Consider both: Job-to-route computation time: Measure it for the current data volume and planning period Consistency under load: Performance should not degrade significantly at high volumes Changed-input run: Start a new run and review its solution quality when inputs change

• Job-to-route computation time: Measure it for the current data volume and planning period
• Consistency under load: Performance should not degrade significantly at high volumes
• Changed-input run: Start a new run and review its solution quality when inputs change

Route engines can calculate a single path between two points, but they do not evaluate a complete home-care schedule against configured constraints:

Solver adapters support these multi-constraint, multi-objective planning problems and produce complete candidate schedules for planner review, not just individual paths.

• Assign visits across many caregivers
• Evaluate configured skills or time-window constraints
• Rebalance workloads
• Produce complete multi-stop plans for the configured scope
• Start a new run when planning inputs change

Home-care scheduling is not merely difficult. It is computationally explosive , combining multiple NP-hard problems into a changing operational challenge.

Neither humans nor solvers can handle the entire complexity alone.

A planner-guided workflow combines stable human structures with solver-generated alternatives and explicit review.

This is the foundation of CAIRE's scheduling model: clear constraints, comparable candidates, and planner-controlled publication.

• Humans provide continuity, context, and qualitative insight.
• Solvers provide systematic candidate comparison, constraint evaluation, and fairness measures.

The TSP seeks the shortest tour that visits every location once. Its search space grows as n!, making brute force impossible even for 50 stops. Every caregiver effectively solves a TSP-like sub-problem daily.

VRPTW extends TSP to multiple routes with earliest and latest service times. Swedish municipalities often require two overlapping windows per client, fracturing the feasible region into thousands of micro pockets.

HHCRSP combines routing, staff assignment, skills, continuity, and labor regulations. It is recognized as one of the hardest NP-hard problems because every constraint interacts with geography and human relationships.

Home-care planning weighs client-facing time, travel, continuity, overtime, and fairness. These goals conflict, so optimization methods compare configured weighted objectives instead of relying on a single static formula.