Скачать книгу

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.

      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 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.

      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.

      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.

      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.

      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

Скачать книгу