TL;DR
This paper introduces OD-TGAT, a novel graph-based deep learning model that significantly improves city-wide taxi demand prediction by considering both spatial dependencies between non-adjacent regions and temporal patterns. By modeling the city as a graph where nodes represent regions and edges represent origin-destination relationships, OD-TGAT achieves state-of-the-art performance, outperforming existing methods by 9.3% in RMSE.
What Problem Does This Paper Address?
Accurate prediction of taxi demand is crucial for the success of ride-hailing services, enabling better allocation of resources, reduced passenger wait times, and increased taxi utilization. However, predicting demand is challenging due to complex spatial and temporal dependencies. Existing approaches often overlook the influence of non-adjacent regions (e.g., two distant but related locations like train stations) and treat spatial relationships as fixed, limiting their ability to capture diverse patterns. This paper aims to address these limitations by proposing a model that can learn these complex, non-local spatial and temporal relationships across an entire city.
Methods
The core of this paper is the Origin–Destination-based Temporal Graph Attention Network (OD-TGAT). This framework comprises four main layers:
- Transforming Layer: This layer converts the city into a graph where each grid cell is a node. Edges are established based on Origin-Destination (OD) taxi trip data, meaning an edge exists between two nodes if a taxi trip occurred from one to the other. This captures non-adjacent spatial relationships. Rich features are also extracted from historical data and contextual information.
- Spatial Layer (OD-GAT): This layer utilizes a Graph Attention Network (GAT) to learn spatial dependencies. Unlike traditional methods that assume fixed neighbor influence, GAT dynamically assigns attention weights to edges, allowing it to learn the varying importance of different neighboring regions (even non-adjacent ones) for predicting demand at a central node.
- Temporal Layer: This layer employs Gated Recurrent Units (GRUs) to capture temporal correlations in the taxi demand time series. GRUs are chosen for their efficiency and ability to handle sequential data.
- Output Layer: A fully-connected layer processes the outputs from the temporal layer to generate the final city-wide taxi demand prediction.
The novelty lies in the combination of OD-based graph construction, graph attention for flexible spatial feature learning, and GRUs for temporal modeling, all integrated into a unified framework.
Datasets
The study uses the New York City (NYC) yellow taxi data from January to March 2016, comprising over 34 million records. This dataset is publicly available from the NYC Taxi and Limousine Commission. The data was partitioned into training (80%) and testing (20%) sets. For experimental efficiency, the analysis focused on the Manhattan Borough.
Key Insights and Ideas
- OD Relations as Edges: Defining graph edges based on actual Origin-Destination taxi trips is a powerful way to capture meaningful, non-local spatial relationships that traditional grid-based or adjacency-based methods miss.
- Attention for Dynamic Spatial Influence: The use of Graph Attention Networks is crucial. It allows the model to learn that the influence of a neighboring region on demand prediction is not static but depends on the specific context and the relationship between regions.
- Weekend vs. Weekday Demand: Taxi demand prediction is significantly harder on weekends than weekdays, likely due to more varied travel patterns and less predictable demand.
- Optimal Grid Size: There's a sweet spot for grid size. Too small, and you have too many isolated nodes; too large, and the graph becomes too coarse, losing granular information. The study found 300m to be optimal.
Key Results
The proposed OD-TGAT model achieved state-of-the-art performance, outperforming several strong baselines, including HA, ARIMA, LR, MLP, Ridge, RF, XGBoost, and ST-ResNet. Specifically, OD-TGAT improved upon the best baseline by 9.3% in terms of Root Mean Squared Error (RMSE). It also showed improvements of 5.5% in Mean Absolute Error (MAE). The model demonstrated robust performance across different times of day and days of the week, although weekend predictions were less accurate.
Limitations and Future Work
The authors acknowledge that predicting taxi demand on weekends is more challenging. They also suggest future work could involve:
- Exploring more effective ways to discover correlations between temporal and spatial data.
- Leveraging additional external features to further enrich the input data.
- Further research into how to improve prediction quality for higher correlation scenarios.
Summary updated