Méthodes exactes et approchées pour le problème de planification des soins à domicile

De par le vieillissement de la population ainsi que le souhait des patients de rester le plus longtemps possible chez eux, auprès de leur famille, la dernière décennie a vu émerger la démocratisation des soins à domicile. Ces services peuvent prendre différentes formes telles que des soins infirmiers (piqûres, changement de pansement), de l'aide à la personne (pour prendre un bain, pour manger) ou encore du soutien psychologique. Au-delà du confort de vie qu'ils permettent chez les patients, ces soins à domicile donnent aussi la possibilité aux gouvernements de réduire le flux de patient dans les hôpitaux, de décentraliser les décisions de soins et de réduire le coût de prise en charge des patients. Néanmoins, afin de prendre en compte un maximum de patients tout en gardant un haut niveau de service, il a été montré qu'une planification des visites faite à la main était sousoptimale. Pour parer à cela, de nombreux outils d'aide à la décision ont été développés durant les vingt dernières années. Ces outils, capables de prendre en compte les nombreuses contraintes métier rencontrées par les agences de soins à domicile, permettent de créer en quelques secondes ou quelques minutes, des horaires hebdomadaires optimisés pour des dizaines d'employés. Cette thèse porte sur l'élaboration de ces outils d'aide à la décision et sur l'amélioration des processus opérationnels des agences de soins à domicile. Ces améliorations permettent alors de prendre en charge plus de patients, tout en conservant un haut niveau de service et de bonnes conditions de travail pour le personnel infirmier. Dans la première partie de cette thèse, nous présentons un travail réalisé en collaboration avec une compagnie montréalaise, Alayacare. Dans ce projet, nous listons l'ensemble des contraintes métier rencontrées pour les agences de soins à domicile et nous développons une modélisation du problème sous la forme d'un partitionnement d'ensemble. Pour résoudre le problème, nous développons une matheuristique, se décomposant en deux grandes parties. Tout d'abord un algorithme à voisinage large (LNS) est développé afin d'itérativement générer de nouvelles solutions réalisables et déterminer de nouveaux horaires hebdomadaires possibles pour les soignants. Ensuite, une résolution de la relaxation linéaire du problème de partitionnement d'ensemble, basée sur les horaires trouvés précédemment, est appelée. Sur des instances réelles issues de notre partenaire industriel, cette méthode de résolution a montré que l'on pouvait réduire de 37% le temps de trajet total, mais aussi augmenter de 16% la continuité des soins entre les patients et le personnel soignant. Dans la seconde partie de cette thèse, nous mettons l'emphase sur l'importance d'avoir une régularité dans les heures et jours de visites des patients. Pour cela, nous prenons en compte le fait que les patients restent plusieurs semaines dans le système des agences de soins à domicile et donc, lors de l'acceptation de nouveaux patients, il faut prendre en compte les contraintes associées aux patients existants (jours et heures de visite, personne soignante affectée). L'objectif est alors d'accepter le plus de nouveaux patients possibles, tout en gardant les horaires des patients existants inchangés. Afin de résoudre ce problème, nous reprenons et améliorons une décomposition de Benders et nous développons l'idée d'utiliser des patterns de visites pour les patients (comprenant les jours et heures de visite ainsi que l'employé affecté). Les expérimentations faites sur des instances réelles de la littérature montrent que notre nouvelle formulation permet de réduire drastiquement les temps de calcul. Enfin, nous montrons que pour les instances les plus difficiles à résoudre, nous pouvons adapter la LNS présentée dans l'article 1 afin d'obtenir les solutions optimales pour un temps de calcul ne dépassant pas les 20 secondes. Enfin, le troisième projet de cette thèse consiste à prendre en compte l'aspect dynamique du problème. En effet, nous avons expliqué précédemment que certains patients restaient dans le système durant plusieurs semaines, conservant leurs jours et heures de visites ainsi que leur personnel soignant affecté. Dans cette dernière partie, nous prenons un horizon roulant sur plus d'un an et étudions l'impact des décisions d'acceptation et de planification prises chaque semaine, sur le nombre de visites moyen. Dans ce contexte, nous recevons donc plusieurs offres de patients chaque jour et nous devons décider si le patient peut être accepté et si oui, qui le visitera, quels jours et à quelle heure. Pour cela, nous développons différentes heuristiques et mettons l'emphase sur les effets positifs que permet la flexibilité lors de la planification des visites. Cette flexibilité vient dans un premier temps du moment auquel nous prenons la décision pour l'acceptation des patients (à la réception de l'offre, à la fin de la journée, à la fin de la semaine). L'autre flexibilité vient du fait que l'on va non pas attribuer une heure exacte de visite au patient pour l'ensemble de son plan de soin, mais plutôt une fenêtre de temps, de soixante minutes par exemple, dans laquelle il sera visité. Les résultats de ces différentes heuristiques ainsi que des différentes flexibilités montrent que, sans modifications massives des processus de décision des agences, il est possible d'accepter jusqu'à 12% de visites en plus chaque semaine.

Abstract

Due to the population's aging and people's will to stay at home with family and friends, the last decade has been the decade of home health care services democratization. Those home care services have different aspects such as nursing acts (injection, band-aid replacement),personnal support (bathing, cooking) or social work for the psychological support of the patients. Beyond the fact that those services positively impact patients' life, they also give governments the possibility of reducing flows of patients in the hospitals, decentralize the decisions and reduce the costs. Nevertheless, keeping up a high level of service for the patients is challenging and it has been shown that the manual scheduling of the visits by the head nurses usually leads to sub-optimal solutions. To cope with this issue, decision-making tools have been developed during the last decades in order to help the home care agencies in this scheduling task. These tools, capable to take into account a large set of practical constraints, allow the users to quickly (in a few seconds or minutes) and efficiently design weekly visit schedules for dozens of nurses. This thesis focuses on the elaboration of efficient decision-making tools and resolution methods in the context of home health care services. In the first part of this thesis, we present a work realised in colalboration with a company from Montréal, Alayacare. In this project, we list the different practical constraints met by their users (worldwide home care agencies) and we propose a set partitioning-based formulation. In order to solve the problem, we propose a matheuristic, composed of two main elements. Firstly, a large neighborhood search (LNS) method is implemented, allowing to iteratively generate new feasible solutions and retrieve a set of feasible weekly schedules for the different nurses. Secondly, a relaxed version of the set partitioning is solved using the weekly schedules previously found. On real instances provided by our industrial partner, experiments show that our method allows to reduce by 37% the travel time and increase by 16% the continuity of care between the patients and the nurses. In the second part of this thesis, we focus on the patients' visits' recurrency aspect. To do so, we take into account the fact that patients stay multiple weeks in home care agencies' system and so, when we accept new patients, we have to take into account resource constraints from the existing patients (visit time and days, assigned nurse). The objective is then to maximize the number of new patients accepted without modifying old patients' assignment and scheduling. In order to solve this problem, we extend a Benders decomposition and propose a new decomposition using visit patterns (composed of visit time and days and an assigned caregiver). Computational experiments show that our new decomposition allows to dramatically reduce the computation times on benchmark instances. For the largest instances, we show that we can adapt the LNS proposed in the first paper using visit patterns and solve optimally all the instances in less than 20 seconds. Finally, the third research projet consists in taking into account the dynamic aspect of the home health care services. Indeed, we previously presented the fact that patients stay multiple weeks in the system and so have to be taken as constraints when accepting new patients. In this last part of the thesis, we take into account the rolling horizon aspect of the problem (on more than a year) and we study the impact of the weekly decisions over time. The metric corresponds to the maximization of the average number of weekly visits. In this context, we receive multiple patient offers per day and we have to decide which patients we can accept and how they will be scheduled. To solve this problem, we propose different heuristics and focus on the impact of flexibility during the acceptance and scheduling process. On the one hand, this flexibility corresponds to the moment the decision is taken (when the offer is received, at the end of the day, at the end of the week). On the other hand, we also study flexibility on the visit time and propose not to assign the patients an exact visit time, but rather a visit time window. Results show that those heuristics and the flexiblity we propose allow the home care agencies, without drastic modification of their processes, to dramatically increase the average number of weekly visits with up to 12%.