Résolution en temps réel du problème de la prise de rendez-vous dans des tournées de véhicules par apprentissage automatique

The construction of real-time schedules for vehicle rounds is a problem that is present in many industrial domains. This thesis focuses on the homecare sector, where the weekly schedule of nursing staff rounds is dynamically constructed by adding patients requesting service one by one. This problem is actively considered in the literature, and our work focuses on patient insertion, requiring an algorithm that can deliver a real-time response. In the context of dynamic optimization of vehicle routes for patient insertion, this dissertation proposes an innovative machine learning-based method to avoid repeated solving of instances of the Home Health Care Routing and Scheduling Problem (HHCRSP). The problem is first formulated as a linear program representing a variant of the Multi-Depot Capacitated Vehicle Routing Problem with Time Windows (MDCVRPTW). The problem incorporates a double compatibility constraint, time windows for patients and caregivers, and stocks of dressings and syringes, in addition to distinct starting points for each member of the nursing staff, thus ensuring the consistency of the schedules created by the algorithm.

Résumé

La construction de planning en temps réel pour des tournées de véhicules est une problématique présente dans de multiples domaines industriels. Ce mémoire se focalise sur le secteur des services de soins à domicile, où le planning hebdomadaire des tournées du personnel soignant est construit dynamiquement en ajoutant les patients demandant à être servis un à un. Ce problème est activement considéré dans la littérature, et notre travail se focalise sur l’insertion de patients, nécessitant un algorithme pouvant délivrer une réponse en temps réel. Dans le cadre de l’optimisation dynamique des tournées de véhicules pour l’insertion de patients, ce mémoire propose une méthode innovante basée sur l’apprentissage automatique afin d’éviter la résolution répétée d’instances du problème de tournées et de planification des soins à domicile (Home Health Care Routing and Scheduling Problem, HHCRSP). Le problème est d’abord formulé comme un programme linéaire représentant une variante du problème de tournées de véhicules multi-dépôt avec capacités et fenêtres de temps (Multi-Depot Capacitated Vehicle Routing Problem with Time Windows, MDCVRPTW). Le problème intègre une double contrainte de compatibilité, les fenêtres de temps pour les patients et soignants, les stocks de pansements et de seringues, en plus de points de départ distincts pour chaque membre du personnel soignant, assurant ainsi la cohérence des plannings créés par l’algorithme.