# A Robust Home Health Care Scheduling and Routing Approach with Time Windows and Synchronization Constraints Under Travel Time and Service Time Uncertainty

Salma Makboul, Said Kharraja, Abderrahman Abbassi, Ahmed El Hilali Alaoui

<figure><img src="image_1.png" /></figure>

## To cite this version:

Salma Makboul, Said Kharraja, Abderrahman Abbassi, Ahmed El Hilali Alaoui. A Robust Home Health Care Scheduling and Routing Approach with Time Windows and Synchronization Constraints Under Travel Time and Service Time Uncertainty. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.391-402, 10.1007/978-3-030-85902-2_42. hal-04117700

HAL Id: hal-04117700

https://inria.hal.science/hal-04117700

Submitted on 5 Jun 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_3.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# A Robust Home Health Care Scheduling and Routing Approach with Time Windows and Synchronization Constraints under Travel Time and Service Time Uncertainty

Salma Makboul¹(✉), Said Kharraja², Abderrahman Abbassi³, and Ahmed El Hilali Alaoui⁴

¹ Modelling and Mathematical Structures Laboratory, FST Fez, SMBA University, Morocco salma.makboul@usmba.ac.ma

² University of Lyon, UJM-Saint-Etienne, LASPI, Roanne, France

³ Faculty of Sciences, Marrakesh, Morocco

⁴ Euromed University 32 Rue Meknes, Fez, Morocco

**Abstract.** Home health care (HHC) services represent a set of medical services given to patients at their homes. The patients require a set of care that must be coordinated and treated by skilled caregivers corresponding to their needs. This study proposes an HHC routing and assignment approach based on a mixed-integer linear programming model that aims to minimize total route cost. The HHC approach takes into account a set of HHC specific constraints and criteria. Secondly, we propose a new robust counterpart HHC model under uncertainty based on the well-known budgeted uncertainty set. The robust counterpart HHC model deals with travel and service times uncertainty. The computational results compare the deterministic model with its robust counterpart model. The small and medium instances have been solved using TSP benchmarks with specific data concerning HHC problems. The models have been implemented using ILOG CPLEX Optimization Studio. The computational results of small and medium instances indicated the efficiency of the proposed approach. Robustness analysis of the obtained results was conducted using a Monte Carlo simulation and indicated the price of robustness. The increase of route cost in comparison with the risk of infeasibility shows the importance of the designed robust routes for HHC routing and scheduling problems.

**Keywords:** Home health care · Uncertainty · Mixed integer linear programming · Routing problem · Precedence constraints · Synchronization constraints

## 1 Introduction

Home health care (HHC) services are characterized as medical and paramedical services given to patients at home [7]. The patients may have various kinds of required care. Besides, the main benefit of HHC services is the reduction of the hospitalization rate [12]. Reports from the world health organization (WHO) have also suggested that elderly patients tend to receive medical treatment at home rather than traditional hospital care [9]. Due to the costly long-term stay in hospitals [4], it is preferable to let
the patients stay as long as possible in their own homes. The routing and scheduling HHC problem is an extension of the vehicle routing problem (VRP) with specific side constraints that make the HHC problem more challenging to solve [5]. The problem consists of scheduling the patients according to the treatment and care needed and caregiver skills. The patient may have specific requests such as gender, language, and so on. [5]. The caregivers must visit the patients within their time window because they may not be available all day. Besides, some patients may need more than one care, and the set of care must be coordinated [17,14]. Sometimes, care required by some patients can involve the presence of more than one caregiver at the same time, which corresponds to the simultaneous synchronization of care [11]. The vast majority of the studies considered knowing the route travel time value in advance, but what happens is the opposite. The travel time can be affected by weather, traffic congestion, stop-and-go movement, and so on. Hence, we also must take into account the uncertainties to build efficient planning. The service time is related to the skill of caregivers and expertise or patient health. Therefore, the service time can also be affected by uncertainties.

