Modélisation mathémathique et couplage métaheuristique-simulation pour un problème de tournée de véhicules

International audienceNous travaillons sur l'optimisation de tournées dans le cadre de soins à domicile. Le problème s'apparente à un m-TSPTW auquel nous ajoutons des contraintes spécifiques. Chaque patient, caractérisé par un niveau de dépendance, nécessite un ou plusieurs soins que nous appelons activité. Elle est réalisée pendant une fenêtre de temps par une ou plusieurs ressources qui peuvent être de types différents. Chaque patient peut émettre des souhaits en matière de ressources affectées. L'objectif est de construire les tournées de chacune des ressources avec les critères suivants : minimiser la durée des tournées, répartir équitablement les patients de même niveau de dépendance entre les tournées, maximiser la satisfaction des patients en leur affectant au mieux les ressources souhaitées et respecter les temps de travail des ressources. Nous avons proposé un modèle mathématique, une méthode exacte (PLNE) et deux méthodes approchées (métaheuristiques) : PLNE : les contraintes spécifiques sont liées à la synchronisation d'activité et les niveaux de dépendance. Nous avons introduit un degré de compatibilité entre les ressources et les activités qui permet de modéliser les types de ressource et la préférence du patient ou le degré d'expérience des ressources. Métaheuristiques : nous avons adapté les algorithmes du kangourou et du recuit simulé. Nous utilisons 2 voisinages de type insertion et permutation. Nos méthodes sont couplées à un modèle de simulation, qui permet de vérifier la validité des solutions et de calculer la date de début de chaque activité. Nous avons testé les méthodes sur des instances générées aléatoirement (15 activités, 3 ressources et 30 activités, 4 ressources) ainsi que sur une instance réelle de 150 activités, 15 ressources.