Modèles et algorithmes pour le management de nouveaux services de mobilité urbaine et rurale

L'optimisation combinatoire est un domaine des mathématiques dans lequel un problème consiste à trouver une solution optimale dans un ensemble fini d'objets. Elle a des applications cruciales dans de nombreux domaines, notamment les mathématiques appliquées, le génie logiciel, l'informatique théorique et l'apprentissage automatique.Cette thèse se place dans le champ des travaux en recherche opérationnelle qui cherchent à améliorer le transport des biens et des personnes dans les zones urbaines et rurales. Ce document se concentre sur l'étude de trois problèmes de mobilité dans lesquels seront abordées les contraintes liées aux véhicules autonomes. L'objectif est d'étudier les particularités des problèmes incluant ce type de véhicules, et d'utiliser leurs caractéristiques générales afin de proposer des algorithmes novateurs. Cette étude ne fait partie d'aucun projet industriel particulier et se concentre donc sur les aspects généraux des véhicules autonomes.Ces problèmes de logistique, auxquels nous souhaitons adjoindre les contraintes liées aux véhicules autonomes, sont nombreux et étudiés depuis longtemps. À commencer par le problème de tournées de véhicules dans lequel l'objectif est de trouver les tournées les plus rapides afin de livrer un ensemble de clients avec un nombre fixé de véhicules. De ce problème est né de nombreuses variantes comme le problème de tournées de véhicules avec fenêtres de temps qui est une extension du VRP où chaque client ne peut être servi que pendant une période prédéfinie, appelée fenêtre de temps. Cette thèse se concentre sur trois problèmes de logistiques distincts avec un point commun : des mécanismes de synchronisations sont ajoutés pour répondre aux problématiques des véhicules autonomes.Dans le premier chapitre, nous étudierons un problème de plus court chemin dans un environnement risqué. Ce risque provient des autres véhicules autonomes déjà présent sur place et de leur planning. Il est donc dépendant du temps et nous cherchons à ajouter un nouveau véhicule autonome pour répondre à une tâche non prise en charge par la flotte actuelle. Ce nouveau véhicule devra trouver un chemin jusqu'à sa destination en tenant compte du risque sur son trajet et en adaptant sa vitesse en conséquence. Ce problème a fait l'objet de trois articles dont deux en conférence internationale et un article de journal international.Dans le deuxième chapitre, nous exposerons une idée que nous proposons pour résoudre les problèmes intrinsèquement dépendant du temps : projeter le problème en supprimant la dimension temporelle, résoudre ce problème projeté et construire une solution du problème temporel dont la projection est exactement la solution du problème projeté. Nous appliquerons cette idée à un problème de relocalisation de marchandises sous la forme d'un problème à deux flots (un flot de véhicules et un flot de marchandises) dans lequel la préemption des marchandises est autorisée. La préemption des marchandises est le fait d'autoriser une marchandise à être déchargé par le véhicule qui la transporte afin d'être récupérée par un deuxième véhicule pour continuer son trajet. Cette contrainte, nécessitant la synchronisation des véhicules pour s'échanger des marchandises, est de plus en plus utilisée dans les entrepôts logistiques autonomes et semi-autonomes. Ce problème a fait l'objet d'un article dans une conférence nationale.Dans le troisième chapitre, nous travaillerons sur un problème de synchronisation de deux acteurs, l'un produisant une ressource nécessaire au bon fonctionnement du deuxième. Périodiquement, un transfert de cette ressource doit avoir lieu pour maintenir l'activité du deuxième acteur. Ce problème peut être vu comme l'échange de batteries entre un véhicule autonome électrique et une station de production d'électricité qui va recharger la batterie inutilisée pendant que le véhicule réalise ses tâches. Ce problème a fait l'objet d'un article dans une conférence internationale.