PaperlayerView exact revision on arXiv

Source-linked AI summary

Predicting origin-destination ride-sourcing demand with a spatio-temporal encoder-decoder residual multi-graph convolutional network

Jintao Ke, Xiaoran Qin, Hai Yang, Zhengfei Zheng, Zheng Zhu, Jieping Ye

arXiv:1910.09103v1eess.SPcs.LG

TL;DR

OD demand forecasting is challenging because spatial-temporal dependencies among OD pairs are complex and insufficiently modeled by existing approaches. The paper proposes ST-ED-RMGC, combining multiple relationship-specific OD graphs with RMGC and LSTM encoders in an encoder-decoder framework. Experiments on Manhattan for-hire-vehicle data report significant improvement over benchmark methods.

  • Problem

    OD-based demand forecasting is more challenging than zone-based prediction because different OD pairs have complex spatial and temporal dependencies.

  • Method

    ST-ED-RMGC constructs multiple OD graphs and uses RMGC and LSTM networks within an encoder-decoder framework to model spatial-temporal demand dependencies.

  • Results

    The proposed model significantly outperforms benchmark algorithms on for-hire-vehicle datasets from Manhattan, New York City.

  • Takeaways & Limitations

    Modeling geographical and semantic correlations among OD pairs is part of the paper’s approach to predicting future OD demand.

  • Takeaways & Limitations

    The model uses selected historical observations rather than all prior OD demand because using the complete history is unnecessary and infeasible under computational-resource limitations.

Abstract

from arXiv · show

With the rapid development of mobile-internet technologies, on-demand ride-sourcing services have become increasingly popular and largely reshaped the way people travel. Demand prediction is one of the most fundamental components in supply-demand management systems of ride-sourcing platforms. With accurate short-term prediction for origin-destination (OD) demand, the platforms make precise and timely decisions on real-time matching, idle vehicle reallocations and ride-sharing vehicle routing, etc. Compared to zone-based demand prediction that has been examined by many previous studies, OD-based demand prediction is more challenging. This is mainly due to the complicated spatial and temporal dependencies among demand of different OD pairs. To overcome this challenge, we propose the Spatio-Temporal Encoder-Decoder Residual Multi-Graph Convolutional network (ST-ED-RMGC), a novel deep learning model for predicting ride-sourcing demand of various OD pairs. Firstly, the model constructs OD graphs, which utilize adjacent matrices to characterize the non-Euclidean pair-wise geographical and semantic correlations among different OD pairs. Secondly, based on the constructed graphs, a residual multi-graph convolutional (RMGC) network is designed to encode the contextual-aware spatial dependencies, and a long-short term memory (LSTM) network is used to encode the temporal dependencies, into a dense vector space. Finally, we reuse the RMGC networks to decode the compressed vector back to OD graphs and predict the future OD demand. Through extensive experiments on the for-hire-vehicles datasets in Manhattan, New York City, we show that our proposed deep learning framework outperforms the state-of-arts by a significant margin.

1. Introduction

Ride-sourcing platforms need accurate real-time OD demand forecasts because OD prediction supports operational decisions but involves complex dependencies that existing methods model poorly. The paper proposes ST-ED-RMGC, combining multiple OD graphs with residual multi-graph convolution, LSTM temporal encoding, and encoder-decoder reconstruction.

  • Motivation: OD demand forecasting supports real-time vehicle reallocations and shared ride-sourcing operations by predicting both origins and destinations.Knowing expected trips from region A to region B can guide advance vehicle allocation to region A.
  • Motivation: OD-based forecasting is less studied than zone-based forecasting because dependencies between OD pairs are difficult to model.Demand can be related across OD pairs through both geographic and semantic relationships.
  • Proposed approach: ST-ED-RMGC constructs multiple OD graphs whose adjacency matrices represent neighborhood, distance, functional similarity, and historical demand correlations.Each OD pair is represented as a graph node, enabling several relationship types to be modeled.
  • Proposed approach: The model uses RMGC networks for spatial dependencies, LSTM for temporal dependencies, and an encoder-decoder structure to learn spatial-temporal features end to end.The encoded representations are combined in a dense space and decoded back toward OD demand prediction.
  • Results: On Manhattan for-hire-vehicle datasets, the proposed model significantly outperforms benchmark algorithms.The reported evaluation covers ride-sourcing demand prediction in Manhattan, New York City.

Demand forecasting

Ride-sourcing demand forecasting research has focused mainly on zone-level demand, while relatively few studies predict complete origin-destination demand. Existing OD approaches use CNNs, grid embeddings, or line GCNs, but their representations have limitations.

  • Prior demand forecasting: Most existing ride-sourcing demand studies predict passenger demand originating from each region or zone rather than complete OD demand.Only a few primary studies are identified as addressing OD passenger demand.
  • Prior demand forecasting: CNN-based OD forecasting can encode origin-destination information in grid tensors, but grid representations constrain spatial modeling.One cited approach partitions the city into squares and uses a 3D matrix for CNN-based prediction.
  • Prior demand forecasting: Other OD approaches use grid embedding with multi-task learning or combine line GCNs with Kalman filtering.The cited methods model spatial mobility patterns or traffic-network OD demand through different architectures.
  • Limitations of prior methods: The reviewed OD methods may treat origins and destinations separately or use adjacency matrices without semantic information.These design choices limit how relationships between OD pairs are represented in the cited approaches.

Graph convolution