The HHC problem has been the subject of several studies in the literature. For recent reviews of the HHC planning and scheduling problems, the reader is referred to [5,8,15]. The HHC process is divided into three decision levels: long-term strategic [2], tactical medium-term, and operational short-term. We cite some papers dealing with the operational level, which refers to the routing and assignment problems [5] and take into consideration the uncertainties. The assignment problem seeks to allocate nurses to patients while considering their skills and workload balancing. The problem of assignment and routing involves scheduling and assigning patient visits to caregivers. The main objective is to define the order and the time during which visits should be carried out [7]. [17] presented modeling for the constrained problem as a fixed partitioning issue and built a “branch and price” algorithm to solve it. Later, [4] presented a mixed-integer linear programming (MILP) model to balance caregivers’ workloads and to decrease the waiting time between consecutive visits and considered the concept of pattern. Only a few studies take into account the uncertain factors relevant to the HHC [5]. [10] presented a stochastic setting where uncertainty occurs regarding where and when prospective patients require treatment. Later, [1] proposed a robust optimization (RO) approach for HHC in the chemotherapy context. [18] presented a model for the daily HHC routing and scheduling problem by taking into account travel and service time uncertainty from the RO perspective. In this study, we first propose an MILP model for the deterministic HHC problem to minimize route cost and take into consideration a set of HHC constraints: Time window, the precedence of care, the synchronization of care, the consistency between caregivers’ skill and patients’ requirement, caregivers lunch breaks, workload restrictions, and coordination between the patients assigned to each caregiver. Secondly, we propose a robust counterpart HHC model that aims to find the “robust” routes traveled by the caregivers. The robust HHC problem refers to the scheduling that represents the minimal cost that increases the chances of having a route feasible in practice when the travel and service times are subject to uncertainty. The routing problem considers travel and service times uncertainties and the most realistic scenario; not all the travel and service times will deviate from their nominal values. To the best of our knowledge, we are the first to study this case on an HHC decision system with a time window and synchronization constraints.
We will evaluate how much it will cost to have the routes of the caregivers feasible in practice. The robust model is inspired by the novel robust counterpart vehicle routing problem with time window (VRPTW) presented in [16] based on the well-known budgeted uncertainty set introduced by [3]. The remainder of this paper is presented as follows. Section 2 presents the proposed deterministic model that aims to minimize route costs. Section 3 describes a brief review of the robust optimization (RO) and defines the robust counterpart under travel and service times uncertainties. The computational results are presented in Sect. 4, the deterministic and robust solutions are compared. Finally, Sect. 5 concludes the paper with conclusions and perspectives.

## 2 Problem Description and Mathematical Modeling

We consider a set of patients requiring a heterogeneous set of care. The HHC organization operates in a single area. The planning includes several constraints related to the HHC problems: Time window, the precedence of care, the synchronization of care, the consistency between caregivers' skill and patient requirement, caregivers lunch breaks, workload restrictions, and coordination between the patients assigned to each caregiver. The caregivers have three grades (advanced, medium, and usual skills). The assignment is done according to the required skill (i.e., a caregiver having "grade 2" can be assigned to a patient requiring medium skill and less). Each care has a service time. The care has an order that must be respected which refers to the precedence synchronization [11]. Without loss of generality, we consider the case where at most two caregivers can be required by a patient simultaneously. We first propose the following deterministic MILP, which aims to minimize route cost. A complete directed network $G = (I, E)$ is considered. $E$ defines the set of arcs, and $I$ corresponds to the cares of the patients. Each caregiver starts its tour from node 0 and ends it at node 0, referring to the HHC structure (depot). The lunch break is also referred to as dummy care (node 1) in the model. Therefore, each caregiver should visit care 1.

### Parameters

<table><tr><td>K</td><td>Set of caregivers</td><td>M</td><td>High value</td></tr><tr><td>S</td><td>Set of cares that require two caregivers ($S \subset I$)</td><td>sp<sub>i</sub></td><td>Skill required by the care i</td></tr><tr><td>s<sub>i</sub></td><td>Service time at care i</td><td>sk<sub>k</sub></td><td>Skill of the caregiver k</td></tr><tr><td>t<sub>ij</sub></td><td>Traveling time from node i to node j, $(i, j) \in E$</td><td>c<sub>ij</sub></td><td>Route cost between care i and care j</td></tr><tr><td>[A<sub>i</sub>, B<sub>i</sub>]</td><td>Respectively the earliest and the latest service time for the care i</td><td>I<sub>i</sub></td><td>Is 1 if the care i requires one caregiver and 2 if it requires two caregivers</td></tr><tr><td>MAXWL</td><td>The maximum daily workload for the caregivers</td><td>ord<sub>i</sub></td><td>Order of precedence of care i (if care i has to be planned before care j we have ($ord_i \ge ord_j$))</td></tr></table>

### Objective function

$$ \min \sum_{(i,j) \in E} \sum_{k \in K} x_{ijk}c_{ij} \qquad (1) $$
Constraints

$$ \sum_{k \in K} y_{ik} = I_j \quad \forall j \in I \mid j \neq 0, j \neq 1 \qquad (2) $$

$$ \sum_{j \in I \mid j \neq 0} x_{0jk} \leq 1 \quad \forall k \in K \qquad (3) $$

$$ \sum_{j \in I \mid j \neq 0} x_{j0k} \leq 1 \quad \forall k \in K \qquad (4) $$

$$ \sum_{j \in I \mid j \neq 1} x_{1jk} \leq 1 \quad \forall k \in K \qquad (5) $$

$$ \sum_{j \in I \mid j \neq 1} x_{j1k} \leq 1 \quad \forall k \in K \qquad (6) $$

$$ y_{jk} = \sum_{i \in I \mid i \neq j} x_{ijk} \quad \forall k \in K \quad \forall j \in I \qquad (7) $$

$$ y_{0k} = 1 \quad \forall k \in K \qquad (8) $$

$$ y_{1k} = 1 \quad \forall k \in K \qquad (9) $$

$$ \sum_{i \in I} x_{ijk} = \sum_{i \in I} x_{jik} \quad \forall k \in K \quad \forall j \in I \mid j \neq 0, j \neq 1 \qquad (10) $$

$$ \mathrm{ord}_i \geq \mathrm{ord}_j x_{ijk} \quad \forall k \in K \quad \forall (i, j) \in E \mid j \neq 0, i \neq 0, i \neq 1, j \neq 1 \qquad (11) $$

