# Home Healthcare Routing and Scheduling Problem During the COVID-19 Pandemic

Fatemeh Taghipour, Reza Tavakkoli-Moghaddam, Maryam Eghbali-Zarch

► To cite this version:

Fatemeh Taghipour, Reza Tavakkoli-Moghaddam, Maryam Eghbali-Zarch. Home Healthcare Routing and Scheduling Problem During the COVID-19 Pandemic. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.373-382, 10.1007/978-3-030-85902-2_40. hal-04117668

HAL Id: hal-04117668

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

Submitted on 5 Jun 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.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.
# Home Healthcare Routing and Scheduling Problem
during the COVID-19 Pandemic

Fatemeh Taghipour [0000-0002-4919-7671], Reza Tavakkoli-Moghaddam [0000-0002-6757-926X]
and Maryam Eghbali-Zarch [0000-0003-0296-4025]

School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran
tavakoli@ut.ac.ir

**Abstract.** Home healthcare routing and scheduling problems provide a better condition for elderly and disabled people. In the presence of the worldwide pandemic of coronavirus disease 2019 (COVID-19 pandemic), these problems have shown their efficiency and necessity to notice this new group of patients suffering from COVID-19. For this purpose, a new mathematical model is developed for a home healthcare routing and scheduling problem (HHCRSP) regarding the impact of the COVID-19 outbreak. The satisfaction and cost of assigning staff to patients with suspected or confirmed COVID-19 are considered. This problem considers travel time between patients and aims to minimize it. The proposed model is solved using GAMS optimization software. Computational experiments are considered for several test problems and a sensitivity analysis is conducted to validate the model performance.

**Keywords:** Home healthcare, Staff scheduling, Employee satisfaction, COVID-19.

## 1 Introduction

One of the effective ways to use resources more efficiently and reduce costs is home healthcare services at home [1]. Furthermore, population aging and increasing life expectancy, government pressure on the health system to reduce costs lead to increasing demand for home healthcare services [2, 3]. On the other hand, in the presence of pandemics, SAR-COV-19 leads people to provide their needs at home as much as possible [4, 5]. Due to the increasing demand for home healthcare services, organizations seek to optimize activities and increase the quality of their services. In this context, one of the problems that have been considered by researchers in recent years is routing and scheduling for staff members [1]. These problems include the combination of nurses, patients, and nurses' routing and scheduling to patients, which complicates the problem and causes more attention of researchers.

A home healthcare problem is an extension of a vehicle routing problem with time windows [6] that aims to determine the optimal plan for staff to visit the patients considering many limitations, such as the availability of patients and nurses' time windows, staff workload, and skill requirement [7].
The primary purpose of this paper is to develop an optimization model considering the allocation of nurses to patients with suspected or confirmed COVID-19. Due to the change of lifestyle during the COVID-19 outbreak, it is obvious that nurses are not willing to service patients with suspected or confirmed COVID-19. Therefore, the satisfaction level of nurses has changed and affects the costs of the organization. The rest of this paper is organized as follows. Sections 2 and 3 present the literature review and the problem description. Section 4 solves an illustrative problem by the developed model. Finally, Section 5 concludes this research and presents opportunities for further research.

## 2 Literature Review

As mentioned in the previous section, the complexity, novelty, and increasing demand of a home healthcare routing and scheduling problem (HHCRSP) cause more attention to researchers. Most researchers have focused on the cost and travel time of staff, and a few numbers have focused on minimizing the number of staff. Braekers et al. [6] proposed a bi-objective model in a home healthcare scheduling problem (HHCSP) to minimize the routing and overtime costs and client inconvenience. They considered the hard time windows, preferences of staff and patients, and overtime of staff. Moussavi et al. [8] presented a multi-period HHCSP to minimize travel time or travel distance. Their model considered continuing care, time windows of staff and patients, determined staff numbers, and the route each staff should travel each period. The Gurobi MILP solver was used to solve and a meta-heuristic algorithm based on the decomposition of the formulation was used to simplify. Mankowska [9] presented a daily scheduling model for HHCSPs to minimize travel costs or maximize service quality. Their model involves synchronization and qualifications of staff members, temporal dependencies, and workload balance. To solve the model, a powerful heuristic method based on a sophisticated solution was proposed.

