💻 computer science

Meeting equity requirements in shared micromobility rebalancing: a constrained Markov decision process with a case study in The Hague

Cet article propose un cadre de processus de décision markovien contraint (CMDP) utilisant l'apprentissage Q-factorisé de type Lagrangien pour optimiser le rééquilibrage de la micromobilité partagée en imposant explicitement des seuils d'équité sur les taux d'échec de service, validé à travers des réseaux synthétiques et une étude de cas réelle à La Haye.

Auteurs originaux : Lorenzo Rota, Canmanie T. Ponnambalam, Thiago D. Simão

Publié 2026-07-08

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Lorenzo Rota, Canmanie T. Ponnambalam, Thiago D. Simão

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez une ville remplie de vélos ou de trottinettes en libre-service. En ce moment, ces véhicules agissent souvent comme une fête populaire : tout le monde veut aller là où l'amusement se trouve (le centre-ville), donc les véhicules s'y entassent. Pendant ce temps, les quartiers plus calmes en périphérie de la ville se retrouvent vides. Si vous habitez dans ces zones extérieures, vous pourriez avoir besoin d'un trajet mais ne trouver aucun véhicule disponible.

Les gestionnaires de ces systèmes de vélos essaient généralement de déplacer les véhicules pour maximiser leurs profits. Cela aggrave naturellement le problème, car ils continuent d'envoyer des vélos vers les centres urbains et riches, tout en ignorant les banlieues pauvres.

Les villes commencent à dire : « Stop ! Nous avons besoin d'équité. » Elles veulent s'assurer que même les quartiers en périphérie disposent de suffisamment de vélos. Mais voici le problème : dire à un ordinateur « Soyez équitable » est vague. Si vous dites simplement à un ordinateur d'« essayer d'être équitable », il doit deviner l'intensité de cet effort. C'est comme dire à un chef : « Rendez la soupe un peu moins salée », sans préciser exactement quelle quantité de sel retirer. Le chef pourrait se tromper dans sa supposition, rendant la soupe trop fade ou pas assez salée, et il devra continuer à goûter et à ajuster jusqu'à ce qu'il obtienne le résultat voulu.

La solution du papier : La « limitation de vitesse » pour les vélos

Les auteurs de ce papier ont trouvé une manière plus intelligente de parler à l'ordinateur. Au lieu de lui demander de « deviner » comment être équitable, ils lui ont donné une règle stricte, comme une limitation de vitesse.

L'ancienne méthode (Reward Shaping / Mise en forme de la récompense) : L'ordinateur reçoit un score pour chaque mouvement. S'il déplace un vélo vers un quartier pauvre, il reçoit quelques points supplémentaires. Mais l'ordinateur doit deviner combien de points sont nécessaires pour que l'effort en vaille la peine. C'est un jeu d'essais et d'erreurs.
La nouvelle méthode (Constrained Decision Making / Prise de décision sous contrainte) : La ville fixe la règle : « Aucun quartier ne peut avoir plus de 5 % de clients ne parvenant pas à trouver un vélo. » L'ordinateur ne devine pas. Il doit trouver le moyen le moins coûteux de déplacer les vélos tout en respectant strictement cette règle. S'il enfreint la règle, il reçoit une lourde pénalité. S'il la respecte, il peut maintenir ses coûts bas.

Comment ça marche : Le policier de la circulation et les zones

Les chercheurs ont divisé la ville en différents types de quartiers (zones), du centre très dense jusqu'aux périphéries lointaines. Ils ont créé un « policier de la circulation » pour chaque type de quartier.

La Règle : La ville fixe une limite de « taux d'échec » (par exemple : « Seulement 5 % des gens dans les zones extérieures peuvent échouer à trouver un vélo »).
L'Étiquette de Prix : L'ordinateur utilise un outil spécial appelé « méthode Lagrangienne ». Considérez cela comme un prix dynamique.
- Si les quartiers extérieurs manquent de vélos et que des gens ne parviennent pas à en trouver, le « prix » de l'échec augmente. L'ordinateur voit ce prix élevé et se dit : « Oh non, je dois déplacer plus de vélos là-bas pour éviter cette pénalité coûteuse ! »
- Si les quartiers ont suffisamment de vélos, le prix baisse, et l'ordinateur arrête de gaspiller de l'argent à déplacer des vélos là-bas.
Le Résultat : L'ordinateur apprend la stratégie exacte pour maintenir le taux d'échec sous la limite fixée tout en dépensant le moins d'argent possible.

Ce qu'ils ont découvert

Les chercheurs ont testé cela de deux manières :

