Dynamic Ridesharing in Peak Travel Periods

Hui Luo, Zhifeng Bao, Farhana Murtaza Choudhury, J. Shane Culpepper

TL;DR

This paper tackles the challenging problem of dynamic ridesharing during peak hours, where rider demand vastly outstrips driver supply. The authors introduce a novel approach that optimizes for both maximizing the number of served riders and minimizing additional travel distance, while also accounting for realistic system update times. Their proposed methods, including a specialized road network index and efficient pruning rules, significantly outperform existing solutions in terms of both speed and service quality.

What Problem Does This Paper Address?

The paper addresses the critical issue of dynamic ridesharing, particularly during peak travel periods. In these times, the number of rider requests can be orders of magnitude higher than the available drivers, creating a significant imbalance. Existing ridesharing solutions often struggle with scalability in such scenarios, typically focusing on single objectives like minimizing driver travel cost. Furthermore, many prior studies overlook the crucial computational cost of updating driver schedules in real-time, which is essential for a realistic system evaluation. This paper aims to fill these gaps by proposing a system that can efficiently handle high demand, optimize for dual objectives (served rate and additional distance), and incorporate realistic system update costs.

Methods

The authors propose a multi-faceted approach:

  • Road Network Indexing: They introduce a novel index structure built on a density-based partitioning of the road network. This index precomputes lower bounds for shortest path distances between vertices and subgraphs, enabling O(1) estimation of distances. This is crucial for quickly pruning infeasible driver-rider matches.
  • Pruning-Based Rider Insertion: A core contribution is an efficient algorithm for inserting new rider requests into existing driver trip schedules. This algorithm leverages the road network index and a set of "pruning rules" (Lemmas 3-8) to quickly eliminate invalid insertion positions without exhaustive checks. This significantly speeds up the process of accommodating new riders.
  • Dual-Objective Algorithms: Two algorithms are proposed to match drivers and riders:
  • Distance-first Algorithm (DF): This algorithm processes rider requests sequentially, prioritizing the driver that minimizes the additional distance for that specific request.
  • Greedy Algorithm (GR): This algorithm considers rider requests in batches and aims to optimize a utility function that balances served rate and average additional distance, providing a more holistic approach to the dual objectives.
  • Pruned Variants (DF+P and GR+P): The authors also present pruned versions of DF and GR that incorporate their proposed pruning rules, demonstrating significant efficiency gains.

Datasets

The experiments were conducted on a real-world dataset from Shanghai, which includes:

  • Road Network Data: 122,319 vertices and 188,426 edges, with latitude/longitude information and edge distances.
  • Taxi Trip Data: 432,327 taxi requests from May 29, 2009. The departure timestamp was used to simulate request submission times, and pickup/dropoff points were mapped to the nearest road network vertices.

The paper does not introduce a new benchmark dataset but uses a large-scale existing one to validate their methods.

Key Insights and Ideas

  • Peak Hour Dynamics are Crucial: The paper highlights that peak hours present unique challenges (high demand, low supply) that require specialized solutions, as general ridesharing algorithms struggle to scale.
  • Dual Objectives are Necessary: Optimizing solely for driver distance or rider satisfaction is insufficient. A balance between maximizing served riders and minimizing additional distance is key for a successful ridesharing system.
  • Realistic Cost Accounting Matters: Including the time spent updating driver schedules and system indices is vital for accurate performance evaluation, a factor often overlooked in prior work.
  • Efficient Pruning is Key to Scalability: The proposed road network index and pruning rules dramatically reduce the search space for valid matches, enabling efficient handling of high-volume requests.
  • Greedy Approach Balances Objectives: The Greedy algorithm, by considering a utility function that balances served rate and additional distance, shows a better trade-off than purely distance-focused methods, especially when served rate is a priority.

Key Results

  • Efficiency Gains: The pruned algorithms (DF+P and GR+P) are significantly faster than the baseline DSA, with matching times being orders of magnitude lower. For instance, update times for their methods are orders of magnitude faster than DSA.
  • Effectiveness Improvements: GR+P consistently achieved a higher served rate (e.g., ~10% improvement over DSA) while maintaining a comparable or slightly increased additional distance.
  • Scalability: The proposed methods demonstrate good scalability, handling large numbers of drivers and requests efficiently.
  • Robustness: The algorithms are shown to be robust across various parameter settings, including waiting time constraints, vehicle capacity, and travel speeds.
  • Performance Bound: A comparison with Simulated Annealing (SA) showed that their GR+P algorithm achieves near-optimal solutions with significantly lower computational cost.

Limitations and Future Work

  • Limitations:
    • The paper assumes a uniform travel speed for simplicity in some calculations, though experiments are conducted with varying speeds.
  • The "Distance-first" algorithm, while efficient, prioritizes individual requests, potentially leading to suboptimal overall served rates compared to the "Greedy" approach.
  • Future Work:
    • Investigate how "fairness" can be applied to the driver-and-rider matching process.
  • Define a fair price mechanism for riders based on their waiting time tolerance.

Summary updated

Abstract

In this paper, we propose and study a variant of the dynamic ridesharing problem with a specific focus on peak hours: Given a set of drivers and a set of rider requests, we aim to match drivers to each rider request by achieving two objectives: maximizing the served rate and minimizing the total additional distance, subject to a series of spatio-temporal constraints. Our problem can be distinguished from existing ridesharing solutions in three aspects: (1) Previous work did not fully explore the impact of peak travel periods where the number of rider requests is much greater than the number of available drivers. (2) Existing ridesharing solutions usually rely on single objective optimization techniques, such as minimizing the total travel cost (either distance or time). (3) When evaluating the overall system performance, the runtime spent on updating drivers' trip schedules as per newly coming rider requests should be incorporated, while it is unfortunately excluded by most existing solutions. In order to achieve our goal, we propose an underlying index structure on top of a partitioned road network, and compute the lower bounds of the shortest path distance between any two vertices. Using the proposed index together with a set of new pruning rules, we develop an efficient algorithm to dynamically include new riders directly into an existing trip schedule of a driver. In order to respond to new rider requests more effectively, we propose two algorithms that bilaterally match drivers with rider requests. Finally, we perform extensive experiments on a large-scale test collection to validate the effectiveness and efficiency of the proposed methods.
BibTeX
@article{luo2021dynamic,
  author = {Hui Luo and Zhifeng Bao and Farhana Murtaza Choudhury and J. Shane Culpepper},
  title = {{Dynamic Ridesharing in Peak Travel Periods}},
  journal = {IEEE Trans. Knowl. Data Eng.},
  year = {2021},
  url = {https://openreview.net/forum?id=7qPCrvJRhv},
}
Figure