Introduction
Operating an Electric Autonomous Mobility-on-Demand (E-AMoD) fleet—the next evolution of ride-hailing services like Uber or Waymo—presents a complex multi-objective optimization problem. Fleet operators must simultaneously match vehicles to passengers, rebalance idle cars to high-demand areas, and manage charging schedules to minimize costs and maximize service.
Traditional approaches using Linear Programming (LP) struggle with the "curse of dimensionality" introduced by the charging dimension. In large-scale urban environments, these methods can take over 40 minutes to compute a single decision window, rendering them impractical for real-time operations. Conversely, simple heuristics are fast but lack the foresight to optimize for long-term demand and fluctuating electricity prices. This paper introduces a hybrid framework that combines Graph Reinforcement Learning (Graph-RL) with classical optimization to achieve near-optimal performance with real-time efficiency.
The Tri-Level Control Framework
The core contribution is a tri-level framework that decouples long-term strategic planning from short-term feasibility constraints. This approach leverages the strengths of both Reinforcement Learning (RL) and Operations Research (OR).
- Step 1: Passenger Matching (LP): A fast optimization layer matches available vehicles to current ride requests to maximize immediate revenue.
- Step 2: Desired Distribution (Graph-RL): A Graph Neural Network (GNN) acts as the system's "brain." By observing the city's state—including vehicle locations, charge levels, and predicted demand—the agent predicts an ideal distribution of idle vehicles across a space-charge graph. The agent is trained using the Soft Actor-Critic (SAC) algorithm to maximize long-term profit.
- Step 3: Vehicle Rebalancing (LP): A final optimization step calculates the specific vehicle flows required to reach the target distribution at minimum cost, ensuring all physical constraints, such as charging station capacities, are strictly met.
By utilizing GNNs, the model is both permutation-invariant and scale-invariant, allowing it to generalize across different city structures and sizes.
Experimental Evaluation
The framework was tested using high-fidelity data from San Francisco (SF) and New York City (NYC). The simulation incorporated real-world origin-destination demand, PG&E’s time-of-use electricity rates, and maintenance costs. The vehicles were modeled after the Chevrolet Bolt EV.
Performance and Efficiency
The Graph-RL approach demonstrated a significant leap in computational efficiency. While traditional Model Predictive Control (MPC) benchmarks scaled poorly with the number of nodes, the Graph-RL policy maintained near-instantaneous execution times.
Key results include:
- 100x Speedup: The system makes decisions in under 10 seconds, compared to 40+ minutes for traditional optimization.
- Near-Optimal Profit: The framework captured up to 89% of the profit achieved by an "Oracle" model with perfect future knowledge.
- Superiority over Heuristics: It outperformed standard domain-specific heuristics by up to 3.2x in total profit.
Generalization and Transfer Learning
A standout feature of the Graph-RL approach is its ability to generalize. Because GNNs operate on local graph structures, a policy trained on NYC can be deployed in SF "zero-shot" and still outperform standard heuristics. Furthermore, the authors demonstrated that "curriculum learning" works remarkably well, allowing agents trained on small-scale simulations to scale up to larger service areas with minimal performance loss.
Conclusion
This research provides a viable path for the real-time management of large-scale E-AMoD fleets. By delegating complex "intuition" to Graph-RL and strict constraint satisfaction to Linear Programming, the framework achieves the high performance of optimization with the speed of heuristics. Future work will focus on integrating individual vehicle dispatching and accounting for dynamic traffic congestion and power grid stability.
Summary updated