Exploring Computational Complexity of Ridepooling Problems

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 the authors 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, the authors explore it in more detail and provide an experimental underpinning to this open research problem. The authors 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. The authors 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 their ExMAS algorithm. The authors observed strong, non-linear trends and identified the limits beyond which the problem exploded and their algorithm failed to compute. Notably, the authors 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.

• Record URL:
  https://annualmeeting.mytrb.org/OnlineProgram/Details/19065
• Supplemental Notes:
  • This paper was sponsored by TRB committee AEP35 Standing Committee of Effects of Information and Communication Technologies (ICT) on Travel Choices.
• Corporate Authors:

  Transportation Research Board

  ,    
• Authors:
  • Akhtar, Usman
  • Kucharski, Rafal
• Conference:
  • Transportation Research Board 102nd Annual Meeting
  • Location: Washington DC, United States
  • Date: 2023-1-8 to 2023-1-12
• Date: 2023

Language

• English

Media Info

• Media Type: Digital/other

Subject/Index Terms

• TRT Terms: Algorithms; Complex variables; Ridesharing; Shared mobility
• Identifier Terms: Mobility-as-a-Service (MaaS)
• Geographic Terms: Amsterdam (Netherlands)
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting;

Filing Info

• Accession Number: 01874535
• Record Type: Publication
• Report/Paper Numbers: TRBAM-23-03199
• Files: TRIS, TRB, ATRI
• Created Date: Feb 24 2023 9:05AM