A few numbers of papers deal with the minimum number of staff, in a long-term period, it is more important than a single period [2]. In this regard, Allaoua et al. [10] developed a single-period integer linear programming model to minimize the number of staff assigned and considering skills and available time windows for staff. They developed a matheuristic method for large-sized problems. Hiermann et al. [11] proposed a single-period model for home healthcare problems to find the most convenient assignment for staff and patients at the same time. Then, they suggested meta-heuristics, such as memetic algorithm (MA), scatter search (SS), simulated annealing (SA) algorithm, and variable neighborhood search (VNS) to solve the model.

Other criteria that can be observed in the objective function of some papers are two types of satisfaction; staff and patients [12]. Rest and Hirsch [13] proposed an HHCSP to minimize travel time and waiting time of staff by considering patient hard time window, maximum working time, and rest time for staff members to satisfy staff. To solve this problem, they suggest tabu search (TS) algorithm. An example of patient satisfaction can find in Wirnitzer et al. [14] who proposed five mixed-integer programming
formulations with different objective functions by considering the continuity of care, breaks, shift rotations, maximum working times, and patient or nurse preferences.

Lean management is one of the latest management systems in healthcare [15]. The results of lean implementation in management include reducing errors, prioritizing patients, and providing quality and more effective services to patients [16, 17]. One of the most important goals of lean is to save time and reduce waiting time in a queue [16, 18] and reduce costs, and increase productivity [16]. For example, Improta et al. [19] reduced the patient waiting time by using lean in the emergency room. Other goals of implementing this improvement in organizations have suggested maximizing the value and eliminating waste and possible response to the need to respond to rapid change [20, 21].

Young et al. [22] is one of the first lean studies to improve patient care. The authors introduce the three industrial approaches of pure thinking, the theory of limitations, and Six Sigma, how these three approaches relate to health care. Then they concluded that for these approaches to be effective, good leadership and participation of employees are needed. Also, by considering these approaches, they concluded that there are many standard features between them, and all of them need to recognize bottlenecks and use a suitable approach to eliminate them. Kim et al. [23] introduced a hospital that provides more helpful and better patient care using lean management. They also addressed the obstacles to using lean methods and ways to overcome them, But Poksinska [24] implemented and described the obstacles and problems.

Staff members are our valuable resources, especially in the presence of covid-19 so we should care for them most. Our main contribution is to reach an assignment that considers maximum cost and minimum satisfaction of staff who assign to covid-19 suspicious patients.

## 3 Problem Definition

In this section, a multi-period mathematical model is presented. A number of patients and staff, cost of assigned staff to the patients with suspected or confirmed COVID-19, and satisfaction of this staff are assumed. The objective of this problem is to minimize the travel time of each staff. The following notations are employed to develop a model for the HHCRSP.

### Sets

*i* Set of employees

*j* and *k* Set of patients

*p* Set of periods per day

*d* Set of days

### Parameters

*ni* Number of employees

*nj* Number of patients

*nd* Number of considered days
$npi$ Maximum number of periods each staff can work

$MS_{jpd}$ Matrix of the care services needed by the patients

$CS_{jpd}$ Matrix of patients with suspected or confirmed COVID-19

$DS_{jk}$ Travel time between patients j and k

$\alpha_i$ Disutility of giving care service of nurse i in the vicinity of patients with suspected or confirmed COVID-19

$Cost_i$ Extra cost for each employee if he/she is assigned to patients with suspected or confirmed COVID-19

$Costo$ Maximum cost of visiting patients with suspected or confirmed COVID-19

$SS$ Minimum satisfaction level of the staff who assign to patients with suspected or confirmed COVID-19

## Variables

$X_{ijpd}$ 1 if staff member i is assigned to patient j in period p of day d; 0, otherwise

$X'_{ijpd}$ 1 if staff member i is assigned to covid-19 suspicious patients j in period p of day d; 0, otherwise

$DI_i$ Time of traveling staff member i during all days

$SA_{id}$ Satisfaction level of staff member i during day d

$SD_i$ Satisfaction level of staff member i during all days

$TI_{ijkd}$ 1 if staff member i has to visit patient k after j in day d; 0, otherwise

$DID_{id}$ Time of traveling staff member i in day d

$DTI$ Total travel time of all staff members

$CTT_{id}$ Cost of staff member i who assigned to patients with suspected or confirmed COVID-19 during day d

$CO$ Cost of all staff's assignments to patients with suspected or confirmed COVID-19

$SO$ Satisfaction level of all staff members assigned to patients with suspected or confirmed COVID-19

The proposed mathematical programming model of the HHCRSP is presented as follows:

$$ \text{Min } Z = DTI \quad (1) $$

