TLDR: This research introduces a simulation-informed reinforcement learning (RL) approach to improve large-scale on-demand ride-pooling systems. By learning from simulated historical data, the system makes non-myopic dispatch decisions for both matching passengers to vehicles and rebalancing idle vehicles. This method significantly increases service rates, reduces passenger wait and in-vehicle times, and can decrease fleet size by over 25% compared to traditional myopic policies, offering substantial operational savings and better user experience.
Ride-pooling, often known as ride-sharing or microtransit, has become a popular transportation service, offering benefits like reduced costs for passengers and operators, decreased traffic congestion, and lower environmental impact. However, a significant challenge in these systems is making decisions that only consider immediate benefits, often overlooking long-term consequences. This ‘myopic’ approach can lead to inefficiencies and poorer service over time.
A recent research paper, titled “Non-myopic Matching and Rebalancing in Large-Scale On-Demand Ride-Pooling Systems Using Simulation-Informed Reinforcement Learning,” addresses this limitation. Authored by Farnoosh Namdarpoura and Joseph Y. J. Chowa from the C2SMARTER University Transportation Center at New York University Tandon School of Engineering, the study proposes an innovative solution to enhance the efficiency and user experience of large-scale ride-pooling systems.
The Challenge of Myopic Decisions
In dynamic ride-pooling, vehicles are assigned to requests, and idle vehicles are repositioned to meet future demand. These are sequential decision problems, meaning a choice made now can significantly impact the system later. Traditional methods often use greedy algorithms that prioritize immediate gains, like assigning the nearest vehicle to a request. While simple, these methods fail to consider how such a decision might affect vehicle availability or demand fulfillment in the future, leading to suboptimal outcomes.
A Non-Myopic Approach with Reinforcement Learning
The researchers introduce a simulation-informed reinforcement learning (RL) approach to overcome myopic decision-making. RL is a powerful artificial intelligence technique where an agent learns to make optimal decisions by interacting with an environment and receiving feedback (rewards). While RL has been widely applied in ride-hailing (one passenger per vehicle), its application in the more complex ride-pooling scenario has been less explored.
This study extends a successful learning and planning framework previously used for ride-hailing by Didi Chuxing, adapting it for ride-pooling. The core idea is to embed a ride-pooling simulator within the learning mechanism. This allows the system to learn from simulated experiences, enabling it to make decisions that consider long-term effects.
How the System Works: Offline Learning and Online Planning
The proposed framework has three main components:
- Offline Simulation-Informed Learning: Historical demand data (like NYC taxi requests) is fed into a ride-pooling simulator. Crucially, the simulator is run with a very large fleet size to ensure no requests are rejected, allowing the system to capture all potential demand-supply patterns without being constrained by vehicle shortages. From these simulated experiences, the system uses a technique called n-step Temporal Difference (TD) learning to learn “spatiotemporal state values.” These values essentially tell the system how “valuable” it is for a vehicle to be in a particular zone at a particular time, based on future demand.
- Online Planning for Matching: In real-time, when a new ride request comes in, the system uses the learned state values to decide which available vehicle should serve it. Instead of just looking at immediate costs (like travel time), it calculates a “marginal expected gain.” This gain considers both the immediate impact of assigning the request and the future value of where the vehicle will end up. Vehicles that will be positioned in more valuable states (i.e., areas with high future demand) are preferred.
- Online Planning for Rebalancing: The system also includes a complementary policy for rebalancing idle vehicles. At regular intervals, it identifies “deficit zones” (where demand is higher than supply) and “surplus zones” (where supply exceeds demand). Idle vehicles from surplus zones are then strategically repositioned to deficit zones, again using the learned state values to guide these decisions and optimize for future demand.
Real-World Evaluation with NYC Taxi Data
The methodology was rigorously tested using real-world NYC yellow taxi request data from February 2024. The simulation used a road network of Manhattan, divided into 69 taxi zones, and defined states based on 5-minute time intervals over a 24-hour period.
Key Findings and Benefits
The results demonstrate significant improvements over traditional myopic policies:
- Increased Service Rate: The non-myopic RL approach (NM-RL) increased the service rate (percentage of accepted requests) by up to 8.4% compared to a myopic policy, especially for smaller fleet sizes.
- Reduced Passenger Times: Passengers experienced significantly shorter in-vehicle times (up to 9.6% decrease) and wait times (up to 20.8% decrease). This indicates that the system effectively positions vehicles closer to where demand arises.
- Fleet Size Reduction: The study found that the proposed non-myopic policy could reduce the required fleet size by over 25% while maintaining the same level of performance as a myopic policy. This translates to substantial cost savings for operators.
- Enhanced Rebalancing: Incorporating the RL-based rebalancing operations further boosted performance. Compared to using matching decisions alone, rebalancing reduced passenger wait time by up to 27.3% and in-vehicle time by 12.5%, while increasing the service rate by 15.1%. This proactive rebalancing, guided by learned demand patterns, proved more effective than reactive methods.
While the rebalancing operations did lead to a slight increase in vehicle minutes traveled per passenger (VMT), the overall improvements in service rate and passenger experience often justify this trade-off, especially given that rebalancing frequency can be adjusted in practice.
Also Read:
- AI Agents Learn to Optimize Urban Traffic Flow
- Balancing Efficiency and Equity: A New Framework for Fair Resource Allocation in Multi-Agent Systems
Conclusion
This research presents a robust and scalable framework for managing large-scale ride-pooling systems. By leveraging simulation-informed reinforcement learning, the system can make intelligent, forward-looking decisions for both matching passengers to vehicles and repositioning idle vehicles. The significant improvements in service rate, passenger wait and in-vehicle times, and the potential for fleet size reduction highlight the transformative potential of this approach for on-demand transportation services. For more details, you can refer to the full research paper here.
