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.
1.3.2. Objective function
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.
1.4. Resolution method
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.
1.4.1. Route generation
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.
1.4.2. Route selection
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.
1.5. Presentation of the prototype
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.
The parameters relating to the rules that are the result of the collective agreements and internal policies of our applied case can also be modified, as well as the sectorization of the territory covered by the company.
The user provides a previously designed, initial schedule. From the database updated with the latest developments in staff and beneficiaries, the prototype recalculates the routes and generates an Excel file with the list of changes that compares to the initial schedule that was supplied as an input. The decision-maker will thus have the list of reassigned interventions with their date, their start and end times (unchanged since they are contractually fixed), the name of the beneficiary and the name of the newly assigned careworker.
1.6. Tests and results
We conduct our tests across several geographic areas in which Adomni-Quemera operates. We start from the initial weekly schedules established in August 2019 and update this schedule to match the October 2019 beneficiary and stakeholder population, which had changed since August. The results are given in Table 1.1. Each instance is characterized by its number of current beneficiaries, its number of current careworkers and the number of services required for the week. In the “Beneficiary variation” column (resp. “Careworker variation”), we specify the number of changes in the beneficiaries (resp. careworkers) compared to when the initial planning was established. Thus, “+1/-2” means that one person has integrated the organization and that two people have left. Next, we indicate the sum of the waiting times and travel times for all careworkers over the whole week. Finally, we indicate the execution time of the algorithm.
The tests were carried out on a machine with the following characteristics: Intel RCoreTMi5-7440HQ CPU 2.80GHz with 16GB of RAM. The optimization algorithm was developed in Java, and we used CPLEX to solve the PLNE. On each of the instances processed, we have variation in beneficiaries and/or careworkers, for which it should be noted that the overall hourly volume of work and the overall hourly volume of services requested remains similar to those provided in the initial schedule.
Due to the method being exact, we found the optimal solution for each of the proposed instances, that is, the solution that minimizes the overall waiting time of the careworkers. Execution times are very fast (at worst, in the order of a minute on the instances tested). Note that minimizing waiting times produces solutions with very low travel times, except for two instances (4 and 7). Since Instance 7 is the largest in terms of the number of careworkers, the average travel times per careworker are in fact no longer than for the other instances. We can compare the results with Instance 6, which has more careworkers but almost half as many services. The routes are far less busy, involving less travel and therefore less travel time. For Instance 4, because the associated sector is geographically larger, the longer travel times are not surprising. However, as we have no constraints or objectives of minimizing travel times, it is not excluded that there is a solution with equivalent waiting times but shorter travel times.
We can notice that Instances 5 and 6 have a similar number of services. As the variations of careworkers are much greater in Instance 6, the continuity constraints are harder to respect and the graphs constructed through our method are denser. This explains the difference in execution times.
Note