Dynamic Rebalancing Problems in Bike-sharing Systems

Les systèmes de partage de vélos (BSSs) se sont imposés comme un mode de transport urbain prédominant, offrant une alternative durable et économique pour les usagers. Néanmoins, la nature stochastique de la demande des utilisateurs et la forte demande pendant les heures de pointe entraînent souvent des déséquilibres d’utilisation aux stations lorsque les vélos ne sont pas disponibles là où ils sont nécessaires. Cette thèse de doctorat se concentre sur le développement de stratégies de rééquilibrage dynamiques pour optimiser la distribution des vélos à travers les stations, améliorant ainsi la satisfaction des utilisateurs. La recherche englobe trois projets principaux comme suit : Premièrement, nous proposons un modèle général de programmation linéaire en nombres entiers (PLNE) pour les problèmes de rééquilibrage multi-périodes qui peut être facilement adapté à différentes hypothèses de modélisation. Le modèle propose une stratégie de rééquilibrage pour chaque véhicule, minimisant la demande perdue, qui est la fonction objectif commune dans la littérature. Une analyse complète de diverses hypothèses de modélisation est présentée, incluant la discrétisation temporelle, la distribution des trajets, les domaines de variables et les séquences d’événements (séquences d’arrivées et de départs des clients, et de rééquilibrage des véhicules pendant chaque période). Nous développons un générateur d’instances pour synthétiser des réseaux de stations réalistes et des trajets clients, ainsi qu’un simulateur à granularité fine pour évaluer la performance opérationnelle des stratégies de rééquilibrage obtenues. Des expériences numériques approfondies sont réalisées, tant sur des données synthétiques que réelles, pour analyser l’efficacité des différentes hypothèses et techniques de modélisation. Cette analyse nous permet d’identifier les hypothèses de modélisation qui fournissent empiriquement les stratégies de rééquilibrage les plus efficaces. Deuxièmement, nous intégrons les intervalles d’inventaire et les inventaires cibles, deux concepts souvent utilisés par les opérateurs de BSS, dans le modèle de rééquilibrage PLNE, présentant une approche plus pragmatique pour les opérateurs de BSS. Deux modèles, nommés DROB-I et DROB-T, sont proposés avec des fonctions objectifs innovantes pour minimiser les écarts par rapport à l’intervalle d’inventaire prévu et à l’inventaire cible, respectivement. Un algorithme d’apprentissage automatique est employé pour prévoir l’intervalle et la cible, en tenant compte de diverses caractéristiques telles que les conditions météorologiques, les données historiques de trajets et les informations temporelles. Trois modes de réoptimisation - statique, roulant et pliant - sont mis en oeuvre et comparés entre les modèles, soulignant l’importance de la réoptimisation en réponse aux mises à jour du système. Des expériences numériques approfondies sont réalisées, tant sur des données synthétiques que réelles, pour analyser l’efficacité des modèles proposés. Nos résultats montrent que DROB-I et DROB-T surpassent le modèle de base, apportant jusqu’à 34% de réduction sur la demande perdue pour la planification en horizon roulant en plus de temps d’exécution très rapides. Troisièmement, nous proposons un algorithme basé sur l’apprentissage par renforcement pour les problèmes de rééquilibrage dynamique dans les BSS, formulé comme un processus de décision de Markov. Les espaces d’état et d’action sont conçus dans un cadre temporel continu, permettant une coopération fluide entre plusieurs véhicules de rééquilibrage pour améliorer le réalisme et l’efficacité du rééquilibrage. Pour saisir la dynamique et les incertitudes du système, un simulateur à granularité fine est présenté pour estimer les récompenses sous différents scénarios de demande sensibles aux conditions météorologiques et aux informations temporelles. L’apprentissage profond Q est utilisé pour apprendre la politique qui minimise la demande totale perdue. Des évaluations comparatives démontrent que notre algorithme surpasse les benchmarks, réduisant notamment la demande perdue de 21,5% par rapport à un modèle PLNE.

Abstract

Bike-sharing systems (BSSs) have emerged as a prevalent mode of urban transportation, offering a sustainable and economical alternative for commuters. Nonetheless, the stochastic nature of user trips and high demand during peak hours often lead to station imbalances, where bikes or docks are not available where needed. This Ph.D. thesis focuses on developing dynamic rebalancing strategies to optimize the distribution of bikes across stations, thus improving user satisfaction. The research encompasses the following three principal projects. First, we propose a general Mixed-integer Programming (MIP) framework for multi-period rebalancing problems that can be easily adapted to different modeling assumptions. The model proposes a rebalancing strategy for each vehicle, minimizing lost demand, which is the common objective function in the literature. A comprehensive analysis of various modeling assumptions, including time discretization, trip distribution, variable domains, and event sequences (i.e., sequences of customer arrivals, departures, and vehicles’ rebalancing during each time-period), is presented. We develop an instance generator to synthesize realistic station networks and customer trips, as well as a realistic fine-grained simulator to evaluate the operational performance of the obtained rebalancing strategies. Extensive numerical experiments are carried out, both on synthetic data and on real-world data, to analyze the effectiveness of various modeling assumptions and techniques. Such analysis allows us to identify the modeling assumptions that empirically provide the most effective rebalancing strategies. Second, we incorporate inventory intervals and target inventories, two concepts that the BSS operators often use, into the MIP rebalancing model, presenting a more pragmatic approach for BSS operators. Two models, named DROB-I and DROB-T, are proposed with innovative objective functions to minimize deviations from the predicted inventory interval and target inventory, respectively. A Machine Learning algorithm is employed to forecast the interval and target, considering various features such as weather conditions, historical trip data, and temporal information. Three reoptimization modes – static, rolling, and folding planning – are implemented and compared across models, showcasing the significance of reoptimization in response to system updates. Extensive numerical experiments are carried out, both on the synthetic and real-world data, to analyze the effectiveness of the proposed models. Our results illustrate that DROB-I and DROB-T outperform the baseline model, especially reducing up to 34% of the lost demand in the rolling planning with swift runtimes. Third, we propose a reinforcement learning-based algorithm for dynamic rebalancing problems in BSSs formulated as a Markov decision process. The state and action spaces are crafted within a continuous time framework, enabling seamless cooperation between multiple rebalancing vehicles to enhance the realism and efficiency of rebalancing. To capture the dynamics and uncertainties of the system, a fine-grained simulator is presented to estimate the rewards under different demand scenarios that are sensitive to weather conditions and temporal information. Deep Q learning is utilized to learn the policy, aiming to minimize the total lost demand. Comparative evaluations demonstrate that our algorithm outperforms benchmarks, particularly reducing the lost demand by 21.5% compared to an MIP model.