Proactive Rebalancing and Speed-Up Techniques for On-Demand High Capacity Ridesourcing Services

Yang Liu, Samitha SamaranayakeIEEE Trans. ITS 2022 · DOI

TL;DR

This paper tackles the challenge of efficiently managing large fleets of on-demand ridesourcing services by introducing two key innovations: speed-up techniques to drastically reduce computation time for trip assignments and a proactive rebalancing method that intelligently routes idle vehicles to anticipate future demand. These improvements lead to significantly faster simulations, increased service rates, and reduced passenger wait times, making high-capacity ridesharing more practical and efficient.

What Problem Does This Paper Address?

The rise of ridesharing services like UberPool and Lyft Line has brought us closer to sustainable urban mobility, but managing these services at scale, especially with autonomous vehicles, presents significant computational challenges. The core problem is efficiently assigning vehicles to passenger requests and ensuring vehicles are optimally positioned to meet future demand. Existing frameworks, while capable of handling complex scenarios, become computationally prohibitive as fleet sizes grow. Specifically, the process of finding feasible trips and assigning vehicles to them can take an unacceptably long time, hindering real-time operations. Furthermore, simply reacting to current demand leaves idle vehicles inefficiently positioned, leading to longer wait times and lower service rates.

Methods

The paper builds upon an existing framework [1] and introduces two main sets of improvements:

  • Speed-up Techniques:
    • Search Space Pruning: Two techniques are proposed to reduce the number of "pickup-and-delivery-problem" (PDP) instances that need to be solved when determining feasible trips. These methods prune the search space based on feasibility constraints, effectively eliminating unlikely or impossible vehicle-trip pairings earlier in the process.
  • I/O Reduction for Parallelization: To address bottlenecks when parallelizing the assignment process, a method is introduced to efficiently partition requests. This aims to minimize redundant data transfer by grouping requests that are likely to share similar candidate vehicles, thereby reducing input/output overhead.
  • Proactive Probabilistic Rebalancing:
    • New Rebalancing Formulation: A revised formulation ensures a one-to-one matching between idle vehicles and unsatisfied requests, preventing situations where multiple vehicles are assigned to a single request and improving spatial coverage.
  • Probabilistic Approach: Instead of just reacting to current unserved demand, this method uses historical data to build probability distributions of future demand within spatial clusters. Idle vehicles are then proactively routed to these high-probability areas, anticipating future requests.

Datasets

The paper uses taxi trip data from Manhattan, NYC, specifically for a day in May 2013 [11]. The road network used is the entire road network of Manhattan, comprising 4092 nodes and 9453 edges. This dataset is used to simulate various scenarios and evaluate the performance of the proposed techniques.

Key Insights and Ideas

  • Computational Bottlenecks are Real: The paper highlights that even sophisticated frameworks struggle with the computational demands of large-scale ridesharing, particularly in the trip feasibility and assignment stages.
  • Proactive is Better than Reactive: Simply reacting to current demand for rebalancing is less effective than anticipating future demand. By understanding where demand is likely to occur, vehicles can be positioned more strategically.
  • Clustering for Efficiency: Using spatial clustering to predict demand is a practical approach for large, sparsely populated urban networks, simplifying the prediction problem.
  • I/O is a Hidden Cost: In parallel computing, data transfer (I/O) can become a significant bottleneck, and clever request partitioning can mitigate this.
  • Small Improvements Add Up: While individual speed-up techniques might seem incremental, their combined effect, along with proactive rebalancing, leads to substantial performance gains.

Key Results

The proposed techniques demonstrate significant improvements:

  • Speed-up: The speed-up techniques reduce computation time by up to 97.67% in experiments.
  • Service Rate: The proactive rebalancing method increases the service rate by an average of 4.8%.
  • Reduced Delays: Passenger waiting time is decreased by an average of 5.0%, and total delay is reduced by an average of 10.7%.
  • Specific Scenario Gains: In one notable case (3000 vehicles, capacity 4, Ω=120, ∆=300), waiting time and total delay were reduced by 24.28% and 68.51%, respectively.
  • Robustness: The speed-up techniques maintain performance even as parameters like maximum waiting time and delay increase, unlike the original framework.

Limitations and Future Work

  • Dynamic Travel Times: The paper notes that its current speed-up techniques are based on the assumption of non-decreasing travel times. Future work should explore speed-up techniques that can be employed in networks with dynamic travel times.
  • Hyperparameter Sensitivity: The authors suggest analyzing the sensitivity of hyperparameters used in the rebalancing methods.
  • Real-world Deployment: While the paper presents simulation results, real-world deployment would involve further validation and adaptation to actual operational constraints.

Summary updated

BibTeX
@article{liu2022proactive,
  author = {Yang Liu and Samitha Samaranayake},
  title = {{Proactive Rebalancing and Speed-Up Techniques for On-Demand High Capacity Ridesourcing Services}},
  journal = {IEEE Trans. ITS},
  year = {2022},
  doi = {10.1109/tits.2020.3016128},
}
Figure