Читать книгу Healthcare Systems - Группа авторов - Страница 15

The Home Health Care Routing and Scheduling Problem (HHCRSP), i.e. the problem of planning home care routes, appears for the first time – to our knowledge – in 1997 in the article by Begur et al. (1997). Their method is based on adaptations of heuristics derived from algorithms for solving vehicle routing problems (VRP); in particular the classical methods developed in Clarke and Wright (1964) and Lin and Kernighan (1973). The modeling of the HHCRSP as a variant of the VRP is quite classic and Cheng and Rich (1998) were the first to adapt it to mixed-integer linear programming. They model the problem through a multi-depot vehicle routing problem (MDVRP) with multiple time windows, over a single-period horizon. The goal is to minimize overtime and tests are conducted on small case studies, made up of 4 nurses and 10 patients.

Since then, much research has focused on solving such problems, as they constitute a topical issue, both in practice and in the field of research with real scientific obstacles. For further details, the reader can refer to recent literature reviews: Cissé et al. (2017), Fikar and Hirsch (2017), Grieco et al. (2020) and Di Mascolo et al. (2021).

The problem is NP-hard, and thus difficult to solve in practice due to the presence of numerous business and industry-specific constraints, which are often treated with metaheuristics (Decerle et al. 2018) or with decomposition methods, such as the approach developed in the prototype presented here. In Grenouilleau et al. (2017), the authors propose a two-step algorithm to solve the routing and scheduling problem with minimization of overtime, staff qualification constraints and the possibility of not providing all the services requested. An LNS algorithm makes it possible to generate feasible routes, then a set partitioning model whose linear relaxation is repaired through a constructive heuristic, making it possible to select the routes that constitute the final schedule. In Fikar and Hirsch (2015), identification of potential routes precedes the overall scheduling optimization phase. The problem can also be broken down into a first step of assigning services to careworkers, then solving a traveling salesperson (TSP) problem for each of them. Issaoui et al. (2015) add a third step to this decomposition, in which they improve the routes obtained using a heuristic.

Most of the time, the objectives studied relate to the economic aspects of the problem, namely cost minimization (Fathollahi-Fard et al. 2019). However, there is also a particular interest in patient satisfaction (Mosquera et al. 2019). Careworker satisfaction, which is rarely studied, mainly consists of balancing the workload of careworkers (Cappanera and Scutellà 2014). The three stakeholders of the problem, namely the careworkers, the beneficiaries and the employer of the organization, 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).