$$ y_{jk} = 0 \quad \forall k \in K \quad \forall j \in I \mid sp_j > sk_k, j \neq 0, j \neq 1 \qquad (12) $$

$$ AT_{jk} \geq A_j \quad \forall k \in K \quad \forall j \in I \mid j \neq 0, j \neq 1 \qquad (13) $$

$$ AT_{jk} \leq B_j \quad \forall k \in K \quad \forall j \in I \mid j \neq 0, j \neq 1 \qquad (14) $$

$$ AT_{jk} = AT_{jk'} \quad \forall k, k' \in K \quad \forall j \in S \qquad (15) $$

$$ RT_{jk} \leq MAXWL \quad \forall k \in K \quad \forall j \in I \mid j \neq 0, j \neq 1 \qquad (16) $$

$$ AT_{jk} \geq AT_{ik} + (s_i + t_{ij})x_{ijk} - (1 - x_{ijk})M \quad \forall k \in K \quad \forall (i, j) \in E \mid j \neq 0, j \neq 1 \qquad (17) $$

$$ RT_{jk} \geq RT_{ik} + (s_j + t_{ij})x_{ijk} - (1 - x_{ijk})M \quad \forall k \in K \quad \forall (i, j) \in E \mid j \neq 0, j \neq 1 \qquad (18) $$

$$ RT_{ik} \geq 0, \quad AT_{ik} \geq 0 \quad \forall k \in K \quad \forall i \in I \qquad (19) $$

$$ x_{ijk} \in \{0, 1\}, \quad y_{jk} \in \{0, 1\} \quad \forall k \in K \quad \forall j \in I \quad \forall i \in I \qquad (20) $$

Objective (1) aims to minimize total route cost. Constraint (2) ensures the number of caregivers a care requires. Constraints (3) and (4) guarantee that at most one care can be done after/before the depot 0, respectively. Constraints (5) and (6) ensure that each caregiver has a lunch break (defined as a dummy care). Constraint (7) guarantees that if care is assigned to a caregiver, the care has a successor (linking between routing and assignment variables). Constraint (8) ensures that each caregiver is assigned to the depot (HHC structure). Constraint (9) assigns a lunch break to each caregiver (defined as dummy care). The classical flow conservation restrictions on the routing variables are the (10) constraint. Constraint (11) ensures the priority of cares (precedence synchronization). Constraint (12) guarantees that the care is assigned to the caregiver with the required skill. Constraints (13) and (14) guarantee that the start
time of the care respects the time window of patients. Constraint (15) ensures the presence of two caregivers at the same moment for the care requiring simultaneous synchronization. Constraint (16) ensures that the maximum daily workload of each caregiver, represented as the number of service times and travel times, should be respected. Constraint (17) calculates the arrival time of the caregiver to care. Constraint (18) gives the elapsed time for the caregivers at each node. Constraints (19) and (20) enforce the binary variables of the model and the non-negativity restrictions.

## 3 Robust Formulation

In this section, we propose a modeling that deals with travel time and service time uncertainties. Robust optimization (RO) is an approach that aims to find robust solutions to optimization problems in which the data are uncertain without resorting to probabilistic distribution. RO has seen a resurgence of interest in recent decades with many contributions. Unlike stochastic approaches, RO models uncertain data using continuous or discrete sets of possible values, with no attached probability distribution. The proposed model provides robust solutions which are protected against uncertainty. We adapt the optimization approach developed by [16] inspired by [3] that relatively adds few variables and constraints compared to the duality formulation. We assume that the travel time and service time are uncertain values modeled as independent random variables $\tilde{t}_{ij}$ and $\tilde{s}_i$. The random variables fall within the symmetric and bounded ranges defined as follows: $\tilde{t}_{ij} \in [\tilde{t}_{ij} - \tilde{t}_{ij}, \tilde{t}_{ij} + \tilde{t}_{ij}]$ (where $\tilde{t}_{ij}$ is the nominal travel time value and $\tilde{t}_{ij}$ its deviation ($\tilde{t}_{ij} \ge 0$)) and $\tilde{s}_i \in [\tilde{s}_i - \tilde{s}_i, \tilde{s}_i + \tilde{s}_i]$ (where $\tilde{s}_i$ is the nominal service time value and $\tilde{s}_i$ its deviation ($\tilde{s}_i \ge 0$)). The decision variables are assumed to be non-negative. The worst case will always be achieved at the right-hand side of the ranges $[\tilde{t}_{ij} - \tilde{t}_{ij}, \tilde{t}_{ij} + \tilde{t}_{ij}]$ and $[\tilde{s}_i - \tilde{s}_i, \tilde{s}_i + \tilde{s}_i]$. Hence, the ranges do not have to be symmetric. The normalized scale deviations $\epsilon_{ij}^t = \frac{\tilde{t}_{ij} - \tilde{t}_{ij}}{\tilde{t}_{ij}}$ and $\epsilon_i^s = \frac{\tilde{s}_i - \tilde{s}_i}{\tilde{s}_i}$ are random variables in $[0, 1]$ (without loss of generality). The cumulative uncertainty of the random variable is bounded by the budget of robustness $\nabla^t$ and $\nabla^s$ which represents the number of travel time and service times affected by the uncertainties, respectively. The data uncertainty models are represented by the polyhedral uncertainty sets (21) and (22) as follows:

$$ \nu^t = \{ \tilde{t} \in \mathbb{R}_+^{|E|} | \tilde{t}_{ij} = \tilde{t}_{ij} + \tilde{t}_{ij} \epsilon_{ij}^t, \sum_{(i,j) \in E} \epsilon_{ij}^t \le \nabla^t, 0 \le \epsilon_{ij}^t \le 1, \forall (i,j) \in E \} \quad (21) $$

$$ \nu^s = \{ \tilde{s} \in \mathbb{R}_+^{|I|} | \tilde{s}_i = \tilde{s}_i + \tilde{s}_i \epsilon_i^s, \sum_{i \in I} \epsilon_i^s \le \nabla^s, 0 \le \epsilon_i^s \le 1, \forall i \in I \} \quad (22) $$

The budget of uncertainty refers to the number of parameters that are subject to uncertainty. The random variable $\epsilon_{ij}^t$ and $\epsilon_i^s$ are continuous from the interval $[0, 1]$ and the budget of robustness bounds their sum (i.e., some travel and service times take their worst-case value, while others take their expected value). When $\nabla^t = 0$ and $\nabla^s = 0$, it refers to the deterministic case. The large budgets express more conservative solutions. Because of the structure of the uncertainty set, the robustness of a route can be defined explicitly using recursive equations [13].

**Time Window:** $AT_{j\tau\gamma}$ represents the earliest exact time from which the service can
start at node $j$ when up to $\tau$ travel times and $\gamma$ service times reach their worst-case values. The recursion can compute it:

$$AT_{j\tau\gamma} = \begin{cases} A_0, & \text{if } j=0; \\ \max\{A_j, AT_{j-1\tau\gamma} + \bar{s}_{j-1} + \bar{t}_{j-1j}\}, & \text{if } \tau=0 \text{ and } \gamma=0; \\ \max\{A_j, AT_{j-1\tau\gamma} + \bar{s}_{j-1} + \bar{t}_{j-1j}, \\ \quad AT_{j-1,\tau-1,\gamma-1} + \bar{s}_{j-1} + \hat{s}_{j-1} + \bar{t}_{j-1j} + \hat{t}_{j-1j}\}, & \text{otherwise.} \end{cases}$$

To be robust feasible, the route must satisfy:

$$AT_{j\tau\gamma} \le B_j \quad \forall j \in I \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad \forall \tau \in \{0, 1, \dots, \nabla^s\} \quad (23)$$

$AT_{j\tau\gamma}$ is not necessarily given by the largest travel and service times deviations because the care only can start after when the time window of the patient opens.

**Caregiver Workload:** $RT_{j\tau\gamma}$ represents the largest elapsed time when the caregiver leaves node $j$ when up to $\tau$ travel times and $\gamma$ service times reach their worst-case values. It can be computed by the recursion:

$$RT_{j\tau\gamma} = \begin{cases} s_0, & \text{if } j=0; \\ RT_{j-1\tau\gamma} + \bar{s}_j + \bar{t}_{j-1j}, & \text{if } \tau=0 \text{ and } \gamma=0; \\ \max\{RT_{j-1\tau\gamma} + \bar{s}_j + \bar{t}_{j-1j}, RT_{j-1,\tau-1,\gamma-1} + \bar{s}_j + \hat{s}_j + \bar{t}_{j-1j} + \hat{t}_{j-1j}\}, & \text{otherwise.} \end{cases}$$

To be robust feasible, the route must satisfy:

$$RT_{j\tau\gamma} \le MAXWL \quad \forall j \in I \quad \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (24)$$

The robust model is given by replacing constraints (13-19) by constraints (25-33)

$$RT_{jk\tau\gamma} \le MAXWL \quad \forall k \in K \quad \forall j \in I | j \ne 0, j \ne 1 \quad \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (25)$$

$$AT_{jk\tau\gamma} \ge A_j \quad \forall k \in K \quad \forall j \in I | j \ne 0, j \ne 1 \quad \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (26)$$

$$AT_{jk\tau\gamma} \le B_j \quad \forall k \in K \quad \forall j \in I | j \ne 0, j \ne 1 \quad \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (27)$$

$$AT_{jk\tau\gamma} = AT_{jk'\tau\gamma} \quad \forall k, k' \in K \quad \forall j \in S \quad \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (28)$$

$$AT_{jk\tau\gamma} \ge AT_{ik\tau\gamma} + (\bar{s}_i + \bar{t}_{ij})x_{ijk} - (1 - x_{ijk})M \quad \forall k \in K \quad \forall (i, j) \in E | j \ne 0, j \ne 1 \\ \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (29)$$

$$AT_{jk\tau\gamma} \ge AT_{ik\tau-1\gamma-1} + (\bar{s}_i + \hat{s}_i + \bar{t}_{ij} + \hat{t}_{ij})x_{ijk} - (1 - x_{ijk})M \quad \forall k \in K \quad \forall (i, j) \in E | j \ne 0, j \ne 1 \\ \forall \gamma \in \{1, \dots, \nabla^s\} \quad \forall \tau \in \{1, \dots, \nabla^t\} \quad (30)$$

$$RT_{jk\tau\gamma} \ge RT_{ik\tau\gamma} + (\bar{s}_j + \bar{t}_{ij})x_{ijk} - (1 - x_{ijk})M \quad \forall k \in K \quad \forall (i, j) \in E | j \ne 0, j \ne 1 \\ \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (31)$$

$$RT_{jk\tau\gamma} \ge RT_{ik\tau-1\gamma-1} + (\bar{s}_j + \hat{s}_j + \bar{t}_{ij} + \hat{t}_{ij})x_{ijk} - (1 - x_{ijk})M \quad \forall k \in K \quad \forall (i, j) \in E | j \ne 0, j \ne 1 \\ \forall \gamma \in \{1, \dots, \nabla^s\} \quad \forall \tau \in \{1, \dots, \nabla^t\} \quad (32)$$

$$RT_{jk\tau\gamma} \ge 0, \quad AT_{jk\tau\gamma} \ge 0 \quad \forall k \in K \quad \forall j \in I \quad \forall \gamma \in \{0, 1, \dots, \nabla^s\} \quad \forall \tau \in \{0, 1, \dots, \nabla^t\} \quad (33)$$
## 4 Computational Results

The proposed models were implemented with ILOG CPLEX Optimization Studio and performed on Dell computer Intel Xeon CPU E5-2667 v4 3.20 GHz 64 GB RAM using [6] benchmarks, and some generated data specific to HHC problems. The maximum daily workload is fixed to 480 minutes. I.PXCYKZ denotes a given instance I with X patients, Y cares and Z caregivers. The number of required care characterizes each patient. Table 1 presents an example of required care by the patients. (S) refers to cares requiring simultaneous synchronization. (+) denotes if a patient requires care and (-) otherwise. The default values of travel and service times are considered nominal values. The deviations are computed as 0.2 of the default values.

<table><caption>**Table 1.** Data related to instance (1.P10C15K5)</caption><thead><tr><th>Patient</th><th>Care α</th><th>Care β</th><th>Care γ</th></tr></thead><tbody><tr><td>1</td><td>(+)</td><td>(-)</td><td>(-)</td></tr><tr><td>2</td><td>(+)<br>before β</td><td>(+)<br>before γ</td><td>(+)</td></tr><tr><td>3</td><td>(+)<br>before β<br>(S)</td><td>(+)</td><td>(-)</td></tr><tr><td>4</td><td>(+)</td><td>(-)</td><td>(-)</td></tr><tr><td>5</td><td>(-)</td><td>(+)</td><td>(-)</td></tr><tr><td>6</td><td>(-)</td><td>(-)</td><td>(+)</td></tr><tr><td>7</td><td>(+)<br>before β</td><td>(+)</td><td>(-)</td></tr><tr><td>8</td><td>(-)</td><td>(+)</td><td>(-)</td></tr><tr><td>9</td><td>(+)<br>before α</td><td>(+)</td><td>(-)</td></tr><tr><td>10</td><td>(-)</td><td>(+)</td><td>(-)</td></tr></tbody></table>

<table><caption>**Table 2.** Computational results</caption><thead><tr><th>Instance</th><th>∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 0</th><th>∇<sup>t</sup> = 1<br>∇<sup>s</sup> = 0</th><th>∇<sup>t</sup> = 2<br>∇<sup>s</sup> = 0</th><th>∇<sup>t</sup> = 4<br>∇<sup>s</sup> = 0</th><th>∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 1</th></tr></thead><tbody><tr><td>1.P10C15K5</td><td>154.65</td><td>166.75</td><td>185.84</td><td>199.84</td><td>162.75</td></tr><tr><td>2.P10C15K5</td><td>160.52</td><td>172.64</td><td>185.82</td><td>196.80</td><td>170.36</td></tr><tr><td>3.P20C30K8</td><td>254.69</td><td>266.77</td><td>287.86</td><td>296.84</td><td>270.96</td></tr><tr><td>4.P20C30K8</td><td>231.59</td><td>245.80</td><td>262.82</td><td>299.83</td><td>265.80</td></tr><tr><td>5.P30C40K10</td><td>396.47</td><td>410.66</td><td>463.75</td><td>470.86</td><td>396.47</td></tr><tr><td>6.P30C40K10</td><td>386.51</td><td>402.69</td><td>430.70</td><td>486.89</td><td>412.74</td></tr><tr><td>7.P40C52K12</td><td>533.67</td><td>546.75</td><td>-</td><td>-</td><td>523.74</td></tr><tr><td>8.P40C52K12</td><td>598.66</td><td>617.71</td><td>-</td><td>-</td><td>590.74</td></tr><tr><td>Instances</td><td>∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 2</td><td>∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 4</td><td>∇<sup>t</sup> = 1<br>∇<sup>s</sup> = 1</td><td>∇<sup>t</sup> = 2<br>∇<sup>s</sup> = 2</td><td>∇<sup>t</sup> = 4<br>∇<sup>s</sup> = 4</td></tr><tr><td>1.P10C15K5</td><td>179.98</td><td>179.54</td><td>188.26</td><td>220.98</td><td>220.36</td></tr><tr><td>2.P10C15K5</td><td>189.78</td><td>196.46</td><td>203.75</td><td>216.94</td><td>216.94</td></tr><tr><td>3.P20C30K8</td><td>301.58</td><td>307.96</td><td>280.63</td><td>311.94</td><td>315.78</td></tr><tr><td>4.P20C30K8</td><td>272.12</td><td>309.83</td><td>298.74</td><td>306.43</td><td>320.74</td></tr><tr><td>5.P30C40K10</td><td>410.66</td><td>433.75</td><td>390.75</td><td>454.74</td><td>454.74</td></tr><tr><td>6.P30C40K10</td><td>400.70</td><td>479.94</td><td>450.95</td><td>486.81</td><td>483.74</td></tr><tr><td>7.P40C52K12</td><td>540.78</td><td>-</td><td>550.10</td><td>-</td><td>-</td></tr><tr><td>8.P40C52K12</td><td>-</td><td>-</td><td>612.41</td><td>-</td><td>-</td></tr></tbody></table>

<table><caption>**Table 3.** Computational time (seconds)</caption><thead><tr><th>Instance</th><th colspan="2">∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 0</th><th colspan="2">∇<sup>t</sup> = 1<br>∇<sup>s</sup> = 0</th><th colspan="2">∇<sup>t</sup> = 2<br>∇<sup>s</sup> = 0</th><th colspan="2">∇<sup>t</sup> = 4<br>∇<sup>s</sup> = 0</th><th colspan="2">∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 1</th></tr><tr><th></th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th></tr></thead><tbody><tr><td>1.P10C15K5</td><td>60.20</td><td>+</td><td>300.85</td><td>0.004</td><td>401.25</td><td>0.013</td><td>1684.69</td><td>0.122</td><td>432.25</td><td>0.002</td></tr><tr><td>2.P10C15K5</td><td>34.96</td><td>+</td><td>450.29</td><td>0.003</td><td>545.26</td><td>0.003</td><td>1858.36</td><td>0.070</td><td>514.95</td><td>0.045</td></tr><tr><td>3.P20C30K8</td><td>103.69</td><td>+</td><td>605.27</td><td>0.010</td><td>1505.63</td><td>0.075</td><td>1762.84</td><td>0.012</td><td>511.78</td><td>0.07</td></tr><tr><td>4.P20C30K8</td><td>150.78</td><td>0.001</td><td>640.98</td><td>0.010</td><td>1783.69</td><td>0.092</td><td>1907.45</td><td>0.052</td><td>597.65</td><td>0.193</td></tr><tr><td>5.P30C40K10</td><td>204.98</td><td>0.013</td><td>852.93</td><td>0.136</td><td>1902.75</td><td>0.312</td><td>1940.75</td><td>0.120</td><td>625.14</td><td>0.178</td></tr><tr><td>6.P30C40K10</td><td>340.78</td><td>0.156</td><td>1270.98</td><td>0.121</td><td>1974.95</td><td>0.152</td><td>2075.65</td><td>0.211</td><td>945.14</td><td>0.196</td></tr><tr><td>7.P40C52K12</td><td>500.96</td><td>0.163</td><td>1243.87</td><td>0.120</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1432.85</td><td>0.142</td></tr><tr><td>8.P40C52K12</td><td>690.96</td><td>0.181</td><td>1783.87</td><td>0.320</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1534.88</td><td>0.174</td></tr><tr><th>Instance</th><th colspan="2">∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 2</th><th colspan="2">∇<sup>t</sup> = 0<br>∇<sup>s</sup> = 4</th><th colspan="2">∇<sup>t</sup> = 1<br>∇<sup>s</sup> = 1</th><th colspan="2">∇<sup>t</sup> = 2<br>∇<sup>s</sup> = 2</th><th colspan="2">∇<sup>t</sup> = 4<br>∇<sup>s</sup> = 4</th></tr><tr><th></th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th><th>CT</th><th>GAP</th></tr><tr><td>1.P10C15K5</td><td>620.10</td><td>0.09</td><td>1350.15</td><td>0.14</td><td>1763.08</td><td>0.013</td><td>1989.96</td><td>0.122</td><td>2989.33</td><td>0.32</td></tr><tr><td>2.P10C15K5</td><td>594.19</td><td>0.04</td><td>1474.08</td><td>0.19</td><td>1845.16</td><td>0.003</td><td>2201.66</td><td>0.15</td><td>2982.64</td><td>0.392</td></tr><tr><td>3.P20C30K8</td><td>1003.19</td><td>0.007</td><td>1635.72</td><td>0.23</td><td>1805.13</td><td>0.075</td><td>2485.36</td><td>0.19</td><td>3420.95</td><td>0.412</td></tr><tr><td>4.P20C30K8</td><td>1230.01</td><td>0.19</td><td>1647.87</td><td>0.20</td><td>1823.57</td><td>0.092</td><td>2547.25</td><td>0.23</td><td>3485.32</td><td>0.480</td></tr><tr><td>5.P30C40K10</td><td>1403.17</td><td>0.213</td><td>1687.37</td><td>0.30</td><td>1890.51</td><td>0.312</td><td>2340.23</td><td>0.29</td><td>3111.54</td><td>0.255</td></tr><tr><td>6.P30C40K10</td><td>1340.08</td><td>0.320</td><td>1770.78</td><td>0.39</td><td>2983.71</td><td>0.152</td><td>3005.65</td><td>0.32</td><td>3105.84</td><td>0.324</td></tr><tr><td>7.P40C52K12</td><td>-</td><td>0.458</td><td>-</td><td>-</td><td>2304.32</td><td>0.241</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>8.P40C52K12</td><td>-</td><td>-</td><td>-</td><td>-</td><td>2140.79</td><td>0.413</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>
**Objective Function:** Table 2 presents the obtained objective function value for each instance. The deterministic case (DC) value corresponds to ($\nabla^t = 0, \nabla^s = 0$). The objective function also increases as $\nabla^t$ and $\nabla^s$ increase. It can be explained by requiring its maximal value for all travel and service times. The objective function becomes insensitive to uncertainties for high values of $\nabla^t$ and $\nabla^s$ because it has already reached the maximum number of routes the caregiver will travel according to their workload.

**Computational Time:** Table 3 presents the computational time (CT) of the models in seconds. The uncertainties have a significant impact on CT. The CT of the robust models increases significantly compared to the deterministic counterpart. The robust model with a large budget is more challenging to solve compared with the deterministic counterpart. Most of the instances have not been solved to optimality due to the complexity of the problem. Especially the robust counterpart. The average gap concerning instance (5.P30C40K10) and instance (2.P10C15K5) are about 0.212% and 0.089%, respectively. We remark that the average gap is significantly small for the smallest instances compared to the largest ones. (+) refers to the problem that has been solved to optimality. (-) refers to when we get “out of memory”. (~) is when the solver stops after more than 3600 seconds of running time. The CT increases when $\nabla$ is around 4; the number of routes that a caregiver can travel is reached, and all the chosen arcs and nodes require their maximum travel and service times, respectively.

## 4.1 Robustness Analysis

We evaluate the robust HHC solutions in terms of feasibility and robustness. We seek to find solutions that are immunized against real-life uncertainties. The extra cost incurred by such a robust solution should be compensated by the gain in terms of robustness or feasibility [16]. We consider two performance measures: The price of robustness (PoR) and the risk.

*Price of robustness (PoR).* The PoR is defined as $\frac{z(\nabla)-z}{z}$.100% where $z(\nabla)$ is the optimal objective value for a given value of the budget of robustness $\nabla^s$ and $\nabla^t$, $z$ represents the optimal objective value according to the deterministic problem [16]. *Probability of constraint violation (Risk).* The main objective of robustness is to find solutions that are immunized against uncertainty. The routes provided by the robust solution are likely to be more feasible in real-life situations than deterministic solutions when route travel time or/care time increase which is very common. To evaluate the risk, we use the Monte Carlo simulation and we generate 200 random uniform realization of service time in the range $[\bar{s}_i, \bar{s}_i+\hat{s}_i]$ and travel time in the range $[\bar{t}_{ij}, \bar{t}_{ij}+\hat{t}_{ij}]$. We aim to assess the number of times a given robust solution is infeasible out of the 200 realizations. The main steps of the simulation are given as follows:

1. **Input.** Solution $x(\nabla)$

2. For $\omega = 1$ to 200, do:

$$-\tilde{s}_i^\omega \sim U[\bar{s}_i, \bar{s}_i + \hat{s}_i], \forall i \in I$$

$$-\bar{t}_{ij}^\omega \sim U[\bar{t}_{ij}, \bar{t}_{ij} + t_{ij}], \forall (i, j) \in E$$

-Evaluate the feasibility of $x(\nabla)$ with $s_i^\omega$ and $t_{ij}^\omega$

3. **Output.** The empirical probability evaluating constraint violation of the solution
<figure><img src="image_4.png" /><figcaption>**Fig. 1.** Risk versus PoR
($\nabla^t = 0$ to 4, $\nabla^s = 0$)</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Risk versus PoR
($\nabla^s = 0$ to 4, $\nabla^t = 0$)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 3.** Risk versus PoR
($\nabla^s = 0$ to 4, $\nabla^t = 0$ to 4)</figcaption></figure>

For a small value of $\nabla^t$ and $\nabla^s$, the risk of having an infeasible route significantly increases (e.g., for the case $\nabla^s = 0$ and $\nabla^t = 0$, the risk of having infeasible routes increases by 95.98%, the risk is obtained from the Monte Carlo simulation). Hence, the deterministic solutions are not protected against uncertainties [16], and most routes will be infeasible if caregivers' travel and service times deviate from the nominal values. Besides, if we assume the default values and the caregiver travels within his worst-case travel time, the time window of his next care can be already closed, and the route will be infeasible. The robust solutions give an advantage in terms of cost and feasibility for most instances. Figure 1, Fig. 2 and Fig. 3 illustrate the risk versus the PoR for instance (P20C30K8). They show a trade-off between the risk of having constraints violation and not being too conservation. The cost is not dramatically increased to protect the solutions against constraints violation. Figure 2 shows that there is almost no risk ($risk = 0.05\%$) of constraint violation when the PoR is up to 19.11% ($\nabla^s = 0$ to 4, $\nabla^t = 0$ and 20% deviation).

# 5 Conclusions and Perspectives

In this study, a new approach to solving the daily HHC routing and scheduling problem was proposed. The approach included a set of relevant HHC constraints. Also, a novel robust counterpart HHC model under travel and service time uncertainty was presented. Using the price of robustness gives the minimal cost that leads to an increase in the chances of having caregivers' routes feasible in practice. A robustness analysis using a Monte Carlo simulation was done to show the efficiency of the proposed approach. The proposed robust counterpart model was more challenging to solve than the deterministic model, especially for large budgets. The proposed approach gives good solutions compared to the approaches in the literature; the price of robustness was not dramatically increased even for large values of the budget of robustness. Comparing the increase of route cost and risk of solutions infeasibility using the simulation indicates the relevance of the obtained robust solutions and the importance of considering uncertainty to solving real-life planning problems. A column generation algorithm will be developed to solve the large instances of the problem with additional constraints and criteria, which will be future work.
References

1. Ben Rabaa, F., Harbi, S., Amraoui, A.: Robust optimization for a home care scheduling problem. In: The 4th International Conference on Logistics Operations Management, GOL’18, April 10-12 LEHAVRE FRANCE (04 2018)

2. Benzerti, Y.: Home health care operations management: Applying the districting approach to Home Health Care. Ph.D. thesis, Ecole Centrale Paris. (2012)

3. Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Programming **98**, 49–71 (2003)

4. Cappanera, P., Scutella, M.: Joint assignment, scheduling, and routing models to home care optimization: A pattern based approach. Transportation Science **49**, 830–852 (2015)

5. Cisse, M., Yalcindag, S., Kergosien, Y., Sahin, E., Lente, C., Matta, A.: Or problems related to home health care: A review of relevant routing and scheduling problems. Operations Research for Health Care **13**, 1–22 (2017)

6. Dumas, Y., Desrosiers, J., Gelinas, J., Solomon, M.M.: An optimal algorithm for the traveling salesman problem with time windows. Operations Research **43**, 367–371 (1995)

7. En-nahli, L., Allaoui, H., Nouaouri, I.: A multi-objective modelling to human resource assignment and routing problem for home health care services. IFAC-PapersOnLine **48**, 698–703 (2015)

8. Fikar, C., Hirsch, P.: Home health care routing and scheduling: A review. Comput. Oper. Res. **77**, 86–95 (2017)

9. Grenouilleau, F., Legrain, A., Lahrichi, N., Rousseau, L.M.: A set partitioning heuristic for the home health care routing and scheduling problem. Eur. J. Oper. Res. **275**, 295–303 (2019)

10. Gror, C., Golden, B., Wasil, E.: The consistent vehicle routing problem. Manuf. Serv. Oper. Manage. **11**, 630–643 (2009)

11. Haddadene, S.A., Labadie, N., Prodhon, C.: Nsgaii enhanced with a local search for the vehicle routing problem with time windows and synchronization constraints. IFAC-PapersOnLine **49**, 1198–1203 (2016)

12. Lanzarone, E., Matta, A., Sahin, E.: Operations management applied to home care services: 2012 the problem of assigning human resources to patients. IEEE Trans. Syst. Man. Cybern. Part A: Syst. Hum. **42**, 1346–1363 (2012)

13. Lee, C., Lee, K., Park, S.: Robust vehicle routing problem with deadlines and travel time/demand uncertainty. J. Oper. Res. Soc. **63**, 1294–1306 (2012)

14. Makboul, S., Kharraja, S., Abbassi, A., El Hilali Alaoui, A.: A Three-stage Approach for the Multi-period Green Home Health Care Problem with Varying Speed Constraints. In: 13ème CONFERENCE INTERNATIONALE DE MODELISATION, OPTIMISATION ET SIMULATION (MOSIM2020), 12-14 Nov 2020, AGADIR, Maroc. AGADIR (virtual), Morocco (Nov 2020)

15. Mascolo, M.D., Martinez, C., Espinouse, M.: Routing and scheduling in home health care: A literature survey and bibliometric analysis. Computers & Industrial Engineering p. 107255 (2021). https://doi.org/10.1016/j.cie.2021.107255

16. Munari, P., Moreno, A., Vega, J.D.L., Alem, D., Gondzio, J., Morabito, R.: The robust vehicle routing problem with time windows: Compact formulation and branch-price-and-cut method. Transportation Science **53**, 1043–1066 (2019)

17. Rasmussen, M., Justesen, T., Dohn, A., Larsen, J.: The home care crew scheduling problem: Preference-based visit clustering and temporal dependencies. European J. Oper. Res. **219**, 598–610 (2012)

18. Shi, Y., Boudouhb, T., Grunder, O.: A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times. Transportation Research Part E: Logistics and Transportation Review **128**, 52 – 95 (2019)