## Home care

Supportive care provided at the patient's home

• alternative to traditional institutional care
• e.g., hospitalization or nursing homes
• cost effective, e.g., no need to allocate resources,
• easier to accept for the patient (known environment),
• more comfortable no need to move the patient.
• studied in operations research since the late '90s.

## A routing problem

Home care activities are carried out by caregivers, who travel from patient to patient delivering services

• health care, e.g., medications, physiotherapy, or
• daily activities, e.g., bedding, meals, walk, etc.
• possibly requiring more than one caregiver.

The problem has a significant vehicle routing component.

The temporal nature of the services makes it a variant of the vehicle routing problem with time windows.

## Activities

In this paper we consider a multi-day home care scheduling formulation

• a horizon $\mathcal{H} = \{0, \dots, H-1\}$ of $H$ working days,
• each day $d \in \mathcal{H}$ has a set $\mathcal{A_d} = \{1, \dots, n_d - 1\}$ of activities,
• each activity $a$ is defined by,
• a location $(lat_a, long_a)$ (the patient's house),
• a time window $[\sigma_a,\epsilon_a]$ in which they must be served,
• a duration $d_a$,
• a number $r_a$ of caregivers, needed to fulfil the activity.

## Caregivers

In order to carry out the activities, we have

• a set $\mathcal{E} = \{0,\dots,E-1\}$ of available caregivers,
• each caregiver $e \in \mathcal{E}$ is defined by
• a starting/ending location $(lat_e, long_e)$
• a working time $[\sigma_{e,d},\epsilon_{e,d}]$ (dependent on the day $d \in \mathcal{H}$)
• a set $\mathcal{A_e}$ of activities compatible with their skills.

Skills are not explicitly represented in the formulation, but rather flattened in the binary compatibility relation $\rho_{e,a}$.

## Objective (informal)

Determine the daily routes of the caregivers

• assignment of activities and arrival times,
• some sets of activities which cannot be completely assigned.

Therefore we seek least-cost solutions

• Goals
• first: minimize number of unscheduled patients,
• second: minimize traveling costs and overtime work.

## Side constaints

In addition, we have a number of side constraints

• maximum consecutive days

a caregiver may not work more than $k$ consecutive working days ($k$ is the same for every caregiver),

• minimum working hours

a caregiver must work at least $\underline{t}_{e,d}$ hours on a day, or skip it,

• maximum working hours

a caregiver must not work more $\overline{t}_{e,d}$ hours on a day, or skip it (soft, minimize overtime).

## Context

This formulation is the result of real-world requirements collected and provided to us by EasyStaff S.r.l.

Related work, various formulations since [Cheng & Rich, 97]

• mostly single-day, except [Nickel et al., 2012]
• focus on matching one nurse to one patient,
• a lot of works on real-world health care systems
• Sweden [Eveborn et al., 2005]
• Denmark [Rasmussen et al., 2010]
• Austria [Hirsch et al., 2011], [Rendl et al., 2012]
• Germany and Netherlands [Nickel et al., 2012]

## Model

We model the problem as a rich vehicle routing problem.

Two classes of constraints

• constraints in a day perspective,
• constraints in a horizon perspecitve.

The days can be treated separately as far as routing is concerned.

However resource allocation and costs must be considered in a horizon perspective.

## Activity graph

We map the problem on a directed graph $G = \langle V,E\rangle$

• each activity $a$ is represented by $r_a$ nodes, where $r_a$ is the number of needed caregivers,
• each caregiver $e \in \mathcal{E}$ has a starting activity $s_e$ and an ending activity $t_e$ (nodes),
• edges weighted proportionally to the driving distance.

A dummy caregiver visits all unscheduled activities $\mathcal{E} \rightarrow \mathcal{E}^{+}$ (penalty).

## Model, activity graph

Time windows are attached to each node

• Times are discretized by a parameter $\gamma$, e.g., 10 minutes (durations are given in the same unit).
• For the starting and ending activities the time windows coincide with the caregivers' working hours, e.g., $[7/\gamma,18/\gamma]$.
• For the regular activities the time windows coincide with the service time specified in the input, e.g., for a lunch activity $[12/\gamma, 14/\gamma]$.

## Essential activity variables

A solution assigns the following essential decision variables to each (artificial) activity $a \in V$, for each day $d \in \mathcal{H}$

Variable Domain Meaning
$start_a$ $[0,24/\gamma]$ start of activity $a$
$succ_a$ $V$ activity after $a$
$caregiver_a$ $\mathcal{E}^{+}$ caregiver carrying out $a$

The following additional variables are defined for each activity $a \in V$, for each day $d \in \mathcal{H}$

Variable Domain Meaning
$end_a$ $[0,24/\gamma]$ end of activity $a$
$duration_a$ $[0,24/\gamma]$ duration of activity $a$
$pred_a$ $V$ activity before $a$ (redundant)
$slack_a$ $[0,24/\gamma]$ time between arrival at $a$ and $start_a$

## Caregiver variables

Similarly, many objectives are defined in a caregiver perspective, thus for each caregiver $e \in \mathcal{E}$, we define the following variables for each day $d \in \mathcal{H}$

Variable Domain Meaning
$worktime_e$ $[0,24/\gamma]$ total working time of $e$ in $d$
$overtime_e$ $[0,24/\gamma]$ total overtime of $e$ in $d$
$isWorking_e$ {$0, 1$} time between arrival at $a$ and $start_a$

## Day variables

Finally, for each day $d \in \mathcal{H}$ we define the following variables

Variable Domain Meaning
$unscheduled$ $[0,\dots,n_d]$ # unscheduled activities in $d$
$distance$ $[0,\dots,n_d]$ distance traveled in $d$
$cost$ $[0,\dots,n_d]$ overall cost in $d$

The cost is an economic function of the traveled distance, the overtime work, the number of unscheduled activities, and the slack time.

## Solution representation

A solution, in a daily perspective, is a Hamiltonian circuit over $G$, defined on the $succ$ (and $pred$) variables.

Modeled with circuit global constraint (good propagators).

## Solution initialization

The solution is primed by connecting each caregiver's ending location with the following caregiver's starting location.

## Horizon perspective

On a horizon perspective

• we can limit the number of consecutive working days by posting a sequence constraint on the $isWorking$ variables,
• objectives are defined as aggregation of daily costs,
• days represent a natural decomposition of the problem.

## Constraints

The constraints can be organized in

• essential constraints, which define the search space, and
• redundant constraints, e.g., symmetry breaking, which make the tree-search process more efficient.

In the following, the $d$ subscript is omitted when clear form the context.

## Routing

First we start establish the relation between the $succ$ and $pred$ variables by using two element constraints

$$\mathbf{element}(pred, succ_i) = i, \forall i \in V \\ \mathbf{element}(succ, pred_i) = i, \forall i \in V$$

then, the we link ending and starting locations (initialization)

$$succ_{t_e} = s_{e+1 \; \text{mod} \; E+1}, \forall e \in \mathcal{E}^{+} \\ pred_{s_e} = t_{e-1 \; \text{mod} \; E+1}, \forall e \in \mathcal{E}^{+}$$

## Routing

Finally, we force the $succ$ and $pred$ variables to define two Hamiltonian circuits, through the circuit global constraint

$$\mathbf{circuit}(succ, \mathcal{TD}, forwardDistance) \\ \mathbf{circuit}(pred, \mathcal{TD}, backwardDistance)$$

where $\mathcal{TD}$ is the distance matrix (possibly asymmetric), and the $*Distance$ variable arrays contain the distances of the selected edges.

## Caregivers

We assign each caregiver to her starting and ending activities

$$caregiver_{s_e} = e, \forall e \in \mathcal{E}^{+} \\ caregiver_{t_e} = e, \forall e \in \mathcal{E}^{+} \\$$

we then propagate the caregiver along each route (only for real activities)

$$\mathbf{element}(caregiver, succ_a) = caregiver_a, \forall a \in \mathcal{R} \\ \mathbf{element}(caregiver, pred_a) = caregiver_a, \forall a \in \mathcal{R}$$

## Caregivers

Some caregivers are not entitled to execute some activities, e.g., injections, or physiotherapy.

Incompatibility is encoded in a binary function $\rho: \mathcal{E}^{+} \times \mathcal{R} \rightarrow$ {$0, 1$}

$$\rho_{a,e} = 0 \implies caregiver_a \ne e, \forall a \in \mathcal{R}, e \in \mathcal{E}^{+}$$

Note that $\rho_{a,E} = 1, \forall a \in \mathcal{R}$.

## Unscheduled activities

We keep track of the number of unscheduled activities through a count constraint on number of activities whose caregiver is the dummy

$$\mathbf{count}(caregiver, E, unscheduled)$$

the total distance traveled is computed from $forwardDistance$ and a binary test on the dummy caregiver

$$distance = \sum_{i \in V} (caregiver_i \ne E) \cdot forwardDistance_i$$

## Time constraints

The time constraints are conditional to an activity being served by a real caregiver.

For the dummy route, all the time variables ($start$, $duration$, and $slack$) are $0$ on the path.

$$caregiver_a = E \implies start_a = 0 \land slack_a = 0 \land duration_a = 0, \; \forall a \in \mathcal{R} \\ caregiver_i \ne E \implies start_i \geq \sigma_i \land end_i \leq \epsilon_i, \; \forall i \in V$$

Moreover, the $start$, $slack$, $end$, and $duration$ variables are connected by the relation

$$end_a = start_a + duration_a + slack_a, \; \forall a \in \mathcal{R}$$

## Time constraints

The $duration$ and $slack$ are set to $0$ for starting and ending nodes

$$duration_i = 0 \land slack_i = 0, \; \forall i \in \mathcal{S} \cup \mathcal{T}$$

Then we setup the time chain along each route

$$\mathbf{element}(start, succ_i) = start_i + (caregiver_i \ne E) \cdot \\(duration_i + slack_i + \mathbf{element}(\mathcal{TT}, i, succ_i)), \; \forall i \in \mathcal{S} \cup \mathcal{R}$$

where $\mathcal{TT}$ is the matrix of traveling times.

## Time constraints

The $worktime$ and $overtime$ variables are tied to the caregivers

$$worktime_{e,d} = start_{t_{e,d}} - start_{s_{e,d}}, \; \forall e \in \mathcal{E}, d \in \mathcal{H} \\ overtime_{e,d} = max(0, worktime_{e,d} - \overline{t}_{e,d}), \; \forall e \in \mathcal{E}, d \in \mathcal{H}$$

moreover, we want each caregiver to work at least $\underline{t}_{e,d}$ time units in a day, or not work at all

$$worktime_{e,d} \ge \underline{t}_{e,d} \lor worktime_{e,d} = 0, \; \forall e \in \mathcal{E}$$

## Split activities

Activities that require multiple operators are splitted.

The following constraint synchronize them

$$\mathbf{nvalues}(start_{a,\dots,a+r_a-1},1), \; \forall a \in \mathcal{R}^{*} \\ \mathbf{nvalues}(duration_{a,\dots,a+r_a-1},1), \; \forall a \in \mathcal{R}^{*}$$

where $\mathcal{R}^{*}$ is the set of activities except replicas.

## Split activities

Moreover, we require all the replicas or none of them to be scheduled on regular caregivers, this is accomplished by the following count constraint

$$\mathbf{count}(caregiver_{a,\dots,a+r_a-1}, \mathcal{E}, regularCaregivers_a), \; \forall a \in \mathcal{R}^{*}$$

where $dom(regularCaregivers_a) =$ {$0, r_a$} (either zero or $r_a$).

## Horizon constraints

Next we limit the amount of consecutive working days to $k$ with a sequence constraint

$$isWorking_{e,d} \iff worktime_{e,d} > 0, \; \forall e \in \mathcal{E} \\ \mathbf{sequence}(isWorking_{e,d \in \mathcal{H}}, 1, h, wd), \; \forall e \in \mathcal{E}$$

where $dom(wd) =${$0,\dots,k$}, thus allowing sequences of at most $k$ ones in the $isWorking_e$ arrays of length $d$.

## Redundant constraints

Constraints targeted at making the search faster, e.g.,

• activities with non-overlapping time windows can be statically ordered (by disallowing certain assignments to $succ$),
• activities such that $caregiver_i \ne E$ and $start_i > end_j$ can be dynamically ordered (by disallowing certain assignments to $succ$),
• if a caregiver $d$ is not working on day $d$, then $succ_{s_e} = t_e$,
• (symmetry breaking) order activities assigned to the dummy caregiver,

We implemented a special one-step look-ahead propagator that

• looks at the possible $j \in dom(succ_i)$ of activity $i \in \mathcal{R}$,
• considers the distance of $j$ from the final depot $t$,
• prunes from $succ_i$ all the values $j$ for which it is not possible to reach $t$ within the time limit $\epsilon_{e,d}$.

## Cost constraints

The cost is a linear combination of the daily metrics.

The cost components involve

• unscheduled activities, which contribute 100 €/ea to the cost,
• overtime, which contribute 25 €/h to the cost,
• slack, which contribute 25 €/h to the cost,
• distance, which contribute 0.30 €/km to the cost.

## Search

Our search strategy consists of

• a custom branching strategy to explore the search space as defined by the model, and
• a large neighborhood search (LNS) defined on top of the model.

The branching strategy can be used to solve the problem with plain branch & bound, which we use as a baseline to compare the performance of LNS.

## Branching strategy

The days are processed in order.

• First the caregivers working on $d$ are chosen,
• number of caregivers chosen with median first strategy,
• working caregivers chosen uniformly at random,
• then the activity schedule is determined according to the following scheme
• the next route to extend is the shortest one (order breaks ties),
• the next activity to add is chosen according to heuristics.

## Heuristics

The next activity is chosen according to (in order of priority)

• prefer regular nodes over ending nodes,
• prefer incomplete split activities,
• prefer activities with earliest end,
• prefer shorter activities,
• prefer activities with earliest start,
• prefer activities with highest number of needed caregivers.

## Finalization

Once all the routes for the regular caregivers have been set, the remaining activities are assigned to the dummy caregiver.

This step is deterministic because of the ordering of the unscheduled activities, and this is a single step.

## Large neighborhood search

A neighborhood search meta-heuristic

• large neighborhoods often lead to solutions of higher quality,
• exploring large neighborhoods is demanding
• many solutions are infeasible or bad,
• difficult to get deltas right for real-world problems,
• but we can use a CP model to filter out
• infeasible solution, with the essential constraints,

## Large neighborhood search

CP-based LNS starts from an initial complete solution, then alternates

• a destroy step, which relaxes a fraction of the solution,
• as a black-box: random destroy step,
• in practice: to obtain good performance, ad-hoc destroy step,
• a repair step, which re-optimizes the (now) smaller problem
• a tree-search, e.g., branch & bound, on the model.

## Destroy step

Our destroy relaxes all the variables of $\delta \in$ {$1,\dots,H$} days at each iteration, following an adaptive scheme

• at the beginning $\delta = \delta_{init} = 1$,
• once a maximum number $ii_{max}$ of non-improving iterations has been executed, $\delta$ is increased,
• if a new optimum is found, $\delta$ is reset to $\delta_{init}$,
• if $ii_{max}$ iterations have been spent at $\delta = h$, the search is restarted.

## Repair step

Our repair step runs a branch & bound search on the defined model, using the described brancher (which is also used to find the initial solution).

At each repair step, the cost is constrained to be $\le$ of the cost of the best solution so far (in order to allow escaping from plateaux).

The repair step is given a timeout proportional to the number of the free variables.

## Experimental analysis

We compared the performance of pure branch & bound over our model with the performance of the described LNS approach

## Gecode-LNS

• initial_solution_branching, initial branching strategy,
• neighborhood_branching, repair step branching,
• relax, the destroy step,
• relaxable_vars, the total number of relaxable vars,
• improving, the solution acceptance criterion,
• constrain
• operations to execute before repair go here,
• typically used to constrain the solution,

## Instances

Generated randomly, by varying a number of parameters

• number of activities,
• horizon length,
• operation area (coordinates),
• number of operators per activity (parameter $k$ for Poisson distribution),
• correction rate on upper bound of needed caregivers,
• probability of shift,
• probability of incompatibility.

## Instances

We generated a pool of $540$ instances, organized in $18$ families with different horizon length ($3$ or $6$ days) number of activities ($20$, $30$, or $40$), and caregiver correction rate ($0.6$, $0.7$ or $0.8$).

The maximum consecutive working days was set to $h-1$, and the operation area is a square of $40 \times 40$ Km centered around Udine.

The parameters of LNS were automatically tuned using F-Race on a pool of $360$ instances, while the remaining $180$ were used as validation set. A timeout of 10 minutes was given both to tuning and validation.

## Results

The LNS approach outperformed pure branch & bound on $17$ over $18$ instance families, systematically improving the cost incurred for unassigned activities, overtime, and slack time.

The overall cost was, on average, $38\%$ smaller than branch & bound.

Pure branch & bound, on the other hand, achieved generally superior performance regarding the minimization of traveling distances, however leaving several activities unscheduled.

See Di Gaspero, L. & Urli, T. (2014). A CP/LNS approach for Multi-day Homecare Scheduling Problems for detailed results.