Healthcare Systems

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.

The routes generated by the offline algorithm may be subject to changes due to unforeseen events. In order to integrate a dynamic and reactive aspect to the proposed algorithm, we propose the management of in real time uncertainties related to caregiver availability or delay due to a change in activity duration. Caregivers should send notifications at the start and end of each visit through a dedicated mobile application. If they are late or unable to complete the assigned activity, they should immediately notify this to the planning officer. As a result, the scheduling agent executes the rescheduling algorithm (online) to reassign care to another available caregiver. The objective is to be able to carry out all the planned visits with the available caseworkers while respecting all the constraints shown in Figure 2.2.

Figure 2.2. Online rescheduling process. For a color version of this figure, see www.iste.co.uk/chaabane/healthcare.zip

To ensure that the rescheduling step takes place in case of disruptions, the planning officer needs to know the availability of careworkers. The required information is provided by notifications from caregivers. The planning officer has all the necessary information about patients’ preferences. When the new plan is generated, the agent sends it to the workers concerned after generating the new schedule ( equation [2.2]).

[ 2.2]

SA corresponds to the scheduling agent who is the request sender, MSAk represents the care worker k with a modification on their schedule, Vm ( t ) corresponds to the vector containing all the tasks t to be performed by MSAk , TreatmentTime ( Vm ) corresponds to the duration of the treatment Vm ( t ), PC refers to the geolocation coordinates of the patient and PS corresponds to the full patient features. When an MSAk receives a new schedule, they must approve it by notifying the SA scheduling agent.

To conclude, we have chosen a modeling approach based on two phases. The first phase is establishing caregiver schedules in an offline mode. The second phase, dedicated to the management of disruptions, generates a new schedule in real time, that is, online. It consists of rescheduling the GGA algorithm several times, taking into consideration the available caregivers and the associated information known at the time of the rescheduling (the state of their current schedule and their geolocation).

In order to ensure better patient care, we develop a platform that optimizes routes by taking into account the constraints related to patients and caregivers. The medical and coordination staff can thus communicate with each other and receive information on the patients treated and those still waiting for treatment. The platform is developed used for both offline planning and online rescheduling. It also allows the HHC schedule coordinator to record and consult the information needed. The main component of this platform is the genetic clustering algorithm. This algorithm communicates with Google Maps API to display the routes of caregivers as well as the geographical location of patients.