TL;DR
This paper introduces LSPS-DNN, a novel deep learning model for estimating taxi travel times using only Origin-Destination (OD) data. It addresses the challenge of limited taxi data by employing a "Latent Semantic Pulse Sequence Coding" approach to capture complex spatio-temporal patterns, outperforming traditional methods.
What Problem Does This Paper Address?
Estimating travel time is crucial for both passengers and transportation resource management. Traditional methods often rely on precise path planning and extensive real-time traffic data (road network topology, flow, sensors), which can be impractical or unavailable. While using taxi trip data (OD pairs, timestamps, trajectories) offers a more lightweight alternative, existing methods often struggle with shallow feature engineering, failing to capture complex moving patterns and spatio-temporal dependencies effectively, especially in data-limited scenarios. This paper aims to bridge this gap by developing a model that can accurately estimate travel time using only OD data, by learning deeper semantic representations of trip trajectories.
Methods
The core innovation of this paper is the Latent Semantic Pulse Sequence Coding (LSPS) approach, implemented within a LSPS-DNN architecture. Here's a breakdown:
- Shallow Feature Extraction: The model first extracts basic features from historical trip data, including OD coordinates, timestamps (at various granularities like year, month, day, hour), and derived spatial features.
- Latent Semantic Pulse Propagation Graph (LSPPG) Construction: This is the novel part.
- Coarse-Grained Semantic Network: The spatial coordinates of ODs are clustered using k-means to create "semantic nodes." This reduces sensitivity to minor path variations.
- Pulse-Coupled Neural Network (PCNN): A PCNN is employed to model the propagation of "pulses" between these semantic nodes. The ignition process of PCNN neurons, mimicking autowave propagation, is used to derive a "propagation graph" that represents a sequence of latent paths between ODs. This implicitly captures spatio-temporal features and directional trends.
- Sequential Representation: The ignition order of neurons in the PCNN forms a sequential representation of the propagation graph.
- Recurrent Spatiotemporal Unified Encoding: The sequential patterns (SPs) from the propagation graph are then encoded into a fixed-length, low-dimensional embedding vector using a recurrent coding layer. This process aims to preserve sequence features and facilitate similarity calculations.
- Feature Fusion and DNN Layer: The learned deep propagation features are fused with the shallow features (OD coordinates, time, distance) and fed into a Deep Neural Network (DNN) layer for the final travel time prediction.
Datasets
The proposed LSPS-DNN model was trained and evaluated on two real-world taxi datasets:
- Chengdu Dataset: Taxi order data from November 1 to November 30, 2016, provided by Didi Chuxing.
- New York City (NYC) Dataset: Taxi trip data from January 1 to June 30, 2016, obtained from the NYC Taxi and Limousine Commission, augmented with trajectory data from OSRM.
Key Insights and Ideas
- The Power of Implicit Path Representation: The paper demonstrates that by modeling the "pulse propagation" through a PCNN on a coarse-grained semantic network, one can effectively capture the implicit spatio-temporal semantics of taxi trips, even without explicit route information.
- Beyond Shallow Features: Traditional methods relying on simple OD coordinates and timestamps struggle to capture complex movement patterns. The LSPS approach provides a richer representation that significantly improves travel time estimation.
- PCNN for Spatio-Temporal Dynamics: The application of PCNNs for encoding spatio-temporal propagation features in travel time estimation is a novel contribution, leveraging its iterative ignition process to model dynamic path sequences.
- Coarse-Graining is Key: Using k-means clustering to create semantic nodes for the PCNN is crucial. It makes the model robust to small variations in taxi paths and focuses on broader travel trends, preventing overfitting to noisy data.
- Fusion is Essential: Combining shallow features (like OD location and time) with the learned deep propagation features leads to the best performance, highlighting the complementary nature of different information sources.
Key Results
The LSPS-DNN model demonstrated superior performance compared to several baseline methods (MLR, MLP, Random Forest, SGDR, XGBoost) across both the Chengdu and NYC datasets.
- Improved Accuracy: The paper reports significant improvements in forecasting accuracy. For instance, on the Chengdu dataset, LSPS-DNN achieved an R2 score of 0.73, an improvement over the best baseline (XGBoost) which had an R2 of 0.70. On the NYC dataset, LSPS-DNN achieved an R2 of 0.77, compared to XGBoost's 0.76.
- Reduced Errors: MAE and RMSE were also consistently lower for LSPS-DNN across both datasets. For example, MAE on Chengdu dropped from 0.2390 (XGBoost) to 0.2195.
- Feature Importance: Experiments showed that while temporal and spatial features contribute, the latent semantic propagation features (PF) are crucial for achieving the best results, especially when fused with other features (LSF).
Limitations and Future Work
- Parameter Sensitivity: The performance of LSPS-DNN is influenced by parameters like the coarsening granularity (k) and encoding length. While the paper explores these, finding optimal values might require further tuning.
- Dynamic Network Properties: The current model constructs a static propagation graph. Future work could explore the time-varying properties of these graphs and dynamically update connections to better reflect real-time network changes.
- Generalizability: While tested on two datasets, further validation on more diverse urban environments and traffic conditions would be beneficial.
Summary updated