Cette thèse traite des méthodes d'optimisation pour la planification proactive des plans de routes d'un grand réseau d'ambulances et la planification réactive pour leur mise à jour durant la journée. Les solutions proactives correspondent au plan du matin qui décide des heures de début de travail des chauffeurs et leurs premières visites. Ce plan doit être robuste au sens de la meilleure acceptation des requêtes qui apparaissent au cours de la journée. Lorsque de nouvelles requêtes sont révélées, les méthodes réactives doivent proposer de les intégrer dans le plan courant en équilibrant l’efficacité et le potentiel d'acceptabilité de futures requêtes.

Les verrous scientifiques attaqués dans la thèse portent sur deux points : (1) l'intégration de contraintes métiers complexes et résistantes aux approches existantes de la littérature, et (2) des problèmes de très grande taille (plusieurs milliers) par rapport à ceux traités par les approches classiques. Les contraintes métiers complexes comportent la recombinaison d'équipages avec changement de véhicules, et la gestion des temps de travail (horaires de début et de fin de journée, plus les pauses).

Pour la planification proactive, une Métaheuristique (Adaptive Large Neighborhood Search) avec des procédures spécifiques pour gérer les verrous précités est proposée. La comparaison de notre algorithme ALNS avec une méthode de planification manuelle montre l’importance de la méthode développée. Notre algorithme se montre aussi très compétitif avec l'état de l'art sur des cas particuliers de notre problème, Resource Constrained Dial-a-ride Problem; Multi Trip Vehicle Routing Problem with Time Windows et Pick-and-Delivery Problem with Time Windows.

Pour la planification réactive un canevas général de stratégies de réoptimisation est proposé et permet d'élaborer à partir de trois paramètres des stratégies variées en terme d'anticipation, de fréquence et de conservatisme. Les meilleures configurations trouvées sont comparées à deux approches manuelles de régulateurs simulées automatiquement.

Le jury de thèse sera composé de :

•                   Andrea-Cynthia DUHAMEL, Université Le Havre Normandie (Rapportrice)
•                   Nacima LABADIE, Université de Technologie de Troyes (Rapportrice)
•                   Marc  SEVAUX, Université de Bretagne-Sud (Examinateur)
•                   Yannick KERGOSIEN, Université de Tours (Examinateur)
•                   Xiaolan XIE, Mines Saint Etienne (Directeur de thèse)
•                   Thierry Garaix, Mines Saint-Étienne (co-encadrant)
•                   Romain ISSART, LOMACO (Invité)
•                  Jérôme VENZAC, LOMACO (Invité)
•                  Alexandre Mazier, Apis-Consulting (Invité).