s.t.

$$ \sum_{i=1}^{n_i} X_{ijpd} = MS_{jpd} \quad \forall p \in P, j \in J, d \in D \quad (2) $$

$$ \sum_{j=1}^{n_j} X_{ijpd} \le I \quad \forall p \in P, j \in J, d \in D \quad (3) $$

$$ \sum_{j=1}^{n_j} \sum_{p=1}^{h} X_{ijpd} \le npi \quad \forall i \in I, d \in D \quad (4) $$
$$X_{ijpd} + \sum_{k \in J - j} X_{ik(p+1)d} \le 1 \qquad \forall i \in I, j \in J, p \in P^{-}, d \in D \quad (5)$$

$$X_{ijpd} + \sum_{l \in I - i} X_{lj(p+1)d} \le 1 \qquad \forall i \in I, j \in J, p \in P^{-}, d \in D \quad (6)$$

$$X'_{ijpd} \le X_{ijpd} \times (2 - X_{ijpd}) \qquad \forall i \in I, j \in J, p \in P, d \in D \quad (7)$$

$$\sum_{i=1}^{ni} X'_{ijpd} = CS_{jpd} \qquad \forall j \in J, p \in P, d \in D \quad (8)$$

$$\sum_{i=1}^{ni} \sum_{j=1}^{nj} Tl_{ijkd} = 1 \qquad \forall k \in J, d \in D \quad (9)$$

$$\sum_{j=1}^{nj} Tl_{ikjd} = \sum_{j=1}^{n} Tl_{ijkd} \qquad \forall i \in I, k \in J, d \in D \quad (10)$$

$$Tl_{ijkd} \le X_{ijpd} \qquad \forall i \in I, j \in J, k \in J, d \in D \quad (11)$$

$$DID_{id} = \sum_{j=1}^{nj} \sum_{k=1}^{nj} DIS_{jk} \times T_{ijkd} \qquad \forall i \in I, d \in D \quad (12)$$

$$DI_i = \sum_{d=1}^{nd} DID_{id} \qquad \forall i \in I \quad (13)$$

$$DTI = \sum_{d=1}^{nd} \sum_{i=1}^{m} DID_{id} \qquad (14)$$

$$\sum_{j=1}^{nj} \sum_{p=1}^{npi} \alpha_i X'_{ijpd} + X_{ijpd} - X'_{ijpd} = SA_{id} \qquad \forall i \in I, d \in D \quad (15)$$

$$SD_i = \sum_{d=1}^{t} SA_{id} \qquad \forall i \in I \quad (16)$$

$$\sum_{d=1}^{nd} \sum_{i=1}^{ni} SA_{id} \ge SS \qquad (17)$$

$$\sum_{d=1}^{nd} \sum_{i=1}^{ni} SA_{id} = SO \qquad (18)$$

$$\sum_{j=1}^{nj} \sum_{p=1}^{npi} cost_i \times X'_{ijpd} = CTT_{id} \qquad \forall i \in I, d \in D \quad (19)$$

$$\sum_{d=1}^{nd} \sum_{i=1}^{ni} CTT_{id} \le Costo \qquad (20)$$

$$\sum_{d=1}^{nd} \sum_{i=1}^{ni} CTT_{id} = CO \qquad (21)$$
The objective function (1) minimizes the total travel time by all the staff members during a day. Equation (2) ensures that only one staff member can assign to each patient who needs care services. Equation (3) ensures that each staff member can only assign to one patient. Equation (4) implies that each staff member cannot work more than the maximum number of periods per day. Equation (5) prevents that staff members visit two different patients in two consecutive periods because the model considers travel time between visits. Equation (6) implies continue of care if a patient needs more than one period. Equations (7) and (8) imply that employees are assigned to patients with suspected or confirmed COVID-19. Equations (9) - (11) indicate the sequence of the patients who are visited by an employee. Equation (12) calculates the travel time of staff members in a day. Equations (13) and (14) calculate the travel time for staff member *i* during all days and the total travel time of all staff. Equations (15) and (16) indicate the satisfaction level of staff member *i* during a day and the satisfaction level of staff member *i* during all days. Equation (17) controls the minimum satisfaction level of the staff members assigned to the patients with suspected or confirmed COVID-19. Equation (18) computes the satisfaction level of all staff members assigned to the patients with suspected or confirmed COVID-19. Equation (19) calculates the cost of all staff's assignments to the patients with suspected or confirmed COVID-19 during a day. Equation (20) indicates the budget constraint of visiting requirements for the patients with suspected or confirmed COVID-19. Equation (21) calculates the cost for all staff members assigned to the patients with suspected or confirmed COVID-19.