Graph convolutional methods address non-Euclidean relationships that conventional CNNs do not represent well. They either use spectral graph transformations or aggregate neighboring-node features directly, with the latter supporting computation over node batches.

  • Motivation: CNNs require matrix or tensor inputs, making them difficult to adapt to arbitrary non-Euclidean graphs.Graph convolution was introduced to capture relationships that do not fit image-like spatial layouts.
  • Graph convolution approaches: Spatial graph methods perform convolution by aggregating features from neighboring nodes in the original graph domain.These methods can operate on batches of nodes rather than the whole graph, reducing computational complexity.
  • Transportation applications: GCNs are used in transportation applications including traffic flow, traffic speed and state, and parking occupancy prediction.The cited applications illustrate the adoption of graph convolution in transportation research.

3. Research problem

The paper formulates OD demand prediction on irregular Manhattan zones by representing each OD pair as a node in a fully connected graph. Inputs use selected historical intervals capturing recent tendency and daily or weekly periodicity.

  • Research problem: Manhattan is divided into irregular zones based on administrative zip codes, and the task predicts requested orders for all OD pairs in each time interval.The segmentation is intended to represent administrative and functional regional properties.
  • OD graph: The tailored OD graph treats each OD pair as a node and uses adjacency matrices to encode connections between OD pairs.Unlike a conventional traffic graph, its vertices represent origin-destination pairs rather than interactions or zones.
  • OD graph: The OD graph is fully connected, although connections may be weak when OD pairs are geographically or semantically distant.Every pair of OD nodes has an edge in the graph.
  • Research problem and features: The demand feature for an OD pair contains observations from recent intervals and corresponding times across previous days and weeks.These observations represent tendency and periodicity-based temporal dependencies.
  • Research problem and features: The learning problem maps historical demand for all OD pairs on an OD graph to demand for those OD pairs in the next time interval.The formulation defines a function from historical graph demand to next-interval graph demand.

4. The Proposed ST-ED-RMGC Model

ST-ED-RMGC combines multiple OD graphs, residual multi-graph convolutions, and a spatial LSTM within an encoder-decoder framework to model spatial and temporal dependencies for OD demand prediction.

  • Overview of model framework: The encoder-decoder framework uses RMGCs to model spatial correlations and a spatial LSTM to learn temporal dependencies across OD pairs.The decoder reuses RMGC networks to transform the compressed representation back into an OD graph for target-demand prediction.
  • OD graph construction: The model constructs neighborhood, functional-similarity, centroid-distance, and mobility-pattern-correlation graphs to represent different spatial relationships.Neighborhood graphs capture adjacent origins or destinations; functional graphs use land-use properties, distance graphs use centroid distances, and mobility graphs use historical demand covariance.
  • OD graph construction: Neighborhood adjacency matrices indicate whether the origins or destinations of two OD pairs are adjacent.Separate matrices represent origin-based and destination-based neighborhood relationships.
  • OD graph construction: Functional-similarity graphs use selected land-use properties to represent similarities between the origin and destination zones of OD pairs.The properties include urban characteristics such as density and road-related features.
  • RMGC network: The RMGC combines multi-graph convolution with residual blocks, while spectral graph convolution propagates features using adjacency matrices, degree normalization, and trainable weights.MGC processes multiple adjacency matrices in batches and maps input features with dimensions F to output features with dimensions O.

5. Experimental Results

Experiments on New York City for-hire-vehicle data evaluate ST-ED-RMGC against traditional, machine-learning, and graph-convolutional baselines. The model captures spatially imbalanced OD patterns and unstable temporal fluctuations, while evaluation accounts for OD-demand sparsity.

  • Data and models: The experiments use New York City for-hire-vehicle records and compare ST-ED-RMGC with traditional machine-learning models and graph convolutional networks.The compared models include HA, XGBoost, MLP, GBDT, RF, LASSO, LSTM, MGC, and RMGC.
  • Evaluation: MAPE is evaluated only for OD pairs with demand above 1 unit because zero-demand pairs make MAPE infinite.Prediction error is assessed with RMSE, MAE, and MAPE.
  • Model comparison: GCNs significantly outperform the traditional machine-learning and deep-learning baselines, and ST-ED-RMGC improves further through its encoder-decoder structure.Residual units provide marginal gains over MGC, whereas the encoder-decoder combines spatial RMGC and temporal LSTM features.
  • Spatial prediction results: OD demand is strongly imbalanced across space and time, with different morning and evening district patterns that the model captures in its predictions.Figure 8 compares ground truth, predictions, and relative prediction error for 20pm and 8am across a 30 by 30 district matrix.
  • Temporal prediction results: Across two high-variance OD pairs, ST-ED-RMGC better captures day-to-day temporal fluctuations than LASSO, which over-reacts or under-reacts to unstable oscillations.The examined two-week trends include days with two peaks, one peak, or a strong peak accompanied by a weak peak.

6. Conclusions and Future Work

The paper addresses OD-based ride-sourcing demand prediction by modeling geographical, neighboring, mobility-pattern, and functional relationships among OD pairs. It reports significant improvements over baselines on Manhattan data and identifies external features and abnormal-demand prediction as future directions.

  • Conclusion: ST-ED-RMGC constructs multiple OD graphs to represent geographical and semantic correlations, encodes spatial and temporal characteristics, and decodes them to predict future OD demand.The graphs capture distances, neighboring relationships, mobility-pattern correlations, and functional similarities.
  • Conclusion: On real-world Manhattan ride-sourcing data, the proposed model significantly outperforms the baselines.
  • Future work: Future work includes adding weather, temperature, and emergency features and extending the model to abnormal passenger demand caused by accidents.
Loading 1910.09103v1…