Algorithms for the Stochastic Bicycle Repositioning Problem and the Stochastic Vehicle Routing Problem

Un repositionnement efficace des vélos et les tournées des véhicules sont cruciaux pour les systèmes de transport et de logistique. La programmation mathématique présente des défis fondamentaux dans ce domaine. Alors que les problèmes de tournées de véhicules ont été largement étudiés depuis la fin des années 1950, le repositionnement des vélos est un domaine de recherche relativement récent dans lequel les chercheurs se sont déjà attaqués à divers problèmes combinatoires. L’objectif de ce dernier est d’assurer des niveaux de service élevés et de répondre à la demande des utilisateurs, également appelé maximisation des exigences de niveau de service.Faire face à l’incertitude ajoute à la complexité des deux problèmes. Dans le domaine des tournées de véhicules, la variante la plus étudiée prend en compte l’incertitude des clients ayant des demandes aléatoires. Parallèlement, lors du repositionnement, il est crucial d’anticiper les demandes de voyage incertaines. Cela est particulièrement difficile dans les systèmes de partage de vélos réels, avec des milliers de stations et des demandes de déplacements quotidiens élevées. Actuellement, les méthodes de pointe ont du mal à gérer des systèmes de grande taille. Dans les tournées de véhicules avec des demandes stochastiques, les méthodes exactes ont du mal à résoudre les instances comportant plus d’une centaine de clients, de longues tournées et des flottes de grande taille. Cette thèse comble les lacunes en proposant de nouvelles méthodes exactes qui se révèlent très efficaces en pratique. Bien que le problème des tournées de véhicules avec des demandes stochastiques repose sur une base théorique solide en termes de méthodes exactes, cela n’a pas été étendu au repositionnement des vélos dans des con-ditions d’incertitude. Nous exploitons cette base en proposant une nouvelle variante de la méthode en forme de L en nombre entière, et nous proposons des implémenta-tions pour le problème de tournées de véhicules avec des demandes stochastiques et le repositionnement des vélos. De plus, nous abordons les exigences de niveau de ser-vice dans les systèmes de partage de vélos grandeur nature en dévoilant un nouveau cadre centré autour d’une méthode exacte pour un problème nouvellement proposé. L’objectif est de montrer que ces nouvelles variantes algorithmiques exactes peuvent considérablement améliorer les solutions non seulement pour le problème de reposi-tionnement stochastique des vélos, mais également pour le problème de tournées de véhicules avec des demandes stochastiques.