Читать книгу Healthcare Systems - Группа авторов - Страница 33

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 a possible route, the caregiver starts from origin 0, which is generally the HHC structure, and visits the nodes {i, i + 1, i + 2, ..., j-1, j}. In our case, we have to calculate a score cij (equation [2.1]), thus calculating the sum of the distances traveled by the caregiver from their starting point, until they return to the HHC at the end of their schedules. Likewise, the fitness function must take into consideration time constraints, that is, the penalties incurred in the case of violating a patient’s availability time window.

[2.1]

dij denotes the distances between two patients i and j; v represents the cost per distance traveled; ke and kl represent, respectively, the penalties when a caregiver arrives at the patient’s home too early or too late; ei and li denote the availability time window of patient i and ai indicates the caregiver arrival time at the home of patient i. We have also integrated the variable Qu into the fitness function to designate whether a care worker is qualified to perform a treatment or a visit or not. We considered a correlation between the caregiver qualification and the patient dependency level. The variable Qu can be equal to 1 or 0 indicating, respectively, a qualified or unqualified caregiver.

Selection. Once the score has been calculated for the whole population, we can select the most adapted individuals to become parents. There are different approaches for the selection. In our case, we have chosen to apply a probabilistic method called “roulette wheel selection”.

Crossing. This is a mechanism by which the selected chromosomes produce a new generation. This genetic operator will help us to explore the full range of possible solutions.

Mutation. Once the new chromosome is generated, we apply the mutation before adding the child to the next generation. Mutation consists of altering a gene in the generated chromosome. We include the new population in the old list and then we repeat from step 2.

Stop condition. The process is repeated until a maximum number of generations is reached. When looking for an optimal solution, many conditions are taken into account. A workload is limited to up to four patients for each caregiver, and patients are visited according to their availability windows.