Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics

• URL: http://arxiv.org/abs/2504.10649v1
• Date: Mon, 14 Apr 2025 19:01:47 GMT
• Title: Ride-pool Assignment Algorithms: Modern Implementation and Swapping Heuristics
• Authors: Matthew Zalesak, Hins Hu, Samitha Samaranayake,
• Abstract summary: We present a ride-pool simulator that encompasses several key ride-pool assignment algorithms, along with associated components such as vehicle routing and rebalancing.<n>We also open-source a highly optimized and modular C++, designed to facilitate extension of new algorithms.<n>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 achieves a state-of-the-art service rate with significantly reduced computational time.
• Score: 3.5112462023222504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Accelerating Vehicle Routing via AI-Initialized Genetic Algorithms [55.78505925402658]
  Vehicle Routing Problems (VRP) are an extension of the Traveling Salesperson Problem and are a fundamental NP-hard challenge in Evolutionary optimization.<n>We introduce a novel optimization framework that uses a reinforcement learning agent - trained on prior instances - to quickly generate initial solutions, which are then further optimized by genetic algorithms.<n>For example, EARLI handles vehicle routing with 500 locations within 1s, 10x faster than current solvers for the same solution quality, enabling applications like real-time and interactive routing.
  arXiv  Detail & Related papers  (2025-04-08T15:21:01Z)
• A Multiagent Path Search Algorithm for Large-Scale Coalition Structure Generation [61.08720171136229]
  Coalition structure generation is a fundamental computational problem in multiagent systems.<n>We develop SALDAE, a multiagent path finding algorithm for CSG that operates on a graph of coalition structures.
  arXiv  Detail & Related papers  (2025-02-14T15:21:27Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Fast and computationally efficient generative adversarial network algorithm for unmanned aerial vehicle-based network coverage optimization [1.2853186701496802]
  The challenge of dynamic traffic demand in mobile networks is tackled by moving cells based on unmanned aerial vehicles. Considering the tremendous potential of unmanned aerial vehicles in the future, we propose a new algorithm for coverage optimization. The proposed algorithm is implemented based on a conditional generative adversarial neural network, with a unique multilayer sum-pooling loss function.
  arXiv  Detail & Related papers  (2022-03-25T12:13:21Z)
• Online V2X Scheduling for Raw-Level Cooperative Perception [21.099819062731463]
  Cooperative perception of connected vehicles comes to the rescue when the field of view restricts stand-alone intelligence. We present a model of raw-level cooperative perception and formulate the energy minimization problem of sensor sharing scheduling. We propose an online learning-based algorithm with logarithmic performance loss, achieving a decent trade-off between exploration and exploitation.
  arXiv  Detail & Related papers  (2022-02-12T15:16:45Z)
• Real-world Ride-hailing Vehicle Repositioning using Deep Reinforcement Learning [52.2663102239029]
  We present a new practical framework based on deep reinforcement learning and decision-time planning for real-world vehicle on idle-hailing platforms. Our approach learns ride-based state-value function using a batch training algorithm with deep value. We benchmark our algorithm with baselines in a ride-hailing simulation environment to demonstrate its superiority in improving income efficiency.
  arXiv  Detail & Related papers  (2021-03-08T05:34:05Z)
• A Hybrid Multi-Objective Carpool Route Optimization Technique using Genetic Algorithm and A* Algorithm [0.0]
  This work presents a hybrid GA-A* algorithm to obtain optimal routes for the carpooling problem. The routes obtained maximize the profit of the service provider by minimizing the travel and detour distance as well as pick-up/drop costs. The proposed algorithm has been implemented over the Salt Lake area of Kolkata.
  arXiv  Detail & Related papers  (2020-07-11T14:13:20Z)
• Reinforcement Learning Based Vehicle-cell Association Algorithm for Highly Mobile Millimeter Wave Communication [53.47785498477648]
  This paper investigates the problem of vehicle-cell association in millimeter wave (mmWave) communication networks. We first formulate the user state (VU) problem as a discrete non-vehicle association optimization problem. The proposed solution achieves up to 15% gains in terms sum of user complexity and 20% reduction in VUE compared to several baseline designs.
  arXiv  Detail & Related papers  (2020-01-22T08:51:05Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.