# 4 Numerical Experiments

In this section, the proposed model is solved by GAMS software using the BARON solver for small-sized instances.

## 4.1 Case study and result

To validate the model introduced in this study, the model is applied on small-sized instances that each day includes 12 periods. Table 1 represents the value of parameters for each test problem. All the data are selected random numbers between 0 and 30.

## 4.2 Sensitivity analysis

The model is solved by changing some parameters to determine sensitivity analysis. The number of patients with suspected or confirmed COVID-19 in the fourth instance of the last section is modified to investigate the changes in cost and satisfaction level of staff members servicing the patients with suspected or confirmed COVID-19. The computational results are shown in Figs. (1) – (4), which reveal that by increasing the number of patients with suspected or confirmed COVID-19, the cost of all staff's assignments to these people increases, and the satisfaction level of staff members will decrease.
<table><caption>**Table 1.** Description of each test problem</caption><thead><tr><th>No. of days</th><th>No. of patients</th><th>No. of staff</th><th>DTI</th><th>SO</th><th>CO</th><th>Cycle time</th></tr></thead><tbody><tr><td>1</td><td>4</td><td>2</td><td>63</td><td>1.11</td><td>3.5</td><td>&lt;0</td></tr><tr><td>1</td><td>8</td><td>3</td><td>186</td><td>2.86</td><td>17.75</td><td>11s</td></tr><tr><td>1</td><td>12</td><td>5</td><td>117</td><td>6.7</td><td>36.3</td><td>918s</td></tr><tr><td>1</td><td>16</td><td>7</td><td>474</td><td>4.56</td><td>41.19</td><td>3240s</td></tr><tr><td>2</td><td>4</td><td>2</td><td>148</td><td>2.44</td><td>4.5</td><td>&lt;0</td></tr><tr><td>2</td><td>8</td><td>3</td><td>104</td><td>3.19</td><td>24.13</td><td>63s</td></tr><tr><td>2</td><td>12</td><td>5</td><td>89</td><td>3.86</td><td>37.47</td><td>1920s</td></tr><tr><td>2</td><td>16</td><td>7</td><td>397</td><td>4.32</td><td>46.25</td><td>8944s</td></tr><tr><td>3</td><td>4</td><td>2</td><td>123</td><td>3.2</td><td>8.27</td><td>&lt;0</td></tr><tr><td>3</td><td>8</td><td>3</td><td>179</td><td>2.5</td><td>54.46</td><td>71s</td></tr><tr><td>3</td><td>12</td><td>5</td><td>517</td><td>1.95</td><td>98.72</td><td>3856s</td></tr><tr><td>3</td><td>16</td><td>7</td><td>945</td><td>2.5</td><td>189.3</td><td>5470s</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Effects of changing the number of patients on the staff's cost (D=1)</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Effects of changing the number of patients on the staff's satisfaction level (D=1)</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Fig. 3. Effects of changing the number of patients on the staff's cost (D=2)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Fig. 4. Effects of changing the number of patients on the staff's satisfaction level (D=2)</figcaption></figure>

**5 Conclusion**

In this study, a mathematical model was proposed for a home healthcare routing and scheduling problem (HHCRSP). The impact of the Covid-19 pandemic is considered in the proposed model by controlling the cost and minimum satisfaction level of staff members, who are assigned to the patients with suspected or confirmed COVID-19. To validate the model performance, a set of small-sized instances were solved using GAMS software and a sensitivity analysis was conducted. For future studies, the model can be extended to a multi-objective model by considering more preferences of patients and staff. The model can be solved by heuristics and meta-heuristics for large-sized problems.

**References**

1. Khodabandeh, P., Kayvanfar, V., Rafiee, M., Werner, F.: A bi-objective home health care routing and scheduling model with considering nurse downgrading costs. International Journal of Environmental Research and Public Health 18(3), 900 (2021).
2. Fikar, C., Hirsch, P.: Home health care routing and scheduling: A review. Computers & Operations Research 77, 86-95 (2017).

3. Shahnejat-Bushehri, S., Tavakkoli-Moghaddam, R., Momen, S., Ghasemkhani, A., Tavakkoli-Moghaddam, H.: Home health care routing and scheduling problem considering temporal dependencies and perishability with simultaneous pickup and delivery. IFAC-PapersOnLine 52(13), 118-123 (2019).

