generally have divergent interests and objectives. In Carello et al. (2018), a linear program, with several objective functions integrated into a threshold method, makes it possible to establish a compromise between all the stakeholders of the problem.
While the research cited above addresses the problem of static scheduling, it should be noted that in the home healthcare industry, it is rare to be able to maintain a functional schedule over a long period. Indeed, the instability inherent in the health sector quickly makes scheduling obsolete or not suited in the dynamic aspects of the problem (Cappanera et al. 2018).
In Heching et al. (2019), a Benders decomposition is used to accurately solve the problem of re-scheduling following the departure or arrival of patients. The first step is to solve an assignment problem with a mixed linear program. Next, a constraint programming model is used to plan the routes. The objective is to maximize the number of patients visited over a weekly period while respecting continuity constraints. In Nickel et al. (2012), the re-scheduling problem is solved by integrating new patients into the system with an insertion heuristic, then improving the solution with an LNS-type algorithm. The evolution of the patient population is considered in these two articles, while the composition of the staff remains unchanged.
In the literature, a wide range of constraints and objectives have been considered. However, much of the work remains theoretical and does not make it possible to deal with actual cases or to offer operational solutions given that, for example, legal constraints are often only partially addressed. In Szander et al. (2018), the authors want to reduce this gap between theoretical research and real-life situations through a case study of a home care center in Hungary, where the appointment times are fixed, and the objective is to minimize travel costs while maximizing beneficiary satisfaction through an MILP. In Gomes and Ramos (2019), the authors deal with a re-scheduling problem with the constraints of non-continuity of care that are not very common in the literature but which stem from actual cases encountered in Portugal: a non-profit organization and a Catholic parish where part of their mission is home help. Using different mixed linear programs, they are developing a multi-objective approach that aims to reduce travel times while minimizing the disruption associated with the departure and arrival of new patients. Once again, careworker changes are not considered here.
Thus, more and more works are interested in actual cases, even though their applied aspect is often limited to experiments on real data. Nevertheless, a few methods developed in direct relation with actors in the sector have made it possible to develop prototypes that can be used in practice and even software that is now deployed in practice. To the best of our knowledge, the first decision support system for this type of problem was proposed by Begur et al. (1997). An optimization module for the routing phase is integrated into a geographic information system that allows us to view routes. The LAPS CARE tool (Eveborn et al. 2006), now used in care units in Sweden, makes it possible to plan routes according to patient preferences and Swedish regulations. The proposed routes do not necessarily satisfy all the constraints and must be modified by the users when necessary. However, the scheduling task is made easier through the use of this tool, especially when it comes to quickly re-optimizing routes to deal with a last-minute, unforeseen event. More recently, a decision support system was created to support the Ottawa Hospital in its setup for home dialysis (Kandakoglu et al. 2020). Schedules are set by the day and last-minute disruptions are managed with the help of “floating” nurses who can act as replacements at a moment’s notice.
Here, we are interested in a real-world scenario that includes more constraints than most of the work in the literature, as we consider almost all of the constraints arising from French national collective agreements (lunch breaks, work shifts, effective working time). We pay particular attention to the continuity of care, which constitutes a real scientific challenge. We consider the variations in beneficiaries as well as in the staff, and consider updating schedules on a strategic level, while most of the work in the literature is concerned with managing disruptions in the shorter term. Our aim is to propose solutions applicable in practice which therefore respect both the legislation and several rules of use and internal functioning of the organization with which we collaborate. We present a prototype whose objective is to allow the decision-makers to generate new schedules themselves, to keep the database up-to-date as careworkers and beneficiaries evolve. It should be noted that we find optimal solutions for real-size instances (up to 92 beneficiaries and 337 services).
1.3. Description of the problem
We consider the case of a home care organization that employs careworkers characterized by different levels of qualifications, specific time availability and a contractual and individualized monthly work volume. The organization plans its routes to provide a set of services required by a set of beneficiaries who need careworkers with different qualifications.
We assume that a schedule has already been established but has become obsolete due to changes in staff or beneficiaries. We consider the cases where one or more beneficiaries and/or careworkers leave the organization and where new beneficiaries and/or careworkers must instead be integrated into the schedules.
1.3.1. Constraints
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.
1.3.1.1. Continuity constraints
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.
1.3.1.2. Legal constraints
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.
1.3.1.3. Internal policies
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