Spatial-Temporal Demand Forecasting and Competitive Supply via Graph Convolutional Networks

Bolong Zheng, Qi Hu, Lingfeng Ming, Jilin Hu, Lu Chen, Kai Zheng, Christian S. JensenarXiv 2020 · arXiv

Abstract

The SOUP framework addresses the dual challenge of ride-hailing demand prediction and idle driver routing. By integrating a novel graph-based deep learning model (ST-GCSL) for forecasting with a demand-aware routing algorithm (DROP), the system reduces driver idle time and passenger wait times while mitigating the "herding effect." Evaluation on large-scale datasets from New York City and Haikou demonstrates that SOUP outperforms state-of-the-art baselines in both forecasting accuracy and operational efficiency.

Introduction

In urban ride-hailing platforms, balancing driver supply with passenger demand is a critical operational challenge. When drivers become idle after a drop-off, they often rely on intuition or simple platform-provided "hot zone" indicators to find their next fare. This decentralized decision-making leads to two primary inefficiencies: inaccurate forecasting that ignores the complex road network structure and the "herding effect," where an oversupply of drivers converges on high-demand areas, leaving other regions underserved. To address these issues, we propose SOUP (Spatial-Temporal demand forecasting and competitive sUPply), a framework that combines advanced graph-based forecasting with competitive routing strategies.

The SOUP Framework

The SOUP framework operates in two distinct phases: an offline forecasting phase and an online routing phase.

The SOUP framework architecture, illustrating the offline forecasting phase (ST-GCSL) and the online routing phase (DROP).
  1. ST-GCSL (Spatial-Temporal Graph Convolutional Sequential Learning): This module partitions the city into hexagonal regions using the Uber H3 library. It captures complex spatial-temporal dependencies through a "sandwich" architecture of temporal and graph convolutions. Notably, it utilizes a Multiple Spatial-Temporal Convolutional Module (MSTCM) to model short-term demand bursts alongside standard modules for long-term trends.
  2. DROP (Demand-aware Route Planning): This algorithm guides idle drivers based on ST-GCSL's predictions. It employs a state-dependent strategy that prioritizes high-demand areas during peak hours and focuses on spreading drivers to avoid competition during non-peak hours.

Key Insights: Beyond Physical Proximity

A core innovation in SOUP is the definition of "neighbors" within the graph. Traditional models often rely solely on geographical proximity. SOUP introduces "Semantic Neighbors"—regions that may be physically distant but exhibit similar demand patterns (e.g., two separate business districts).

Spatial partitioning and neighbor definitions: (a) Hexagonal regions in Manhattan, (b) Geographical neighbors, and (c) Semantic neighbors with similar demand patterns.

By linking these semantic neighbors, the model learns more robust features. Furthermore, the DROP algorithm considers the "real-time ratio" of idle agents, ensuring that routing decisions account for potential competition, thereby preventing the herding effect.

Evaluation and Results

The framework was evaluated using two massive real-world datasets: NYC TLC Yellow Taxi (69 million orders) and Haikou Didi Chuxing (12 million orders). ST-GCSL achieved significant improvements in forecasting accuracy, reaching a MAPE of 16.46% in NYC compared to the historical average of 43.71%. In operational simulations, the DROP algorithm reduced average driver idle time by 10 seconds and passenger wait times by 26.8 seconds in NYC, while also reducing the rate of expired requests by 0.73%.

Conclusion

SOUP demonstrates the power of combining graph-based spatial-temporal modeling with competitive routing logic. While the current model assumes independent agents, future work will explore multi-agent reinforcement learning to further optimize fleet coordination. Additionally, addressing data sparsity in smaller cities and refining node-level destination selection remain key areas for improvement.

Summary updated

Abstract

We consider a setting with an evolving set of requests for transportation from an origin to a destination before a deadline and a set of agents capable of servicing the requests. In this setting, an assignment authority is to assign agents to requests such that the average idle time of the agents is minimized. An example is the scheduling of taxis (agents) to meet incoming requests for trips while ensuring that the taxis are empty as little as possible. In this paper, we study the problem of spatial-temporal demand forecasting and competitive supply (SOUP). We address the problem in two steps. First, we build a granular model that provides spatial-temporal predictions of requests. Specifically, we propose a Spatial-Temporal Graph Convolutional Sequential Learning (ST-GCSL) algorithm that predicts the service requests across locations and time slots. Second, we provide means of routing agents to request origins while avoiding competition among the agents. In particular, we develop a demand-aware route planning (DROP) algorithm that considers both the spatial-temporal predictions and the supplydemand state. We report on extensive experiments with realworld and synthetic data that offer insight into the performance of the solution and show that it is capable of outperforming the state-of-the-art proposals.
BibTeX
@misc{zheng2020spatial,
  author = {Bolong Zheng and Qi Hu and Lingfeng Ming and Jilin Hu and Lu Chen and Kai Zheng and Christian S. Jensen},
  title = {{Spatial-Temporal Demand Forecasting and Competitive Supply via Graph Convolutional Networks}},
  year = {2020},
  eprint = {2009.12157},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2009.12157},
}
Figure