This research, a collaboration between Wayne State University and DiDi Research, introduces a data-driven framework designed to optimize taxi carpooling. By integrating a novel spatio-temporal neural network for travel time estimation with a reinforcement learning (RL) agent, the authors developed a system that intelligently determines when a taxi should accept a carpool request to maximize long-term transportation efficiency.
Problem Statement
Carpooling is a powerful tool for reducing urban congestion and pollution, but it presents a complex decision-making challenge: When should a taxi driver accept a second passenger?
A "greedy" policy—simply accepting every carpool request—might seem optimal in the short term but can be counterproductive. A poorly timed carpool might lead a driver into a low-demand area or result in a route so inefficient that it increases total traffic. Existing systems often rely on fixed rules or simple heuristics. This paper seeks a "look-ahead" strategy that considers the long-term consequences of a carpool assignment on a driver's total "effective distance" covered throughout a day.
Methodology
The researchers addressed the problem in two main stages: travel time prediction and policy optimization.
Spatio-Temporal Neural Network (ST-NN)
To simulate carpooling effectively, accurate travel time estimation is required. The authors proposed ST-NN, which jointly learns travel time and distance. The model uses raw GPS coordinates (binned into 200m x 200m cells) and time-of-day as inputs. Its architecture consists of two connected Multi-Layer Perceptrons (MLPs): a "Dist-DNN" to predict time-invariant distance and a "Time-DNN" that incorporates temporal data to predict fluctuating travel times. This joint learning ensures the model understands the structural relationship between distance and time.
Reinforcement Learning (RL) Framework
The authors modeled the driver’s day as a Markov Decision Process (MDP), where the agent learns to maximize rewards over an entire episode (one day).
- State: Defined by the taxi’s current location and time.
- Actions: The agent can choose to Wait, Take a single passenger (TK1), or Carpool (TK2).
- Reward: Defined as "Effective distance"—the sum of the distances of individual trips satisfied minus the actual distance the taxi traveled.
- Algorithm: Deep Q-Networks (DQN) and Double DQN were employed to handle the massive, continuous state space of a city, allowing the agent to approximate the value of actions based on future potential rewards.
Datasets and Preprocessing
The study utilizes the 2013 NYC Taxi Trip Dataset, a massive repository containing roughly 173 million trips. The authors discretized the city into a grid and the day into 10-minute bins to manage the data's scale.
Rigorous cleaning was implemented to remove "anomalous" trips, such as those with zero duration but non-zero distance, or records indicating more than seven passengers.
Key Insights and Results
- The "Greedy" Trap: In high-density areas like Downtown Manhattan, always accepting a carpool is nearly optimal due to ubiquitous demand. However, in lower-density areas (Uptown), the RL agent learned to be selective, sometimes rejecting a carpool to stay in a high-value zone.
- Joint Learning for ETA: ST-NN outperformed state-of-the-art methods by 17% in Mean Absolute Error (MAE), proving more robust to noisy urban GPS data.
- Policy Performance: In Uptown Manhattan, the RL-learned policy achieved a mean cumulative reward of 46.08, significantly higher than the 41.54 achieved by the fixed baseline policy.
- Efficiency Alignment: By using "effective distance" as a reward, the model aligns individual driver goals with the societal goal of maximizing the number of people moved per mile of road used.
Conclusion and Future Work
The RL agent’s behavior proved logically sound, following fixed policies during high-demand morning hours but prioritizing long-term positioning in the afternoon. While successful, the current model treats each taxi as an independent agent. Future research will explore Multi-Agent Reinforcement Learning (MARL) to account for fleet-wide coordination and incorporate external factors like real-time weather and special events.
Summary updated