💻 computer science

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

This paper proposes a constrained Markov decision process (CMDP) framework using factorized Lagrangian Q-learning to optimize shared micromobility rebalancing by explicitly enforcing equity thresholds on service failure rates, validated through both synthetic networks and a real-world case study in The Hague.

Original authors: Lorenzo Rota, Canmanie T. Ponnambalam, Thiago D. Simão

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lorenzo Rota, Canmanie T. Ponnambalam, Thiago D. Simão

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a city full of shared bikes or scooters. Right now, these vehicles often act like a popular party: everyone wants to go where the fun is (the city center), so the vehicles pile up there. Meanwhile, the quieter neighborhoods on the edge of town get left empty. If you live in those outer areas, you might need a ride but find none available.

The people who run these bike systems usually try to move vehicles around to make the most money. This naturally makes the problem worse, because they keep sending bikes to the busy, wealthy centers and ignoring the poorer outskirts.

Cities are starting to say, "Stop! We need fairness." They want to make sure that even the neighborhoods on the edge have enough bikes. But here's the problem: telling a computer, "Be fair," is vague. If you just tell a computer to "try to be fair," it has to guess how hard to try. It's like telling a chef, "Make the soup a little less salty," without saying exactly how much salt to remove. The chef might guess wrong, making the soup too bland or not salty enough, and they have to keep tasting and adjusting until they get it right.

The Paper's Solution: The "Speed Limit" for Bikes

The authors of this paper came up with a smarter way to talk to the computer. Instead of asking it to "guess" how to be fair, they gave it a strict rule, like a speed limit.

The Old Way (Reward Shaping): The computer gets a score for every move. If it moves a bike to a poor neighborhood, it gets a few extra points. But the computer has to guess how many points are enough to make it worth the effort. It's a game of trial and error.
The New Way (Constrained Decision Making): The city says, "Here is the rule: No neighborhood can have more than 5% of riders fail to find a bike." The computer doesn't guess. It has to find the cheapest way to move bikes that strictly obeys this rule. If it breaks the rule, it gets a heavy penalty. If it follows the rule, it gets to keep its costs low.

How It Works: The Traffic Cop and the Zones

The researchers divided the city into different types of neighborhoods (zones), from the very center to the far edges. They created a "traffic cop" for each type of neighborhood.

The Rule: The city sets a "failure rate" limit (e.g., "Only 5% of people in the outer zones can fail to find a bike").
The Price Tag: The computer uses a special tool called a "Lagrangian method." Think of this as a dynamic price tag.
- If the outer neighborhoods are running out of bikes and people are failing to find them, the "price" of failing goes up. The computer sees this high price and thinks, "Oh no, I need to move more bikes there to avoid this expensive penalty!"
- If the neighborhoods have plenty of bikes, the price drops, and the computer stops wasting money moving bikes there.
The Result: The computer learns the exact strategy to keep the failure rate under the limit while spending the least amount of money possible.

What They Found

The researchers tested this in two ways:

A Fake City (Synthetic Network): They created a computer simulation of a city. They found that this new method could hit the exact "failure rate" targets the city set. If the city said, "We want 5% or less," the system delivered 5% or less.
- The Cost: As the city demanded stricter rules (e.g., dropping the failure rate from 10% to 5%), the cost of moving bikes went up. This makes sense: it costs more money to ensure everyone has a bike than to just let the busy areas have them all.
- The Metric: They also discovered that a common way to measure fairness (called the "Gini index") was actually a bad tool for this job. It's like measuring fairness by how equal everyone is. But the goal here isn't to make everyone equal; it's to make sure the worst-off people have enough. The new method improved the worst-off areas without hurting the well-off areas, which actually made the "equality" score look worse, even though the situation for the poor got better.
Real City (The Hague, Netherlands): They applied this to real data from The Hague, using actual bike station locations and travel surveys.
- They built a model of the city's bike network.
- They showed that even with real-world messy data, the system could learn a strategy to meet the rules.
- The Catch: When they set the rules extremely tight (like 0.5% failure rate), the system struggled a bit in the smallest, most volatile neighborhoods. It's hard to guarantee perfection in every single tiny spot when you are using one strategy for a whole group of neighborhoods. However, for reasonable rules, it worked well.

The Bottom Line

This paper shows that cities don't have to guess how to make shared bikes fair. Instead of giving vague instructions to the operators, they can set a clear, hard limit on how many people are left without a ride. The computer can then figure out the most cost-effective way to meet that limit. It turns a vague goal of "fairness" into a concrete, achievable plan with a known price tag.

Technical Summary: Meeting Equity Requirements in Shared Micromobility Rebalancing

