# Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics

arXiv: https://arxiv.org/abs/2504.10649 · HTML: https://mlsanity.com/paper/2504.10649/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 25 references that are in the map.
- First posted on arXiv 14 Apr 2025.

## Builds on (most cited first, 8 of 8)

- [The SCIP Optimization Suite 9.0](https://mlsanity.com/paper/2402.17702/) (2024)
- [Neural Approximate Dynamic Programming for On-Demand Ride-Pooling](https://mlsanity.com/paper/1911.08842/) (2019)
- [Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning](https://mlsanity.com/paper/2103.04555/) (2021)
- [Quantifying the benefits of vehicle pooling with shareability networks](https://mlsanity.com/paper/1310.2963/) (2013)
- [Real-time City-scale Ridesharing via Linear Assignment Problems](https://mlsanity.com/paper/1902.10676/) (2019)
- [Zone pAth Construction (ZAC) based Approaches for Effective Real-Time Ridesharing](https://mlsanity.com/paper/2009.06051/) (2020)
- [Column Generation for Real-Time Ride-Sharing Operations](https://mlsanity.com/paper/2303.02522/) (2023)
- [On the Request-Trip-Vehicle Assignment Problem](https://mlsanity.com/paper/2011.09952/) (2020)

## Abstract (arXiv)

On-demand ride-pooling has emerged as a popular urban transportation solution, addressing the efficiency limitations of traditional ride-hailing services by grouping multiple riding requests with spatiotemporal proximity into a single vehicle. Although numerous algorithms have been developed for the Ride-pool Assignment Problem (RAP) -- a core component of ride-pooling systems, there is a lack of open-source implementations, making it difficult to benchmark these algorithms on a common dataset and objective. In this paper, we present the implementation details of a ride-pool simulator that encompasses several key ride-pool assignment algorithms, along with associated components such as vehicle routing and rebalancing. We also open-source a highly optimized and modular C++ codebase, designed to facilitate the extension of new algorithms and features. Additionally, we introduce a family of swapping-based local-search heuristics to enhance existing ride-pool assignment algorithms, achieving a better balance between performance and computational efficiency. Extensive experiments on a large-scale, real-world dataset from Manhattan, NYC reveal that while all selected algorithms perform comparably, the newly proposed Multi-Round Linear Assignment with Cyclic Exchange (LA-MR-CE) algorithm achieves a state-of-the-art service rate with significantly reduced computational time. Furthermore, an in-depth analysis suggests that a performance barrier exists for all myopic ride-pool assignment algorithms due to the system's capacity bottleneck, and incorporating future information could be key to overcoming this limitation.