Space-Time Graph Modeling of Ride Requests Based on Real-World Data

Abhinav Jauhri, Brian Foo, Jérôme Berclaz, Chih Chi Hu, Radek Grzeszczuk, Vasu Parameswaran, John Paul ShenWorkshops @ AAAI 2017

TL;DR

This paper introduces a novel space-time graph model to represent ride-sharing requests, revealing that these graphs exhibit a "densification power law" similar to social networks. This property allows for the generation of synthetic ride request data and directly correlates with a city's "poolability" – the potential to combine rides for efficiency.

What Problem Does This Paper Address?

The explosive growth of ride-sharing services has transformed urban mobility, but understanding and modeling the complex patterns of ride requests remains a challenge. Previous studies often relied on limited data or synthetic models that didn't fully capture the dynamic interplay of location and time. This paper aims to bridge this gap by analyzing extensive real-world ride request data to develop a model that accurately reflects spatial and temporal variations, and to explore the implications for ride pooling. The core problem is to move beyond simple statistical analysis to a more robust, graph-based representation that can uncover underlying structural properties and inform practical applications like ride pooling.

Methods

The authors introduce a Space-Time Graph Model for ride requests. This model discretizes a city into a grid of cells (100m x 100m) and represents ride requests within a specific time interval (5-minute intervals used) as a directed graph. Each cell containing a ride's origin or destination becomes a node, and a ride request forms a directed edge.

Key methodological contributions include:

  • Ride Request Graph (RRG) Generation: A process to convert raw ride request data into these directed graphs, capturing both spatial and temporal aspects.
  • Densification Power Law (DPL) Discovery: The paper demonstrates that RRGs exhibit a DPL, a property where the number of edges grows superlinearly with the number of nodes over time, mirroring social and collaboration networks. This is analyzed using log-log plots of edge count vs. node count.
  • Synthetic RRG Generation: Leveraging the DPL property, they propose algorithms (SPATIALPROPGEN and DENSPROPGEN) to generate synthetic RRGs that mimic the densification characteristics of real-world data. This involves using Points of Interest (PoI) data from OpenStreetMap to guide spatial distribution and a probabilistic approach for edge creation that incorporates a "rich-get-richer" dynamic.
  • Ride Poolability Metric: A new concept is introduced to quantify the potential for ride pooling. It defines poolable rides based on proximity constraints in time (Δt minutes) and space (Δs meters for origin, Δd meters for destination).

Datasets

The primary dataset used is extensive, real-world ride request data from Uber, spanning 40 cities over several weeks in Spring 2016. For the synthetic model's spatial component, they utilize publicly available geospatial information from OpenStreetMap (OSM) on node density (Points of Interest - PoIs).

Key Insights and Ideas

  • Ride Requests as Evolving Graphs: The fundamental insight is that ride requests, when modeled spatially and temporally, form evolving graphs that share structural properties with well-studied human-generated networks like social networks.
  • The "Densification Power Law" in Urban Mobility: Discovering the DPL in ride request graphs suggests that urban transportation networks exhibit a natural tendency towards increased connectivity and clustering over time, similar to how social ties strengthen.
  • Characterizing Cities by Densification: The densification factor (α) derived from the DPL provides a concise way to characterize the unique ride request patterns of different cities.
  • Predictive Power of DPL for Poolability: A crucial finding is the direct correlation between a city's densification factor (α) and its ride poolability. Cities with higher α values tend to have higher poolability, suggesting that the inherent clustering in ride requests directly translates to opportunities for ride sharing.
  • Synthetic Data Mimics Reality: The ability to generate synthetic RRGs that accurately capture both spatial distribution and temporal densification suggests that these graph properties are fundamental and can be replicated without direct access to real-time data.

Key Results

  • DPL Confirmed: RRGs from four analyzed cities (Hyderabad, Paris, New York, San Francisco) consistently exhibited the densification power law, with densification factors (α) ranging from 1.031 to 1.104.
  • Synthetic Model Accuracy: Synthesized RRGs showed densification factors very similar to those from real data. Spatial distribution plots also showed good qualitative agreement between real and synthetic node distributions.
  • Poolability Correlation: A direct correlation was observed between the densification factor (α) and ride poolability. Cities with higher α values consistently showed higher poolability.
  • Poolability Metrics: Mean poolability varied across cities, with San Francisco showing the highest mean (5.48) and Hyderabad the lowest (2.23) for the tested parameters (Δt=5min, Δs=100m, Δd=1000m).
  • Synthetic Poolability Match: The synthetic model's poolability predictions closely matched real data, capturing temporal variations and daily patterns, though with some minor over/under-prediction likely due to static PoI density assumptions.

Limitations and Future Work

Limitations:

  • Static PoI Density: The synthetic model's spatial generation relies on static PoI density from OSM. This doesn't dynamically reflect how PoI density might change or influence ride requests at different times of the day or week.
  • Simplified Poolability Constraints: The poolability metric uses fixed temporal and spatial constraints (Δt, Δs, Δd). The paper questions if relaxing these could improve poolability.
  • Limited Scope of Analysis: While data from 40 cities was used for analysis, detailed results and figures are presented for only four cities.

Future Work:

  • Relaxing Poolability Constraints: Investigating if loosening temporal and spatial constraints can significantly boost ride poolability.
  • Intelligent Ride Pooling Algorithms: Leveraging temporal and spatial variations in ride poolability to create more sophisticated ride pooling algorithms.
  • Vehicle Reduction: Exploring the potential for aggressive ride pooling to significantly reduce the number of vehicles needed on the road.
  • Rigorously Characterizing DPL-Poolability Relationship: Further formalizing the relationship between ride poolability and the densification factor.
  • Traffic Congestion Prediction: Utilizing historical ride request data for real-time traffic congestion prediction and alleviation.
  • Graph Generator Comparison: Comparing their RRG generation method with existing graph generators for spatio-temporal data.

Summary updated

BibTeX
@inproceedings{jauhri2017space,
  author = {Abhinav Jauhri and Brian Foo and Jérôme Berclaz and Chih Chi Hu and Radek Grzeszczuk and Vasu Parameswaran and John Paul Shen},
  title = {{Space-Time Graph Modeling of Ride Requests Based on Real-World Data}},
  booktitle = {Workshops @ AAAI},
  year = {2017},
}
Figure