Accelerating High-Capacity Ridepooling in Robo-Taxi Systems
Xinling Li, Daniele Gammelli, Alex Wallar, Jinhua Zhao, Gioele Zardini
AI summary
Problem
State-of-the-art high-capacity ridepooling algorithms struggle to meet strict real-time constraints due to combinatorial complexity, limiting their scalability in dense urban settings.
Approach
The authors identify computational bottlenecks in the baseline shareability graph framework and introduce a data-driven feasibility predictor to filter low-potential trips, alongside a graph-partitioning scheme to parallelize trip generation.
Key results
- Formal reformulation and bottleneck identification of the baseline algorithm
- Data-driven feasibility predictor filtering low-potential trips
- Graph-partitioning scheme enabling parallelizable trip generation
- Up to 27% reduction in optimality gap and 5% cut in empty travel time on Manhattan data
Why it matters
Advances the real-time scalability of high-capacity robo-taxi fleets, offering actionable algorithmic guidance for urban mobility planners and autonomous vehicle operators.
Abstract
Rapid urbanization has increased demand for cus- tomized urban mobility, making on-demand services and robo- taxis central to future transportation. The efficiency of these sys- tems hinges on real-time fleet coordination algorithms. This work accelerates the state-of-the-art high-capacity ridepooling frame- work by identifying its computational bottlenecks and introducing two complementary strategies: (i) a data-driven feasibility predic- tor that filters low-potential trips, and (ii) a graph-partitioning scheme that enables parallelizable trip generation. Using real- world Manhattan demand data, we show that the acceleration algorithms reduce the optimality gap by up to 27% under real-time constraints and cut empty travel time by up to 5%. These improve- ments translate into tangible economic and environmental benefits, advancing the scalability of high-capacity robo-taxi operations in dense urban settings.