4. Euchi, J.: Optimising the routing of home health caregivers: can a hybrid ant colony metaheuristic provide a solution? British Journal of Healthcare Management 26(7), 192-196 (2020).

5. Euchi, J.: Do drones have a realistic place in a pandemic fight for delivering medical supplies in healthcare systems problems?. Chinese Journal of Aeronaut 34(2), 182-190 (2021).

6. Braekers, K., Hartl, R. F., Parragh, S. N., Tricoire, F., A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience. European Journal of Operational Research 248(2), 428-443 (2016).

7. Goodarzian, F., Abraham, A., Fathollahi-Fard, A.M.: A biobjective home health care logistics considering the working time and route balancing: A self-adaptive social engineering optimizer. Journal of Computational Design and Engineering 8(1), 452-474 (2021).

8. Moussavi, S.E., Mahdjoub, M., Grunder, O.: A matheuristic approach to the integration of worker assignment and vehicle routing problems: Application to home healthcare scheduling. Expert Systems with Applications 125, 317-332 (2019).

9. Mankowska, D.S., Meisel, F., Bierwirth, C.: The home health care routing and scheduling problem with interdependent services. Health Care Management Science 17(1), 15-30 (2014).

10. Allaoua, H., Borne, S., Létocart, L., Calvo, R. W.: A matheuristic approach for solving a home health care problem. Electronic Notes in Discrete Mathematics 41, 471-478 (2013).

11. Hiermann, G., Prandtstetter, M., Rendl, A., Puchinger, J., Raidl, G. R.: Metaheuristics for solving a multimodal home-healthcare scheduling problem. Central European Journal of Operations Research 23(1), 89-113 (2015).

12. Cissé, M., Yalçındağ, S., Kergosien, Y., Şahin, E., Lenté, 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).

13. Rest, K.-D., Hirsch, P.: Daily scheduling of home health care services using time-dependent public transport. Flexible Services and Manufacturing Journal 28(3), 495-525 (2016).

14. Wirnitzer, J., Heckmann, I., Meyer, A., Nickel, S.: Patient-based nurse rostering in home care. Operations Research for Health Care 8, 91-102 (2016).

15. Mazzocato, P., Thor, J., Bäckman, U., Brommels, M., Carlsson, J., Jonsson, F., Savage, C.: Complexity complicates lean: Lessons from seven emergency services. Journal of Health Organization and Management 28(2), 266-288 (2014).

16. Mazzocato, P., Holden, R. J., Brommels, M., Aronsson, H., Bäckman, U., Elg, M., Thor, J.: How does lean work in emergency care? A case study of a lean-inspired intervention at the Astrid Lindgren Children's hospital, Stockholm, Sweden. BMC Health Services Research 12(1), 1-13 (2012).

17. Mazzocato, P., Savage, C., Brommels, M., Aronsson, H., Thor, J.: Lean thinking in healthcare: a realist review of the literature. BMJ Quality & Safety 19(5), 376-382 (2010).

18. Hydes, T., Hansi, N., Trebble, T. M.: Lean thinking transformation of the unsedated upper gastrointestinal endoscopy pathway improves efficiency and is associated with high levels of patient satisfaction. BMJ Quality & Safety 21(1), 63-69 (2012).
10 F. Taghipour et al.

19. Improta, G., Romano, M., Di Cicco, M.V., Ferraro, A., Borrelli, A., Verdoliva, C., Triassi, M., Cesarelli, M.: Lean thinking to improve emergency department throughput at AORN Cardarelli hospital. BMC Health Services Research 18(1), p. 1-9 (2018).

20. Womack, J. P., Byrne, A. P., Fiume, O. J., Kaplan, G. S., Toussaint, J.: Going lean in health care. Cambridge, MA: Institute for Healthcare Improvement (2005).

21. Jones, D., Mitchell, A.: Lean thinking for the NHS. Vol. 51, NHS Confederation London (2006).

22. Young, T., Brailsford, S., Connell, C., Davies, R., Harper, P., Klein, J. H.: Using industrial processes to improve patient care. BMJ 328(7432), 162-164 (2004).

23. Kim, C. S., Spahlinger, D. A., Kin, J. M., Billi, J. E.: Lean health care: what can hospitals learn from a world-class automaker? Journal of Hospital Medicine 1(3), 191-199 (2006).

24. Poksinska, B.: The current state of Lean implementation in health care: literature review. Quality Management in Healthcare 19(4), 319-329 (2010).