They have a direct impact on the selection of the caregiver who is able and qualified to visit a patient. Finally, the last group of geographic constraints concern the location and the means of transport (Emiliano et al. 2017).
Planning the activities of HHC workers can be compared to the vehicle routing problem (VRP) or the traveling salesman problem (TSP) (Cissé et al. 2017). These problems have the same objectives and are subject to the same constraints but with specific features related to the types of clients and stakeholders. One of the main specificities in HHC planning activities is the constraints related to the patient for whom care must be provided. Indeed, there are different patient profiles according to their dependency level and the number/types of visits required.
Some studies have focused on chemotherapy, where the constraint of expiring drugs is a priority (Shahnejat-Busheir et al. 2019). In some cases, the structures employ full-time and part-time staff. We then try to ensure that each employee has their own assigned shift while adhering to work schedules. In addition, patient satisfaction remains the priority (Nasir et al. 2018; Di Mascolo et al. 2018) and penalties can be added if patient preferences are not respected (Nasir et al. 2015). Therefore, continuity of care is a very important constraint (Hewitt et al. 2016; Lanzarone and Matta 2014; Wirnitzer et al. 2015). Other work (Cappanera 2013; Cardoso et al. 2015; David and Kim 2018) has focused on the workload distribution between caregivers in order to balance the workload and strenuousness. Each caregiver has a lunchtime break each day, which is a constraint for the schedule. We can consider a flexible lunchtime break that depends on visits in order to optimize the caregiver schedule (Xiao et al. 2018).
The problem of HHC scheduling consists of assigning caregivers to patients with the objective of satisfying the patient’s care plan (Di Mascolo et al. 2017) and taking into account that some patients may need to have several visits during the day (Martinez et al. 2019). In some cases, we must also take into account the means of transport chosen by the provider (car or public transport) and sustainable development by, for example, the use of electric cars (Erdem and Koç 2019; Fathollahi-Fard et al. 2019). The vehicle fleet should also be synchronized with the caregiver’s schedules and the shared visits (Nasir and Kuo 2020). In addition to these constraints, there are uncertainty problems linked to road traffic, personnel absence, etc. (Hewitt et al. 2016; Shi et al. 2017; Cappanera et al. 2018; Shi et al. 2019; Nikzad et al. 2020).
Home hospitalization is an area where, in some cases and for some patients, activities are interdependent. They may also require more than one careworker in the case of shared visits, for example (Redjem et al. 2011; Decerle et al. 2018, 2019). To solve this problem, some studies have created time slots for care. Caregivers are assigned to patients and time slots. Thus, an initial distribution between caregivers and time slots is established (Moussavi et al. 2019).
Several methods from operations research have been adapted to HHC problems (Brailsford and Vissers 2011) and especially to the planning problems that can be formulated as a Vehicle Routing Problem with Time Windows (Mutingi and Mbohwa 2013; Issaoui et al. 2015; Nasir et al. 2018; Xiao et al. 2018). Other works have used metaheuristics (Nickel et al. 2012; Grenouilleau et al. 2019, 2020; Nikzad et al. 2020), immune algorithms (Ben Hassen et al. 2019), genetic algorithms (Nasir and Kuo 2020), multi-agent systems (Widmer and Premm 2015, pp. 233–248; Marcon et al. 2017; Stojanova et al. 2017; Xie et al. 2017), ant colonies (Decerle et al. 2019), simulated annealing and tabu search (Shahnejat-Busheir et al. 2019) or even Markov chains (Koeleman et al. 2012).
HHC scheduling is a very important problem but rescheduling also remains a crucial challenge. The structures must cope with disruptions due to staff absences, the worsening of a patient’s condition, variations in the care duration, etc. Mosquera et al. (2019) offer flexible durations of care and routes with a compromise between the number of treatments and the workloads of caregivers. We observe that few studies have addressed the rescheduling problem. In the following section, we present the proposed approach to address the HHC scheduling problem.
2.3. Description of the proposed approach
In this section, we describe the proposed solution to solve the HHC scheduling problem. The approach is based on two phases. The first is done “offline” and establishes the caregiver schedules. The second phase is done “online” and manages all unforeseen events, especially staff absences and change in care duration or travel time. In case of a disruption, the scheduler needs to regenerate all the schedules in real time. This approach is similar to the periodic repair approach proposed by Xie (2016). In the next section we detail the implementation of the “offline” and “online” phases.
2.3.1. Home healthcare planning “offline phase”
The HHC planning problem can be seen as an extension of the traveling salesman problem (TSP) or the vehicle routing problem (VRP) where we have a set of points to visit and a defined resource number. The objective of our approach is to minimize the travel cost of the medical staff, according to constraints related to the HHC structure, patient care plans and caregiver working hours.
In order to solve this problem, we use the genetic algorithm (GA) originally developed by Holland (1975). It is an evolutionary algorithm that maintains a population of candidate solutions for the problem studied and evolves it by iteratively applying a set of stochastic operators. This algorithm represents the dynamic behavior of our scheduling agent in an “offline” mode.
In Figure 2.1, we present the steps of the genetic algorithm to assign visits to caregivers and to subsequently generate the optimal routes. The three main operators of the proposed algorithm (reproduction, crossing and mutation) are applied on a random population in order to create a new generation. The route is evaluated and tested until the termination criterion, iteratively modified by GA operators, is met. The system examines whether an optimal solution is obtained, that is, whether the visits are assigned to caregivers and all constraints are respected (Vishnupriyan et al. 2008).
Figure 2.1. Genetic algorithm (source: (Vishnupriyan et al. 2008). For a color version of this figure, see www.iste.co.uk/chaabane/healthcare.zip
Another extension of the genetic algorithm is the grouping genetic algorithm (GGA) initially proposed by Falkenauer (1992), which is suitable for solving grouping or classification problems. The general structure of the GGA is similar to the GA. The only difference lies in the internal mechanisms of the coding scheme and the implementation of the genetic operators. We present our solution based on the GGA and the methods chosen for each step.
GGA coding scheme. The structure of the genetic coding applied in this algorithm can strongly influence the performance of the GGA (Filho and Tiberti 2006; Mutingi and Mbohwa 2012). Mutingi and Mbohwa have developed a unique coding scheme that exploits the group structure for the scheduling problem. Let C = [1, n] be a chromosome representing a set of n patients who need to be visited by m caregivers. The purpose of this representation is to simplify the patient grouping across set C into m groups.
Population initialization. This step consists of creating a population of N elements, each with randomly generated DNA. DNA is created by randomly assigning patients to caregivers. A good technique might be to start by organizing the activities in ascending order of their starting times and, in some cases, to even organize them according to their duration. This procedure increases the likelihood that the initialization process will generate good solutions.
Fitness assessment. The fitness function tests the adequacy of the solution in relation with the problem being considered. Let (i, j) be