Optimizing Taxi Carpool Policies via Reinforcement Learning and Spatio-Temporal Mining

Ishan Jindal, Zhiwei Tony Qin, Xuewen Chen, Matthew S. Nokleby, Jieping Ye

TL;DR

This paper introduces a reinforcement learning (RL) system to optimize taxi carpooling policies for increased transportation efficiency. It leverages a novel Spatio-Temporal Neural Network (ST-NN) for accurate travel time prediction and a custom carpooling simulator to train the RL agent, demonstrating significant improvements over baseline policies.

What Problem Does This Paper Address?

As urban populations grow, so does the demand for transportation services like taxis. This leads to increased traffic congestion, air pollution, and inefficient resource utilization. Taxi carpooling offers a promising solution by allowing a single taxi to serve multiple passengers heading in similar directions, thereby reducing the number of vehicles on the road and improving overall efficiency. However, determining the optimal carpooling policy – specifically, when to accept a carpool request – is a complex sequential decision-making problem. Existing approaches often rely on fixed rules or lack the ability to dynamically adapt to real-time conditions and predict future travel times accurately. This paper aims to address this by developing an intelligent, data-driven carpooling policy that maximizes transportation efficiency and minimizes congestion.

Methods

The core of this work lies in two main components:

  • Spatio-Temporal Neural Network (ST-NN): To enable realistic carpooling simulations, accurate travel time estimation is crucial. The authors propose ST-NN, a deep neural network that jointly predicts travel time and distance directly from raw GPS coordinates (origin, destination) and the time of day. Unlike traditional methods that rely on feature engineering or map data, ST-NN learns these representations directly. It consists of two sub-modules: a "Dist-DNN Module" for distance estimation (using binned GPS coordinates) and a "Time-DNN Module" that takes the encoded distance features and time-of-day as input for time prediction. This joint learning approach is shown to improve prediction accuracy.
  • Reinforcement Learning (RL) for Carpooling Policy: The carpooling decision problem is framed as a Markov Decision Process (MDP). A single taxi driver is treated as an RL agent. The agent's state includes its current GPS location and the time of day. The actions available are: "Wait" (W), "Take 1" (TK1 - accept a single passenger), and "Take 2" (TK2 - accept a carpool with up to two passengers). The reward function is defined as the "effective distance" covered by the taxi, which is the sum of actual distances traveled to fulfill passenger demands. A higher effective distance signifies greater efficiency. A carpooling simulator, powered by the ST-NN's predictions, generates experiences (state, action, reward, next state) for training the RL agent. The authors employ a Deep Q-Network (DQN) approach, specifically using Double-DQN for improved training stability, to learn an optimal Q-value function that guides the carpooling decisions.

Datasets

  • NYC Taxi Trip Dataset: A large dataset containing 173 million taxi trips from New York City in 2013 was used for both training the ST-NN model and for building the carpooling simulation environment. This dataset provides trip details including origin and destination GPS coordinates, timestamps, and other variables.

Key Insights and Ideas

  • Joint Travel Time and Distance Prediction: Learning travel time and distance simultaneously with ST-NN proves more effective than learning them in isolation, suggesting a strong interdependency between these factors.
  • Effective Distance as a Reward: Defining the reward as "effective distance" directly aligns the RL agent's objective with the paper's goal of maximizing transportation efficiency and minimizing congestion.
  • Data-Driven Carpooling Policy: Moving beyond heuristic or fixed carpooling rules, an RL-based approach can learn nuanced policies that adapt to varying demand densities and time-of-day conditions.
  • Robustness to Outliers: The ST-NN model demonstrates robustness to outliers in the GPS data, a common issue in real-world urban environments.

Key Results

  • ST-NN Performance: ST-NN significantly improves travel time prediction accuracy compared to baseline methods like Linear Regression and a time-only DNN module. For instance, it achieved a Mean Absolute Error (MAE) of 145.9 seconds, outperforming TimeNN (158.29 seconds) and showing a ~78% improvement over simple linear regression. It also showed robustness to outliers, with only a negligible performance drop.
  • RL Policy Performance: The DQN-learned carpooling policy consistently outperformed a fixed "always-carpool" policy and a tabular Q-learning policy across different regions (Uptown and Downtown Manhattan) and days (weekday and weekend). The DQN policy achieved higher mean cumulative rewards, indicating better optimization of effective trip distance.
  • Selective Action Taking: In areas with less frequent taxi calls (e.g., Uptown Manhattan on weekends), the DQN policy was observed to selectively choose "Take 1" or "Wait" actions, demonstrating a strategic approach to maximize long-term value rather than just immediate rewards.

Limitations and Future Work

  • Single-Agent Assumption: The current RL framework assumes a single taxi driver acting independently. The authors acknowledge that extending this to a multi-agent setting, where taxis coordinate or compete, is a crucial next step.
  • Granularity of Actions: The action space is currently at a high level (accept/reject carpool). Future work could involve a more granular action space that includes specific trip assignments.
  • Deterministic Routing: The carpooling simulator uses a deterministic approach for routing passengers within a carpool. Incorporating more sophisticated routing strategies could further enhance the simulation's realism.
  • Fixed Search Window: While the ST-NN helps predict travel times, the carpooling simulation still uses fixed search windows for taxi calls. Dynamically adjusting these windows based on predictions could be beneficial.

Summary updated

Abstract

In this paper, we develop a reinforcement learning (RL) based system to learn an effective policy for carpooling that maximizes transportation efficiency so that fewer cars are required to fulfill the given amount of trip demand. For this purpose, first, we develop a deep neural network model, called ST-NN (Spatio-Temporal Neural Network), to predict taxi trip time from the raw GPS trip data. Secondly, we develop a carpooling simulation environment for RL training, with the output of ST-NN and using the NYC taxi trip dataset. In order to maximize transportation efficiency and minimize traffic congestion, we choose the effective distance covered by the driver on a carpool trip as the reward. Therefore, the more effective distance a driver achieves over a trip (i.e. to satisfy more trip demand) the higher the efficiency and the less will be the traffic congestion. We compared the performance of RL learned policy to a fixed policy (which always accepts carpool) as a baseline and obtained promising results that are interpretable and demonstrate the advantage of our RL approach. We also compare the performance of ST-NN to that of state-of-the-art travel time estimation methods and observe that ST-NN significantly improves the prediction performance and is more robust to outliers.
BibTeX
@inproceedings{jindal2018optimizing,
  author = {Ishan Jindal and Zhiwei Tony Qin and Xuewen Chen and Matthew S. Nokleby and Jieping Ye},
  title = {{Optimizing Taxi Carpool Policies via Reinforcement Learning and Spatio-Temporal Mining}},
  booktitle = {IEEE BigData},
  year = {2018},
  doi = {10.1109/bigdata.2018.8622481},
}
Figure