Vehicle routing problem with synchronization constraints in home care support services - Mathematical formulation and hybridization based on metaheuristics

Nous nous sommes intéressés à la problématique d’organisation des tournées de soins à domicile dans le cadre de structures de maintien à domicile comme par exemple les service d’Hospitalisation À Domicile ou les Services de Soins Infirmiers À Domicile. Les soins sont prodigués au domicile des patients par un ou deux soignants d’un type défini, comme médecin ou infirmier par exemple pendant une période de disponibilité du patient. Le patient est caractérisé par un niveau de dépendance et peut exprimer une préférence pour être soigné par un soignant plutôt qu’un autre. L’objectif est de construire les tournées des soignants en rendant visite à tous les patients tout en minimisant la longueur (ou durée) des tournées, en équilibrant les tournées suivant le niveau de dépendance des patients et en favorisant la préférence des patients. Après avoir réalisé un état de l’art des problèmes d’organisation de tournées de soins à domicile, nous proposons deux modélisations mathématiques de notre problème sous la forme d’un multiple Traveling Salesman Problem avec fenêtres de temps (m-TSPTW) auquel s’ajoute des contraintes spécifiques comme la synchronisation d’activités ou la prise en compte de types de ressource et des critères de performance propres au problème (équilibrage et préférence). Nous avons ensuite proposé des méthodes approchées basées sur des couplages métaheuristique - modèle de simulation testées sur des instances de la littérature d’un problème proche du nôtre et des instances adaptées à notre problème. Pour terminer, nous abordons trois perspectives de recherche :- la réorganisation des tournées suite à l’absence d’un soignant,- la prise en compte de temps de transport stochastique,- la localisation de structures de maintien à domicile et l’impact sur la construction des tournées.We are interested in a routing problem within the context of home health care. The cares are provided by one or two caregivers with the required type at the patient’s home during the patients’ availability. A type is doctor or nurse for instance. Each patient is characterized by a dependency level and may give a preference for a caregiver. The goal is to construct the tour for each caregiver visiting all patients, minimizing the length of the tours, balancing the workload of the caregivers and maximizing the satisfaction of the patients. We present a state of the art of the home health care problem. Then we propose two mathematical models of our problem based on the multiple Traveling Salesman Problem with Time Windows (m-TSPTW) with specific constraints like the activities’s synchronization or ressources’ type. The performance criteria are specific of our problem : workload balancing and patients’ satisfaction. We then propose approached methods based on combination between Metaheuristics and simulation model. This méthods have been tested on dataset from the literature and dataset adapted to our problem. We conclude with three research perspectives :- the reorganization of the tours when a caregiver is not available,- the integration of stochastic transport time,- the location of home support structure and its impact on the routes’ construction