1
Towards a Prototype for the Strategic Recomputing of Schedules in Home Care Services

1.1. Introduction

Home healthcare agencies are an alternative to standard medical or paramedical organizations, providing services directly to the beneficiary's home. The aging of Western populations is accompanied by an increase in the number of vulnerable people and an explosion in demand for home healthcare and associated services (Guinet 2014), to which the organizations concerned must adapt. Service routing and scheduling is usually done by hand by experienced employees but this is time-consuming and extremely complex on a large scale. The design of decision support tools is becoming essential to automate the routing and scheduling process and build schedules that are satisfactory for the employer, the careworkers and the beneficiaries.

Having effective solutions to plan interventions is unfortunately not always sufficient to meet the challenge of routing and scheduling in the home care sector. Indeed, many eventualities can make a theoretically optimal schedule unfeasible. It is thus necessary to update the schedules to compensate for these unforeseen events. We are particularly interested in changes in the configuration of staff and beneficiaries of a home healthcare organization. Over the weeks, a beneficiary's state of health can deteriorate, which in turn leads to changes in their needs and therefore in the services required, or even bidding farewell to the organization in the event they require hospitalization, for example. When beneficiaries leave, the establishment can, if the number of careworkers is high enough, accept new beneficiaries who will have to be included in the schedules. Likewise, there is a high turnover of staff because the careworkers are often subjected to difficult, stressful working conditions.

From a strategic, decision-making point of view, it would be inappropriate to recalculate optimal routes every time the schedules are disrupted. In a context where the human aspect is essential, it is necessary to take into account the schedule in progress, the assignments of careworkers or even the start time of the interventions, in order to satisfactorily reconstruct disrupted routes. Indeed, continuity is a key factor in patient satisfaction. Consequently continuity of care constraints must be respected by, on the one hand, keeping fixed start and end times (these are also defined contractually) and on the other hand, always assigning the same group of careworkers to the same patients. In order not to aggravate these instabilities, it is also crucial to take careworker satisfaction into account. Schedules that are not satisfactory for the staff increase staff turnover, which impacts the company's quality of service. In a field where competition is increasingly fierce (Béguin 2018), providing good working conditions is not only a central argument for recruiting qualified careworkers but it also plays a decisive role in limiting turnover.

It is important to note that updating long-term schedules consists of creating new sustainable weekly or monthly schedules, in line with changes to staff and beneficiaries, while short-term rescheduling instead aims to provide a quick fix to the problem; for example, a daily schedule compromised by a one-off disruption, such as the sudden absence of a worker for a day.

In this chapter, we present a prototype developed to respond to a long-term weekly rerouting and rescheduling problem encountered by a home care services company operating in Auvergne Rhône-Alpes, France: Adomni-Quemera. We first offer a brief review of existing work on this theme in the literature, followed by a more specific description of the problem under consideration. In section 1.4, we briefly advance our resolution strategy, before presenting the prototype developed to propose solutions in a practical setting in section 1.5. The experiments carried out on real data are detailed in section 1.6. Finally, we approach avenues of research for future work in section 1.7.

1.2. Literature review

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