Problem Statement
Shared micromobility systems often reproduce urban inequities by concentrating vehicles in high-demand, central, and wealthy areas while leaving peripheral and low-income zones underserved. Standard rebalancing policies, which typically maximize revenue, exacerbate this "splintering urbanism." While cities increasingly impose equity requirements—such as minimum vehicle shares in specific zones—current operational methods struggle to meet these mandates efficiently. Existing reinforcement learning (RL) approaches attempt to integrate fairness by adding a weighted penalty to the reward function. However, this method relies on trial-and-error tuning of the penalty weight, offering no direct guarantee that a specific regulatory threshold (e.g., a maximum service-failure rate) will be met, nor does it provide a clear cost-benefit analysis for tightening such rules.

Methodology
The authors propose a reformulation of the fleet rebalancing problem as a Constrained Markov Decision Process (CMDP). Instead of encoding fairness implicitly via reward shaping, the method treats equity as an explicit constraint on the service-failure rate (the share of users finding no vehicle).

Formulation: The service area is partitioned into zones grouped into categories (from peripheral to central). The problem is modeled as an MDP where the state includes the time period, zone category, and vehicle inventory. The objective is to maximize long-term reward (minimizing rebalancing costs and fleet penalties) subject to a constraint: the expected service-failure rate for each zone category and time period must not exceed a city-defined threshold ( $r_{max}$ ).
Solution Algorithm: The CMDP is solved using Factorized Lagrangian Q-learning.
- Lagrangian Relaxation: The constraint is dualized by introducing an adaptive penalty (a dual variable $\lambda$ ) for each category and period. This variable acts as a price for service failures, increasing when failures exceed the target and decreasing when they fall below it.
- Factorization: Assuming demand independence across zones, the problem is decomposed into per-zone sub-problems managed by one agent per category. All zones within a category share a single Q-table, updated by the combined experience of all zones in that category.
- Primal-Dual Updates: The algorithm alternates between updating the Q-values (primal) to optimize the modified reward (base reward minus $\lambda \times$ failures) and updating the dual variables (dual) based on the average violation of the failure constraint over a sliding window.
Real-World Adaptation: For the case study in The Hague, the authors adapted the model to handle zones with unequal capacities by normalizing vehicle inventory to an occupancy fraction ($0$ to $1$). They constructed service zones using weighted k-means clustering of station locations and estimated demand using national travel survey data (ODiN) and address registries.

Key Contributions

Direct Constraint Satisfaction: The method allows a city to specify a maximum service-failure rate directly, eliminating the need for trial-and-error tuning of fairness weights. The algorithm automatically adjusts the rebalancing strategy to meet the bound.
Cost Transparency: The approach quantifies the operational cost of meeting specific equity targets. It demonstrates that as the failure-rate bound tightens, the rebalancing cost increases, allowing cities to evaluate the price of stricter rules before adoption.
Metric Selection: The paper argues that the Gini index is ill-suited for enforcing a "service floor." While reward shaping (which equalizes rates) reduces the Gini index, the constrained approach maintains high service in central zones while improving peripheral zones. This can cause the Gini index to stall or even rise slightly as the worst-case failure rate improves, making the worst-case failure rate a more appropriate metric for this specific goal.
Real-World Applicability: A case study in The Hague demonstrates that the method can be instantiated using publicly available data (station feeds, address registries, and travel surveys) to generate a trained rebalancing strategy.

Results

Synthetic Network: On a synthetic five-category network, the method successfully met specified failure-rate thresholds across all zone categories and time periods. As the bound ( $r_{max}$ ) tightened from 100% to 5%, the worst-case failure rate decreased monotonically, while the rebalancing cost roughly doubled. The central zones remained unaffected by the constraints, while peripheral zones saw significant improvements in availability.
Comparison with Reward Shaping: Compared to the reward-shaping baseline, the constrained approach did not degrade service in well-served central zones to narrow the gap. Instead, it focused resources on the underserved zones to meet the absolute threshold.
The Hague Case Study: Applied to real data, the system already performed well (approx. 2.8% failure rate in the worst case without constraints). When tested with stricter bounds, the method responded by increasing fleet size and rebalancing operations. However, at the tightest bounds (0.5% and 0.75%), the most peripheral zones slightly exceeded the limit due to the per-category factorization (sharing one strategy across zones of varying sizes), highlighting a trade-off between computational efficiency and granular control.

Significance and Claims
The authors claim that this work bridges the gap between regulatory equity requirements and operational decision-making. By framing rebalancing as a CMDP, the method transforms an equity goal into a planning input with a known price. It enables cities to enforce outcome-based rules (service levels) rather than prescriptive inputs (vehicle counts), aligning with recommendations from bodies like the International Transport Forum. The paper concludes that this approach offers a viable path toward achieving the last-mile access goals of UN Sustainable Development Goal 11.2, providing a mechanism to hold a service floor in underserved areas without compromising the efficiency of the rest of the network. The authors remain modest, noting that the current model assumes independent demand and fixed rebalancing instants, and that future work is needed to address demand correlations, intra-period rebalancing, and online adaptation to drifting demand patterns.

More like this