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.