🤖 machine learning

Scalable Ride-Sourcing Vehicle Rebalancing with Service Accessibility Guarantee: A Constrained Mean-Field Reinforcement Learning Approach

This paper proposes a scalable constrained mean-field reinforcement learning approach for ride-sourcing vehicle rebalancing that effectively addresses the curse of dimensionality in large fleets while ensuring equitable service accessibility across geographic regions.

Original authors: Matej Jusup, Kenan Zhang, Zhiyuan Hu, Barna Pásztor, Andreas Krause, Francesco Corman

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Matej Jusup, Kenan Zhang, Zhiyuan Hu, Barna Pásztor, Andreas Krause, Francesco Corman

Original paper licensed under CC BY 4.0 (http://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 filled with thousands of ride-sharing cars (like Uber or Lyft) and a constant stream of people trying to get a ride. The biggest headache for the company running these cars isn't just finding a passenger; it's figuring out where the empty cars should be waiting before anyone even asks for a ride.

If all the cars are stuck in the downtown area while people in the suburbs are waiting, the system fails. If they are all scattered randomly, they waste gas driving around looking for work. This is the problem of Vehicle Rebalancing.

This paper proposes a new, smarter way to manage these fleets using a concept called Mean-Field Reinforcement Learning. Here is how it works, broken down into simple analogies:

1. The Problem: The "Too Many Cooks" Dilemma

Traditionally, trying to control 18,000 cars individually is like trying to conduct an orchestra where every musician is playing a different instrument and you have to tell each one exactly what note to play next. As the number of cars grows, the computer gets overwhelmed (this is called the "curse of dimensionality"). It takes too long to calculate, and by the time it figures it out, the traffic has changed.

2. The Solution: The "Flock of Birds" Approach

Instead of tracking every single car, the authors treat the entire fleet like a flock of birds or a cloud of gas.

The Analogy: Imagine you don't need to tell every bird where to fly. You just need to know the shape of the flock and tell the flock, "Move slightly to the left." The individual birds naturally adjust to fit that shape.
The Tech: This is called Mean-Field Control. The computer doesn't look at Car #4,502. It looks at the "density" of cars in different parts of the city. It asks, "Is there a gap in the cloud of cars in the north? Let's nudge the whole cloud north." This makes the math incredibly fast and scalable, allowing it to handle tens of thousands of cars instantly.

3. The New Twist: The "Fairness Rule"

Most previous systems only cared about efficiency: "Get the most rides possible, make the most money." This usually means dumping all the cars in the busiest, richest neighborhoods, leaving poorer or quieter areas with no service.

The authors added a Service Accessibility Guarantee.

The Analogy: Think of it like a pizza delivery service. A greedy strategy would only send drivers to the busy downtown where orders are guaranteed. But the city says, "You must also make sure there is at least one driver available in the quiet suburbs, even if they don't get many orders."
The Tech: They added a mathematical "rule" (a constraint) to the AI. The AI is told: "You can maximize profits, BUT you must keep the cars spread out enough so that no neighborhood is left completely empty." They use a concept called "entropy" (a measure of spread) to ensure the cars aren't just clumped together.

4. How They Taught the AI

They used two methods to teach the system:

Method A (The Map Reader - MFC): They gave the AI a perfect, pre-calculated map of how cars and riders usually match up. The AI solved the puzzle using this map. This is very fast but relies on the map being perfect.
Method B (The Learner - MFRL): The AI played the game over and over again in a simulation (like a video game), learning from its mistakes. It learned how riders actually behave, not just how a map says they should. This is slightly slower to train but adapts better to real-world chaos.

5. The Results: Fast, Fair, and Strong

When they tested this on real data from Shenzhen (a massive Chinese city with 18,000 simulated cars):

Speed: The new methods could decide where to send all 18,000 cars in less than a second. The old methods took over 10 minutes. In the real world, waiting 10 minutes to move cars is useless; you need to move them now.
Fairness vs. Profit: They found a "sweet spot." By enforcing the fairness rule, they didn't lose much money or efficiency. They could ensure cars were available in quiet neighborhoods without ruining the service in busy ones.
Robustness: When they simulated a sudden, unexpected event (like a concert ending and thousands of people needing rides at once in a weird location), the old systems failed miserably. The new systems, because they kept cars spread out evenly, were ready to handle the surprise surge.

Summary

The paper introduces a way to manage huge fleets of ride-sharing cars that is fast enough to work in real-time and fair enough to serve everyone, not just the rich areas. It does this by stopping the computer from micromanaging every single car and instead managing the "shape" of the whole fleet, while forcing the system to keep a safety net of cars in every neighborhood.

Technical Summary: Scalable Ride-Sourcing Vehicle Rebalancing with Service Accessibility Guarantee

1. Problem Definition

The paper addresses the vehicle rebalancing problem in large-scale ride-sourcing systems (e.g., Uber, Didi Chuxing). The core challenge is the spatiotemporal mismatch between vehicle supply and passenger demand. While existing methods focus on optimizing system-wide efficiency (e.g., maximizing revenue or minimizing waiting times), they often neglect service accessibility, leading to inequitable service distribution where low-demand areas are underserved.

The problem is characterized by three main difficulties:

Scalability: Traditional centralized Reinforcement Learning (RL) suffers from the "curse of dimensionality" as the number of vehicles increases. Multi-agent RL (MARL) reduces dimensionality but introduces non-stationarity and coordination complexities.
Uncertainty: The system involves stochastic demand and complex vehicle-rider matching mechanisms that are difficult to model explicitly.
Equity Constraints: Ensuring a minimum level of service accessibility across geographic regions adds a hard constraint to the optimization problem, which is notoriously difficult to handle within standard RL frameworks.

2. Methodology

The authors propose a Constrained Mean-Field Reinforcement Learning (MFRL) approach, complemented by a Mean-Field Control (MFC) model. This framework treats the fleet as a continuous distribution of agents rather than discrete individuals.

2.1 Mean-Field Formulation

The problem is formulated as a Constrained Mean-Field Markov Decision Process (C-MF-MDP).

State Space: Continuous 2D coordinates of a representative vehicle.
Mean-Field Distribution ( $\mu_t$ ): Represents the limiting distribution of the fleet as the fleet size $L \to \infty$ .
Actions: A continuous repositioning probability ( $p_t$ ) and a movement vector ( $u_t$ ).
Transitions: The state transition is decomposed into three outcomes: repositioning, matching (serving a rider), or cruising. The matching probability is determined by the interaction between the available vehicle distribution and the demand distribution.

2.2 Two Approaches to Dynamics

The paper develops two distinct methods to handle the unknown transition dynamics (specifically the matching process):

Mean-Field Control (MFC): Assumes a closed-form approximation of the matching process using Optimal Transport (OT). The matching is modeled as a minimum cost flow problem between supply and demand distributions. This provides a model-based solution with high sample efficiency.
Mean-Field Reinforcement Learning (MFRL): Learns the matching process directly from data via episodic interactions. A binary classifier is trained to predict matching probabilities based on supply-demand states, which is then used to approximate the state transition function for policy optimization.

2.3 Handling Accessibility Constraints

To enforce service accessibility, the authors introduce a constraint based on the $\epsilon$ -smoothed weighted differential entropy of the available vehicle distribution.

Constraint: $h_w(\mu_t, \pi_t) \ge C$ , where $C$ is a lower bound on entropy.
Mechanism: High entropy corresponds to a uniform distribution of vehicles, ensuring coverage across the service region (excluding non-operational areas like rivers).
Optimization: The constrained problem is transformed into an unconstrained one using the log-barrier method, adding a penalty term $\lambda \log(h_w - C)$ to the reward function. This ensures the policy remains within the feasible region during training.

3. Key Contributions

The paper claims the following contributions:

First Integration of Accessibility in RL: To the authors' knowledge, this is the first study to integrate service accessibility constraints into RL-based vehicle rebalancing under stochastic transitions and non-stationary demand.
Continuous-Space Scalability: Unlike prior zone-level discrete approaches, the proposed MFC and MFRL models operate in a continuous space and scale to tens of thousands of vehicles without retraining when fleet size changes.
Efficiency-Equity Pareto Front: The approach successfully generates policies that explore the trade-off between efficiency (utilization, fulfillment) and equity (accessibility), outperforming benchmarks.
Robustness: The models demonstrate robustness to demand variations, including Gaussian noise, temporal permutations, and sudden demand shocks.

4. Experimental Results

The methods were evaluated using real-world taxi trajectory data from Shenzhen, China (18,000 vehicles, 6-hour peak period).

4.1 Computational Efficiency

Training: MFC training took ~40 minutes; MFRL training took ~26 minutes.
Inference: Both MFC and MFRL generated rebalancing policies for 18,000 vehicles in <0.001 minutes (sub-second) on a GPU.
Comparison: This is significantly faster than Linear Programming (LP) benchmarks, which required 12–19 minutes for inference on a CPU.

4.2 Performance Metrics

Accessibility vs. Efficiency: As the accessibility constraint ( $p$ ) became stricter, the fraction of accessible zones increased, while metrics like utilization and service rate slightly decreased. However, the drop was marginal (e.g., <5% utilization loss for a significant accessibility gain), indicating that high equity can be achieved without sacrificing major efficiency.
Benchmark Comparison: Both MFC and MFRL outperformed "No Rebalancing," "Static LP," and "Dynamic LP" policies across service fulfillment, utilization, and pickup distance. MFRL generally achieved slightly better performance than MFC (up to 5% margin) but at a higher computational cost during training.
Robustness to Shocks: Under hypothetical demand shocks (e.g., a sudden surge of 5,200 requests in a low-demand zone), the proposed policies maintained service rates between 70% and 85%, whereas benchmarks (LP and No Rebalancing) failed to serve more than 40% of requests. The accessibility constraint proved crucial for maintaining service in these unpredictable scenarios.

5. Significance and Claims

The paper positions its work as a significant step toward scalable and equitable urban mobility management.

Scalability: By utilizing mean-field approximation, the approach eliminates the need to retrain models when fleet sizes change, making it viable for metropolitan-scale deployments.
Equity: It addresses the "fairness" critique of private ride-sourcing by mathematically guaranteeing a minimum level of service accessibility, moving beyond purely profit-driven optimization.
Practicality: The sub-second inference time suggests the approach is ready for real-time deployment, capable of reacting to market changes faster than traditional optimization methods.

The authors modestly acknowledge limitations, noting that the current model assumes full driver compliance (ignoring human behavior) and uses time discretization. They suggest future work should address multi-platform competition, finer-grained local constraints, and the integration of autonomous vehicle fleets.