# Matheuristique pour le routage et la planification de soignants à domicile sous incertitudes

Paul Fleurance, Nadia Lahrichi, Olivier Péton, Maria I Restrepo

► To cite this version:

Paul Fleurance, Nadia Lahrichi, Olivier Péton, Maria I Restrepo. Matheuristique pour le routage et la planification de soignants à domicile sous incertitudes. ROADEF 2025 : 26ème congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Axel Parmentier, Feb 2025, Champs Sur Marne, France. hal-04973646

HAL Id: hal-04973646

https://hal.science/hal-04973646v1

Submitted on 3 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Matheuristique pour le routage et la planification de soignants
à domicile sous incertitudes

Paul Fleurance¹, Nadia Lahrichi², Olivier Péton¹, María I. Restrepo¹

¹ IMT Atlantique, LS2N, UMR CNRS 6004, F-44307 Nantes, France
{paul.fleurance, olivier.peton, maria-isabel.restrepo-ruiz}@imt-atlantique.fr

² Polytechnique Montréal, Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport (CIRRELT)
nadia.lahrichi@polymtl.ca

**Mots-clés** : Soins à domicile, optimisation stochastique, optimisation à 2 niveaux, planification de soignants, tournées de véhicules, matheuristique

## 1 Présentation du Problème

Les structures de soins à domicile emploient des professionnels de santé pour fournir des soins au domicile des patients. Le problème de routage et de planification des soignants consiste à organiser, sur un horizon donné, leurs jours et horaires de travail ainsi que leurs itinéraires [1]. L'ensemble de tâches doit être réalisé dans des fenêtres horaires précises. Les solutions doivent respecter des contraintes légales (durées minimales et maximales de travail quotidien, nombre minimal et maximal de jours de repos hebdomadaires, temps de repos minimal entre deux périodes de travail, nombre maximal de nuits de travail consécutives).

Nous traitons ce problème sur plusieurs jours, en intégrant l'incertitude liée aux temps de service et à la disponibilité des soignants. Nous proposons un programme linéaire stochastique à deux étapes avec les recours suivants : (1) Heures supplémentaires : un soignant peut dépasser les limites légales de travail, (2) Sous-traitance : recours à des soignants externes pour certaines tâches, (3) Retard : un soignant peut arriver hors de la fenêtre prévue, dans une limite acceptable. L'objectif est de minimiser une fonction de coût incluant salaires, frais de transport et recours.

## 2 Approche de Modélisation

Les décisions de première étape concernent la planification des soignants et l'affectation des patients à es soignants. Si un patient ne peut être affecté, ses tâches sont sous-traitées. Les décisions doivent respecter les contraintes suivantes : (i) chaque soignant doit être planifié, (ii) tous les patients doivent être affectés ou sous-traités, (iii) les affectations doivent tenir compte des compétences des soignants, (iv) un soignant au repos ne peut être affecté. Affecter dès la première étape permet de décomposer le problème en sous-problèmes définis pour chaque jour, scénario et soignant. Ces sous-problèmes, des problèmes de voyageur de commerce avec fenêtres de temps (TSPTW), incluent les contraintes de durée minimale et maximale des tournées.

## 3 Approche Matheuristique

**Solution initiale** Le problème de première étape peut être vu comme un problème d'affectation généralisé. Martello et Toth [2] ont proposé une heuristique basée sur le problème de sac-à-dos multiple : chaque sac correspond à un horaire possible pour un soignant un jour donné.
Nous avons adapté cette heuristique pour intégrer les contraintes légales. Une seconde stratégie, que l'on l'appelle *Patient Covering*, consiste à choisir la combinaison soignant/jour/horaire couvrant le maximum de patients. Ce soignant est planifié à cet horaire pour ce jour et affecté aux patients couverts. Le processus se répète tant que les soignants peuvent travailler et qu'il reste des patients à traiter.

**Améliorations** L'observation des solutions a révélé deux axes d'amélioration : (i) des soignants sont parfois planifiés à des horaires où de nombreuses tâches sont à effectuer en fin de période. Cela entraîne des heures supplémentaires évitables si ces tâches étaient reportées à l'horaire suivant. Ces ajustements, appelés *Shift Change*, permettent de générer de nouvelles solutions à tester. (ii) les solutions initiales recourent fréquemment à la sous-traitance. L'amélioration proposée, appelée *Assign Outsourced Patient*, est un processus itératif visant à insérer des patients dans les routes des soignants. À chaque itération, la meilleure insertion par jour est testée, et la meilleure solution globale est retenue.

**Matheuristique** Après ces améliorations, une méthode de recherche par voisinage peut être développée. Sur le principe de la décomposition de Benders [3], la recherche est guidée par l'information duale des sous-problèmes relâchés.

# 4 Résultats préliminaires

Nous avons été confrontés au manque de jeux de données réelles pour ce type de problème. Ainsi nous présentons des tests numériques basés sur des instances générées. Ces instances possèdent un horizon de temps de 5 jours allant jusqu'à 10 infirmières, 164 patients et 266 tâches. Les résultats montrent que les solutions obtenues après la procédure *Assign Outsourced Patient* restent encore loin de l'optimum.

En revanche, l'heuristique trouve en environ 100 secondes des solutions équivalentes à ce que Cplex trouve en 10000 secondes. Cela porte la performance de nos heuristiques à l'ordre de la minute. Ainsi nous pensons pouvoir encore agrandir un peu la taille des instances traitées tout en gardant des temps de résolution raisonnables. Des tests numériques seront menés pour affiner cette limite.

# Références

[1] S. Nickel, M. Schröder, J. Steeg. Mid-term and short-term planning support for home health care services *European Journal of Operational Research*, 3(219):574-587, 2012.

[2] S. Martello, P. Toth. Generalized assignment problem in : *Knapsack problems: algorithms and computer implementations*, 189-220, 1990.

[3] J.F. Benders. Partitioning procedures for solving mixed-variables programming problems. *Numerische Mathematik*, 4: 238-252, 1962.