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.

Abstract

Efficient bicycle repositioning and vehicle routing are crucial for transportation and logistics systems. Mathematical programming presents fundamental challenges in this area. While vehicle routing problems have been extensively studied since the late 1950s, bicycle repositioning is a relatively newer area of research where already researchers have tackled various combinatorial problems. The goal of the latter is to ensure high service levels and meet user demand, also known as maximizing service level requirements. Dealing with uncertainty adds complexity to both problems. In vehicle routing, the most studied variant considers uncertainty in customers with random demands. Meanwhile, in repositioning, it’s crucial to anticipate uncertain trip demands. This is particularly challenging in real-life bicycle-sharing systems with thousands of stations and high daily trip demands. Currently, state-of-the-art methods struggle to handle large system sizes. In vehicle routing with stochastic demands, exact methods have difficulty solving instances with more than one hundred customers, long routes, and large fleet sizes. This thesis bridges gaps by proposing new exact methods that turn out to be very efficient in practice. While the vehicle routing problem with stochastic demands has a solid theoretical foundation in exact methods, this has not been extended to bicycle repositioning under uncertainty. We leverage this foundation by proposing a new variant of the integer L-shaped method, and we propose implementations for the vehicle routing problem with stochastic demands and bicycle repositioning. Furthermore, we tackle service-level requirements in real-life-sized bicycle-sharing systems by unveiling a new framework centered around an exact method for a newly proposed problem. The aim is to showcase that these new exact algorithmic variants can significantly elevate solutions for not only the stochastic bicycle repositioning problem but also the vehicle routing problem with stochastic demands.