Supportive care provided **at the patient's home**

**alternative to traditional**institutional care- e.g., hospitalization or nursing homes

- advantages
**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**.

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**.

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.

- a

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.

- a

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

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.

- first:

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**).

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]

- Sweden [Eveborn

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.

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).

**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]$.

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$ |

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$ |

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.

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**).

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

On a horizon perspective

- we can limit the number of
**consecutive working days**by posting aon the $isWorking$ variables,`sequence`

constraint **objectives**are defined as aggregation of daily costs,- days represent a
**natural decomposition**of the problem.

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.

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}^{+} $$

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.

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} $$

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}$.

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 $$

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} $$

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.

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} $$

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.

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$).

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$.

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,
- look-ahead propagator.

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}$.

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.

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.

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*,

- number of caregivers chosen with
- 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*.

- the next route to extend is the

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.

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**.

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
*delta*s right for real-world problems,

- many solutions are
- but we can use a CP model to filter out
- infeasible solution, with the
**essential**constraints, - bad solutions, by adding constraints on the cost.

- infeasible solution, with the

Adding **side constraints** is straightforward.

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.

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.

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.

analysis

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

- The problem was modeled in Gecode (v4.2)
- available (MIT license) at https://bitbucket.org/satt/homecare

- LNS approach implemented as a Gecode meta-engine
**general purpose**(works on any model)- black box, or customizable
- available (MIT license) at https://bitbucket.org/tunnuz/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,

- operations to execute

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.

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.

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.