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.