  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.
