Healthcare Systems

New routes should be designed so that all services are provided while respecting constraints that we have divided into several categories: continuity constraints, legal constraints and constraints arising from the field.

Two types of continuity constraints are considered: time continuity constraints and human continuity constraints. These constraints are characteristic elements of the routing and scheduling update.

We must respect the continuity of the schedule by keeping the start and end times unchanged from those set initially. In our case study, these start and end times are indeed contractual and cannot be called into question for each change in the schedule.

Next, we must respect so-called “human” continuity constraints. We define a continuity rate for each beneficiary, depending on the number of careworkers they know and the maximum number of different careworkers they can tolerate. Depending on the value of this rate, the intervention of employees still unknown to the beneficiary may be authorized. This makes it possible both to integrate new arrivals into the schedules and to compensate for the departure of careworkers.

To our knowledge, the constraints of time continuity are rarely studied in the literature, if at all. As for the constraints of human continuity, they represent a scientific challenge.

These constraints result from French collective agreements (Legifrance 2012).

This involves limiting the amplitude of a work day, the effective working time of a day, a week, and of a month, guaranteeing breaks, in particular the lunch break, and prohibiting too many breaks within a single day and, more specifically, long breaks.

By amplitude we refer to the total duration of a work day, except for the first and last trip of the day. The waiting time under the collective agreements corresponds to the time not worked that is less than 15 minutes between two successive interventions. As for the effective working time, this is the total duration of the services performed during the day with waiting times strictly less than 15 minutes between two services and travel times, except the first and last visit of the route. We make sure that each careworker has a lunch break and takes a break when working for longer than 6 hours at a time.

Finally, a careworker must have the necessary qualifications to provide a service and overqualified work is allowed.

Some constraints are internal policies inherent in the home care industry or those specific to the organization in which we are interested. We build quarter-hour schedules, for obvious practical reasons. We allow for overtime but within a limit of 20% of the contractual hourly volume of the careworker concerned. It is possible to run two services consecutively with overlapping schedules if the duration of this overlap (including travel time) does not exceed 10 minutes. Finally, when the schedule is carried out for a week, the monthly contractual hourly volume is reduced to a weekly volume by dividing the monthly volume by 4.33.

The goal is to minimize the total waiting time induced by the schedule, i.e., the sum of all the careworker waiting times over the planning horizon. As we want to provide satisfactory schedules for careworkers, we count the waiting times as the sum of all the time not worked that is less than 90 minutes between two successive interventions, not counting the travel times. Indeed, when careworkers have an inactivity time of more than 90 minutes, we consider that they can take advantage of this period to conduct personal activities.

Our resolution method is an exact method that is based on a decomposition of the problem into two sub-problems: the generation of the set of admissible daily routes and then the selection of a set of daily routes to carry out a weekly schedule (or possibly a monthly schedule).

In a previous article (Martinez et al. 2019), we proposed an algorithm which allowed us to solve a similar theoretical problem. In the prototype presented here, we have adapted it in order to take into account all the routing and scheduling constraints and cover all the perturbations considered, and not just the departure of beneficiaries. We are not focusing here on the developed method but rather on its implementation and its integration into the prototype.

We start by generating a set of graphs, one for each day and careworker, in order to represent our problem. For a particular graph, a set of vertices represents the set of services that could be provided by this careworker, that is, the services for which he or she is qualified, whose start and end times correspond to their availability, and for which the beneficiary is compatible with the continuity constraints of the problem. To this set of vertices, we add two fictitious services representing the start and end points of a route.

We then create arcs between all the pairs of services which could be performed consecutively by the same careworker. It is thus a matter of ensuring that the start and end times of the two services are compatible, in particular with regard to the travel time between the homes of the two beneficiaries concerned.

A route from the source to the sink thus represents a sequence of compatible services, i.e., a daily route. This route will be said to be admissible if it respects all the daily legal constraints. By constructing the graph, we have already made sure that the constraints of continuity and qualifications are respected.

We weight each arc by the travel time between the two homes of the beneficiaries concerned, the duration of the arc’s first service and the waiting time between the two services, in terms of the collective agreements. If we generate a route from the source to the sink by limiting its length, then we can control the amplitude, the effective working time and the waiting time of the route to which it corresponds. By adapting the algorithm proposed in Rizzi et al. (2015), we can efficiently compute all the admissible daily routes for a careworker on a given day.

Once all the routes have been generated, we need to assign one route per careworker per day, to ensure that the weekly and/or monthly legal constraints are respected and that the overall waiting time of the careworkers is minimal. For this purpose, we use a linear integer program to solve this set partitioning problem. We add constraints to ensure that the weekly (or monthly) working regulations defined in the French collective agreements are respected, as well as the human continuity constraints.

The optimization module described above was developed in Java. We have also developed a basic graphical interface in Excel, which also contains all the data relating to the beneficiaries and the staff of the home care service organization under consideration, as well as the parameters resulting from our case study, which are necessary for the execution of the algorithm. The interface provided allows the user to make changes to the database and software settings and then generate routes.

Thanks to dedicated forms, the user can add new beneficiaries or careworkers, modify those who are already entered in the database or delete them. The distance and travel time calculations between beneficiaries are then calculated automatically from the addresses entered, using the data provided by Google Maps via its geolocation API.