Une ville fictive (Réseau synthétique) : Ils ont créé une simulation informatique d'une ville. Ils ont trouvé que cette nouvelle méthode pouvait atteindre les objectifs exacts de « taux d'échec » fixés par la ville. Si la ville disait : « Nous voulons 5 % ou moins », le système délivrait 5 % ou moins.
- Le Coût : À mesure que la ville exigeait des règles plus strictes (par exemple, faire passer le taux d'échec de 10 % à 5 %), le coût de déplacement des vélos augmentait. Cela est logique : il coûte plus cher d'assurer que tout le monde ait un vélo que de laisser tous les vélos dans les zones denses.
- La Métrique : Ils ont également découvert qu'une façon courante de mesurer l'équité (appelée « indice de Gini ») était en fait un mauvais outil pour ce travail. C'est comme mesurer l'équité par le degré d'égalité entre tous. Mais le but ici n'est pas de rendre tout le monde égal ; le but est de s'assurer que les personnes les plus défavorisées aient suffisamment de ressources. La nouvelle méthode a amélioré les situations des zones les plus mal loties sans nuire aux zones plus aisées, ce qui a en réalité rendu le score d'« égalité » moins bon, bien que la situation des plus pauvres se soit améliorée.
Une vraie ville (La Haye, Pays-Bas) : Ils ont appliqué cela à des données réelles de La Haye, en utilisant l'emplacement réel des stations de vélos et des enquations de déplacement.
- Ils ont construit un modèle du réseau de vélos de la ville.
- Ils ont montré que même avec des données réelles et désordonnées, le système pouvait apprendre une stratégie pour respecter les règles.
- Le Bémol : Lorsque les règles étaient fixées de manière extrêmement stricte (comme un taux d'échec de 0,5 %), le système avait un peu de mal dans les plus petits quartiers très volatils. Il est difficile de garantir la perfection dans chaque petit point isolé lorsque l'on utilise une stratégie globale pour un groupe de quartiers. Cependant, pour des règles raisonnables, cela fonctionnait bien.

L'essentiel à retenir

Ce papier montre que les villes n'ont pas besoin de deviner comment rendre les vélos en libre-service équitables. Au lieu de donner des instructions vagues aux opérateurs, elles peuvent fixer une limite claire et ferme sur le nombre de personnes laissées sans trajet. L'ordinateur peut ensuite déterminer la manière la plus rentable de respecter cette limite. Cela transforme un objectif vague d'« équité » en un plan concret, réalisable et doté d'un coût connu.

Résumé technique : Exigences d'équité de réunion dans le rééquilibrage de la micromobilité partagée

Énoncé du problème
Les systèmes de micromobilité partagée reproduisent souvent les inégalités urbaines en concentrant les véhicules dans les zones de forte demande, centrales et riches, tout en laissant les zones périphériques et à faibles revenus sous-desservies. Les politiques de rééquilibrage standard, qui visent généralement à maximiser les revenus, exacerbent ce « fractionnement urbain » (splintering urbanism). Bien que les villes imposent de plus en-cours des exigences d'équité — telles qu'un nombre minimum de véhicules dans des zones spécifiques — les méthodes opérationnelles actuelles peinent à satisfaire ces mandats de manière efficace. Les approches existantes par apprentissage par renforcement (RL) tentent d'intégrer l'équité en ajoutant une pénalité pondérée à la fonction de récompense. Cependant, cette méthode repose sur un réglage par tâtonnement du poids de la pénalité, n'offrant aucune garantie directe qu'un seuil réglementaire spécifique (par exemple, un taux maximal de défaillance de service) sera respecté, et ne fournit pas non plus d'analyse coût-bénéfice claire pour durcir ces règles.

Méthodologie
Les auteurs proposent de reformuler le problème de rééquilibrage de la flotte comme un Processus de Décision Markovien Contraint (CMDP). Au lieu d'encoder l'équité de manière implicite via un façonnage de la récompense (reward shaping), la méthode traite l'équité comme une contrainte explicite sur le taux de défaillance de service (la part des utilisateurs ne trouvant aucun véhicule).

Formulation : La zone de service est partitionnée en zones regroupées par catégories (de la périphérie au centre). Le problème est modélisé comme un MDP où l'état inclut la période temporelle, la catégorie de zone et l'inventaire des véhicules. L'objectif est de maximiser la récompense à long terme (minimiser les coûts de rééquilibrage et les pénalités de flotte) sous réserve d'une contrainte : le taux de défaillance de service attendu pour chaque catégorie de zone et chaque période ne doit pas dépasser un seuil défini par la ville ( $r_{max}$ ).
Algorithme de résolution : Le CMDP est résolu par un Q-learning Lagrangien factorisé.
- Relaxation Lagrangienne : La contrainte est dualisée par l'introduction d'une pénalité adaptative (une variable duale $\lambda$ ) pour chaque catégorie et période. Cette variable agit comme un prix pour les défaillances de service, augmentant lorsque les défaillances dépassent la cible et diminuant lorsqu'elles tombent en dessous.
- Factorisation : En supposant l'indépendance de la demande entre les zones, le problème est décomposé en sous-problèmes par zone gérés par un agent par catégorie. Toutes les zones d'une même catégorie partagent une table Q unique, mise à jour par l'expérience combinée de toutes les zones de cette catégorie.
- Mises à jour Primal-Dual : L'algorithme alterne entre la mise à jour des valeurs Q (primal) pour optimiser la récompense modifiée (récompense de base moins $\lambda \times$ défaillances) et la mise à jour des variables duales (dual) basées sur la violation moyenne de la contrainte de défaillance sur une fenêtre glissante.
Adaptation au monde réel : Pour le cas d'étude à La Haye, les auteurs ont adapté le modèle pour gérer des zones aux capacités inégales en normalisant l'inventaire des véhicules en une fraction d'occupation ($0 $à$ 1$). Ils ont construit des zones de service en utilisant un clustering k-means pondéré des emplacements de stations et ont estimé la demande à partir de données d'enquêtes nationales de déplacements (ODiN) et de registres d'adresses.

Contributions clés

Satisfaction directe des contraintes : La méthode permet à une ville de spécifier directement un taux maximal de défaillance de service, éliminant ainsi le besoin de réglage par tâtonnement des poids d'équité. L'algorithme ajuste automatiquement la stratégie de rééquilibrage pour respecter la limite.
Transparence des coûts : L'approche quantifie le coût opérationnel pour répondre à des objectifs d'équité spécifiques. Elle démontre qu'à mesure que la limite du taux de défaillance se durcit, le coût de rééquilibrage augmente, permettant aux villes d'évaluer le prix de règles plus strictes avant leur adoption.
Sélection de métriques : L'article soutient que l'indice de Gini est mal adapté pour imposer un « plancher de service ». Si le façonnage de la récompense (qui égalise les taux) réduit l'indice de Gini, l'approche contrainte maintient un service élevé dans les zones centrales tout en améliant les zones périphériques. Cela peut faire stagner, voire augmenter légèrement, l'indice de Gini alors que le taux de défaillance dans le pire des cas s'améliore, faisant du taux de défaillance du pire cas une métrique plus appropriée pour cet objectif spécifique.
Applicabilité réelle : Une étude de cas à La Haye démontre que la méthode peut être instanciée en utilisant des données publiques (flux de stations, registres d'adresses et enquêtes de déplacement) pour générer une stratégie de rééquilibrage entraînée.

Résultats

Réseau synthétique : Sur un réseau synthétique à cinq catégories, la méthode a réussi à respecter les seuils de taux de défaillance spécifiés pour toutes les catégories de zones et périodes. À mesure que la limite ( $r_{max}$ ) se resserrait de 100 % à 5 %, le taux de défaillance du pire cas diminuait de manière monotone, tandis que le coût de rééquilibrage doublait approximativement. Les zones centrales n'ont pas été affectées par les contraintes, tandis que les zones périphériques ont vu une amélioration significative de la disponibilité.
Comparaison avec le façonnage de la récompense : Comparée à la ligne de base du façonnage de la récompense, l'approche contrainte n'a pas dégradé le service dans les zones centrales bien desservies pour réduire l'écart. Au contraire, elle a concentré les ressources sur les zones sous-desservies pour atteindre le seuil absolu.
Étude de cas de La Haye : Appliqué à des données réelles, le système performait déjà bien (environ 2,8 % de taux de défaillance dans le pire des cas sans contraintes). Testé avec des limites plus strictes, la méthode a répondu en augmentant la taille de la flotte et les opérations de rééquilibrage. Cependant, aux limites les plus serrées (0,5 % et 0,75 %), les zones les plus périphériques ont légèrement dépassé la limite en raison de la factorisation par catégorie (partage d'une stratégie unique pour des zones de tailles différentes), soulignant un compromis entre efficacité computationnelle et contrôle granulaire.

Signification et affirmations
Les auteurs affirment que ce travail comble le fossé entre les exigences d'équité réglementaires et la prise de décision opérationnelle. En formulant le rééquilibrage comme un CMDP, la méthode transforme un objectif d'équité en un paramètre de planification doté d'un prix connu. Elle permet aux villes d'imposer des règles basées sur les résultats (niveaux de service) plutôt que sur des intrants prescriptifs (nombre de véhicules), s'alignant sur les recommandations d'organismes tels que le Forum international des transports. L'article conclut que cette approche offre une voie viable vers la réalisation des objectifs de développement durable 11.2 de l'ONU, en fournissant un mécanisme pour maintenir un plancher de service dans les zones mal desservies sans compromettre l'efficacité du reste du réseau. Les auteurs restent modestes, notant que le modèle actuel suppose une demande indépendante et des instants de rééquilibrage fixes, et que des travaux futurs sont nécessaires pour traiter les corrélations de la demande, le rééquilibrage intra-période et l'adaptation en ligne aux changements de modèles de demande.

Articles similaires