Exploring Computational Complexity Of Ride-Pooling Problems

Usman Akhtar, Rafal KucharskiarXiv 2022 · OpenReview

TL;DR

This paper dives into the computational complexity of ride-pooling, revealing that the problem's difficulty explodes with increasing demand and, more critically, with higher discounts offered to incentivize pooling. The authors demonstrate that while their ExMAS algorithm can handle significant loads, there's a clear "critical point" where computation becomes intractable, offering insights into optimizing ride-pooling systems.

What Problem Does This Paper Address?

Ride-pooling, a promising solution for urban mobility, faces a significant hurdle: computational complexity. As more travelers and vehicles are involved, the number of potential ride-sharing combinations grows exponentially, quickly overwhelming analytical solutions. This "curse of dimensionality" makes finding optimal pooling arrangements computationally infeasible for real-world scenarios. Existing approaches often rely on heuristics or simplify the problem, potentially sacrificing efficiency. This paper aims to systematically explore and quantify this complexity, identifying the tipping points where ride-pooling becomes computationally intractable and understanding how factors like demand and discount influence this.

Methods

The researchers employ the ExMAS (Exact Matching of Attractive Shared Rides) algorithm, an offline approach designed to tackle ride-sharing complexity. ExMAS utilizes a "utility-driven" filtering mechanism to prioritize "attractive" shared rides – those where the benefits (like discounts) outweigh the downsides (like increased travel time or detour). They specifically focus on the discount rate ($\lambda$) as a key parameter, formulating a utility difference ($\Delta U$) to filter for rides where pooling offers a net benefit. The study then systematically traces computational complexity by measuring search space size, computation time, and other performance indicators across various demand levels and discount rates.

Datasets

The study utilizes a synthetic demand dataset for Amsterdam, Netherlands. This dataset is generated to mimic realistic urban travel patterns, with origins dispersed and destinations concentrated in the city center, reflecting a typical morning commute. The researchers vary the number of trip requests per hour (up to 3600) and the discount offered for pooling (up to 40%) to simulate different operational scenarios.

Key Insights and Ideas

  • Discount is King (of Complexity): The most striking finding is that the discount offered for ride-pooling has a far greater impact on computational complexity than the number of trip requests. Higher discounts, while incentivizing pooling, dramatically increase the search space and computation time.
  • The "Critical Point" of Intractability: The research identifies a clear "critical point" where the combination of high demand and significant discounts renders the problem computationally intractable for their ExMAS algorithm. This occurs around a 40% discount and 400 trip requests per 10-minute batch.
  • Non-Linear Growth is the Norm: Both search space size and computation time exhibit strong, non-linear growth with increasing demand and discount. This means that even small increases in these parameters can lead to disproportionately larger computational burdens.
  • Efficiency Plateaus, Complexity Explodes: Interestingly, the efficiency of ride-pooling (measured by pooled rides and utility improvements) tends to plateau beyond a certain point, even as the search space continues to explode. This suggests that simply increasing the scale of the problem doesn't necessarily lead to better pooling outcomes, and there might be room for optimization.
  • Higher Degree Rides are More Complex: The complexity of identifying feasible rides increases significantly with the "degree" of the ride (i.e., the number of passengers sharing). While pairs of travelers are manageable, triples and higher degrees contribute substantially to the combinatorial explosion.

Key Results

  • The ExMAS algorithm successfully reduced the search space compared to theoretical calculations, but still faced computational limits.
  • For a mid-size demand of 500 trip requests, computation time increased to 100 seconds with a 15% discount.
  • At a 40% discount and 400 trip requests, the search space exceeded $10^5$ feasible rides, and ExMAS failed to compute a solution.
  • The number of feasible rides for third-degree (three-passenger) pooling reached up to 150,000 in experiments, significantly more than the 25,000 for pairs.
  • Pooling efficiency stabilized around a 7% benefit for search space sizes ranging from $10^3$ to $10^6$.

Limitations and Future Work

The authors acknowledge that the observed trends, particularly for computational times, showed some discrepancies, possibly due to the asynchronous nature of their multi-threaded server. They suggest that more replications might be needed for statistically sound distributions in future studies, especially for lower discount scenarios exhibiting high variability.

Future work could focus on:

  • Smart Shareability Graph Filtering: Leveraging the topology of the shareability graph to intelligently filter the search space without negatively impacting pooling efficiency.
  • Developing Novel Heuristics: Given the intractable nature of the problem at scale, developing more advanced heuristics or approximation algorithms is crucial.
  • Extending Algorithm Capabilities: Adjusting the ExMAS algorithm to better handle the exploding search space by exploring more sophisticated filtering mechanisms.

Summary updated

Abstract

Ride-pooling is computationally challenging. The number of feasible rides grows with the number of travelers and the degree (capacity of the vehicle to perform a pooled ride) and quickly explodes to the sizes making the problem not solvable analytically. In practice, heuristics are applied to limit the number of searches, e.g., maximal detour and delay, or (like we use in this study) attractive rides (for which detour and delay are at least compensated with the discount). Nevertheless, the challenge to solve the ride-pooling remains strongly sensitive to the problem settings. Here, we explore it in more detail and provide an experimental underpinning to this open research problem. We trace how the size of the search space and computation time needed to solve the ride-pooling problem grows with the increasing demand and greater discounts offered for pooling. We run over 100 practical experiments in Amsterdam with 10-minute batches of trip requests up to 3600 trips per hour and trace how challenging it is to propose the solution to the pooling problem with our ExMAS algorithm. We observed strong, non-linear trends and identified the limits beyond which the problem exploded and our algorithm failed to compute. Notably, we found that the demand level (number of trip requests) is less critical than the discount. The search space grows exponentially and quickly reaches huge levels. However, beyond some level, the greater size of the ride-pooling problem does not translate into greater efficiency of pooling. Which opens the opportunity for further search space reductions.
BibTeX
@misc{akhtar2022exploring,
  author = {Usman Akhtar and Rafal Kucharski},
  title = {{Exploring Computational Complexity Of Ride-Pooling Problems}},
  year = {2022},
  eprint = {2208.02504},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2208.02504},
}

Loading related content...

Figure