Large-scale Online Ridesharing: The Effect of Assignment Optimality on System Performance

• URL: http://arxiv.org/abs/2305.02209v2
• Date: Tue, 16 Jan 2024 13:28:46 GMT
• Title: Large-scale Online Ridesharing: The Effect of Assignment Optimality on System Performance
• Authors: David Fiedler, Michal \v{C}ertick\'y, Javier Alonso-Mora, Michal P\v{e}chou\v{c}ek and Michal \v{C}\'ap
• Abstract summary: Mobility-on-demand (MoD) systems consist of a fleet of shared vehicles that can be hailed for one-way point-to-point trips. The total distance driven by the vehicles and the fleet size can be reduced by employing ridesharing, i.e., by assigning multiple passengers to one vehicle. We show how the VGA method, a recently proposed systematic method for ridesharing, can be used to compute the optimal passenger-vehicle assignments in an MoD system.
• Score: 13.010768187625352
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Mobility-on-demand (MoD) systems consist of a fleet of shared vehicles that can be hailed for one-way point-to-point trips. The total distance driven by the vehicles and the fleet size can be reduced by employing ridesharing, i.e., by assigning multiple passengers to one vehicle. However, finding the optimal passenger-vehicle assignment in an MoD system is a hard combinatorial problem. In this work, we demonstrate how the VGA method, a recently proposed systematic method for ridesharing, can be used to compute the optimal passenger-vehicle assignments and corresponding vehicle routes in a massive-scale MoD system. In contrast to existing works, we solve all passenger-vehicle assignment problems to optimality, regularly dealing with instances containing thousands of vehicles and passengers. Moreover, to examine the impact of using optimal ridesharing assignments, we compare the performance of an MoD system that uses optimal assignments against an MoD system that uses assignments computed using insertion heuristic and against an MoD system that uses no ridesharing. We found that the system that uses optimal ridesharing assignments subject to the maximum travel delay of 4 minutes reduces the vehicle distance driven by 57 % compared to an MoD system without ridesharing. Furthermore, we found that the optimal assignments result in a 20 % reduction in vehicle distance driven and 5 % lower average passenger travel delay compared to a system that uses insertion heuristic.

Related papers

• DiFSD: Ego-Centric Fully Sparse Paradigm with Uncertainty Denoising and Iterative Refinement for Efficient End-to-End Autonomous Driving [55.53171248839489]
  We propose an ego-centric fully sparse paradigm, named DiFSD, for end-to-end self-driving. Specifically, DiFSD mainly consists of sparse perception, hierarchical interaction and iterative motion planner. Experiments conducted on nuScenes dataset demonstrate the superior planning performance and great efficiency of DiFSD.
  arXiv  Detail & Related papers  (2024-09-15T15:55:24Z)
• FastRLAP: A System for Learning High-Speed Driving via Deep RL and Autonomous Practicing [71.76084256567599]
  We present a system that enables an autonomous small-scale RC car to drive aggressively from visual observations using reinforcement learning (RL) Our system, FastRLAP (faster lap), trains autonomously in the real world, without human interventions, and without requiring any simulation or expert demonstrations. The resulting policies exhibit emergent aggressive driving skills, such as timing braking and acceleration around turns and avoiding areas which impede the robot's motion, approaching the performance of a human driver using a similar first-person interface over the course of training.
  arXiv  Detail & Related papers  (2023-04-19T17:33:47Z)
• A greedy approach for increased vehicle utilization in ridesharing networks [0.3480973072524161]
  ridesharing platforms have become a prominent mode of transportation for the residents of urban areas. We propose a k-hop-based sliding window approximation algorithm that reduces the search space from entire road network to a window. We evaluate our proposed model on real-world datasets and experimental results demonstrate superior performance by our proposed model.
  arXiv  Detail & Related papers  (2023-04-02T07:25:01Z)
• Dial-a-ride problem with modular platooning and en-route transfers [0.0]
  A fleet of demand-responsive transit vehicles with such technology can serve passengers door to door or have deviate to platoon with each other to travel at lower cost. A mixed integer linear programming (MILP) model is formulated to solve this "modular dial-a-ride problem" A set of small-scale synthetic numerical experiments are tested to evaluate the optimality gap and computation time between exact solutions of the MDARP.
  arXiv  Detail & Related papers  (2022-12-01T05:29:46Z)
• Unified Automatic Control of Vehicular Systems with Reinforcement Learning [64.63619662693068]
  This article contributes a streamlined methodology for vehicular microsimulation. It discovers high performance control strategies with minimal manual design. The study reveals numerous emergent behaviors resembling wave mitigation, traffic signaling, and ramp metering.
  arXiv  Detail & Related papers  (2022-07-30T16:23:45Z)
• Value Function is All You Need: A Unified Learning Framework for Ride Hailing Platforms [57.21078336887961]
  Large ride-hailing platforms, such as DiDi, Uber and Lyft, connect tens of thousands of vehicles in a city to millions of ride demands throughout the day. We propose a unified value-based dynamic learning framework (V1D3) for tackling both tasks.
  arXiv  Detail & Related papers  (2021-05-18T19:22:24Z)
• Dynamic Bicycle Dispatching of Dockless Public Bicycle-sharing Systems using Multi-objective Reinforcement Learning [79.61517670541863]
  How to use AI to provide efficient bicycle dispatching solutions based on dynamic bicycle rental demand is an essential issue for dockless PBS (DL-PBS) We propose a dynamic bicycle dispatching algorithm based on multi-objective reinforcement learning (MORL-BD) to provide the optimal bicycle dispatching solution for DL-PBS.
  arXiv  Detail & Related papers  (2021-01-19T03:09:51Z)
• A multi-objective optimization framework for on-line ridesharing systems [6.247570729758392]
  We propose an algorithm that leverages biogeography-based optimization to solve a multi-objective optimization problem for online ridesharing. We test our algorithm by evaluatingperformance on the Beijing ridesharing dataset.
  arXiv  Detail & Related papers  (2020-12-07T16:25:39Z)
• Vehicular Cooperative Perception Through Action Branching and Federated Reinforcement Learning [101.64598586454571]
  A novel framework is proposed to allow reinforcement learning-based vehicular association, resource block (RB) allocation, and content selection of cooperative perception messages (CPMs) A federated RL approach is introduced in order to speed up the training process across vehicles. Results show that federated RL improves the training process, where better policies can be achieved within the same amount of time compared to the non-federated approach.
  arXiv  Detail & Related papers  (2020-12-07T02:09:15Z)
• PassGoodPool: Joint Passengers and Goods Fleet Management with Reinforcement Learning aided Pricing, Matching, and Route Planning [29.73314892749729]
  We present a demand aware fleet management framework for combined goods and passenger transportation. Our proposed model is deployable independently within each vehicle as this minimizes computational costs associated with the growth of distributed systems.
  arXiv  Detail & Related papers  (2020-11-17T23:15:03Z)
• The Benefits of Autonomous Vehicles for Community-Based Trip Sharing [20.51380943801894]
  This work reconsiders the concept of community-based trip sharing proposed by Hasan et al. It aims at quantifying the benefits of autonomous vehicles for community-based trip sharing, compared to a car-pooling platform where vehicles are driven by their owners. The results of the optimization show that it can leverage autonomous vehicles to reduce the daily vehicle usage by 92%, improving upon the results of the original Commute Trip Sharing Problem by 34%, while also reducing daily vehicle miles traveled by approximately 30%.
  arXiv  Detail & Related papers  (2020-08-28T18:12:13Z)

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.