Développement d'une méthode de réoptimisation progressive appliquée à un problème de planification de soins à domicile

La planification dans le domaine médical constitue un enjeu majeur pour assurer la qualité des soins tout en optimisant les ressources disponibles. De nombreuses méthodes opérationnelles permettent d’obtenir des plannings optimaux ou très performants. Cependant, dans la pratique, il est rarement possible d’utiliser directement le planning optimal, car il peut différer fortement du calendrier en vigueur. Ces différences pourraient entraîner de trop fortes contraintes logistiques ou pourraient nuire à la continuité des soins et à la satisfaction des patients et du personnel soignant. Nous proposons donc dans ce travail une méthode générale pour planifier la transition progressive entre une planification existante et une planification optimale, et ce en limitant à chaque étape le nombre de modifications apportées. Cette approche vise à concilier efficacité et stabilité de la planification. Dans un premier temps, nous formulons ce problème sous la forme d’un problème linéaire en nombres entiers (PLNE) afin d’identifier, à chaque itération, la meilleure modification possible dans la limite du nombre de changements autorisés. Pour nous adapter aux contextes dynamiques où les situations évoluent en permanence (nouveaux patients, imprévus..), nous développons ensuite une méthode de recherche arborescente qui permet d’anticiper plus efficacement l’impact des décisions sur l’avenir et d’adapter la planification de manière plus robuste. Pour valider notre approche, nous appliquons notre méthode à un problème de planification de soins à domicile. Nous résolvons ce problème en deux phases : d’abord en résolvant le problème d’affectation (statique puis dynamique), puis en effectuant le routage pour chaque jour et chaque soignant. Ces phases nous permettent de tester nos méthodes sur des cas de complexité croissante. Les résultats expérimentaux montrent la capacité de notre méthode à réparer efficacement la planification initiale. Nous proposons également des recommandations pratiques à destination des décideurs.

Abstract

Effective planning in healthcare is crucial to ensuring high-quality care while making the best use of available resources. Although many operational methods exist to generate optimal or near-optimal schedules, directly implementing these schedules is often impractical, as they can differ substantially from the current ones. Such differences may cause significant logistical challenges and negatively affect continuity of care, as well as the satisfaction of both patients and healthcare staff. In this work, we propose a general approach to manage the gradual transition from an existing schedule to an improved, optimal one, by limiting the number of changes introduced at each step. This strategy seeks to strike a balance between improving efficiency and maintaining schedule stability. Our approach begins by formulating the problem as an integer linear program (ILP), allowing us to identify, at each iteration, the best possible modifications within a predefined limit on the number of changes. To better accommodate dynamic environments, where new patients arrive and unexpected events occur, we develop a tree search method that anticipates the future impact of decisions and adapts the schedule more effectively and robustly. We validate our method on a home healthcare scheduling problem. The problem is tackled in two stages: first, by solving the assignment problem (both in static and dynamic settings),and then by incorporating routing for each day and caregiver. This stepwise progression enables us to evaluate our approach on problems of increasing complexity. Experimental results demonstrate that our method successfully improves the initial schedule while respecting operational constraints. We also offer practical recommendations to assist decision-makers in implementing these strategies.