Thèse de Michael Saint-Guillain


Sujet :
Modèles et algorithmes pour des problèmes de routage de véhicules en ligne et stochastiques

Résumé :

Quels seront les objectifs et défis des métropoles de demain ? La plupart des problèmes issus du monde réel sont sujets à l’inconnu, nécessitant de prendre de nouvelles décisions de façon dynamique, à la demande, en fonction des évènements aléatoires qui se réalisent. Dans cette thèse, nous nous attaquons à un problème majeur, du moins en perpectives : la gestion dynamique d’une flotte de véhicules en contexte urbain. Les applications pratiques des tournées de véhicules à la demande sont nombreuses, incluant les transports publiques intelligents, les services de livraison, les soins et interventions à domicile, etc. Étant donnés une flotte de véhicules et un ensemble de clients, chacun pouvant potentiellement et à tout moment émettre une requête nécessitant une intervention, l’objectif de cette thèse est de founir une réponse à la question suivante. Étant donné l’état courant à un moment donné, comment gérer notre flotte de véhicules afin de maximiser l’espérance du nombre total de requêtes satisfaites à la fin de la journée ? Ou encore, comment minimiser l’espérance du délai moyen d’intervention de nos véhicules ? Bien entendu, la difficulté réside en ce que la plupart des requêtes, avant d’apparaître dynamiquement, ne sont pas connues. Pour chaque problème, nous considérons qu’il nous est fourni une connaissance, sous forme d’information probabiliste, telle que la probabilité qu’une requête apparaisse à un certain endroit, et à un certain moment de la journée. Grâce à des techniques issues de la recherche opérationnelle et de la programmation stochastique, nous sommes en mesure de construire et résoudre des modèles calculant les actions anticipatives les plus adéquates, comme le redéploiement préventif des véhicules, minimisant le coût total espéré, ou encore maximisant la qualité de service. La question de l’optimisation sous incertitude se pose depuis déjà plusieurs décennies. Grâce aux avancées à la fois théoriques et technologiques, nous sommes chaque jour un peu plus en mesure de palier à l’inconnu. Cependant, la plupart des problèmes intéressants restent extrêmement difficiles à résoudre, si ce n’est impossible. Il reste beaucoup à faire. Cette thèse explore certains concepts fondamentaux de l’optimisation sous incertitude. En intégrant une composante stochastique aux modèles à optimiser, nous verrons ensemble comment il est en effet possible de créer de l’anticipation.


Encadrant : Christine Solnon