Competitive Ratios for Online Multi-capacity Ridesharing

• URL: http://arxiv.org/abs/2009.07925v1
• Date: Wed, 16 Sep 2020 20:29:21 GMT
• Title: Competitive Ratios for Online Multi-capacity Ridesharing
• Authors: Meghna Lowalekar, Pradeep Varakantham, Patrick Jaillet
• Abstract summary: In multi-capacity ridesharing, multiple requests (e.g., customers, food items, parcels) with different origin and destination pairs travel in one resource. Online multi-capacity ridesharing is extremely challenging as the underlying matching graph is no longer bipartite. This paper presents the first approach with bounds on the competitive ratio for online multi-capacity ridesharing.
• Score: 30.964687022746226
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In multi-capacity ridesharing, multiple requests (e.g., customers, food items, parcels) with different origin and destination pairs travel in one resource. In recent years, online multi-capacity ridesharing services (i.e., where assignments are made online) like Uber-pool, foodpanda, and on-demand shuttles have become hugely popular in transportation, food delivery, logistics and other domains. This is because multi-capacity ridesharing services benefit all parties involved { the customers (due to lower costs), the drivers (due to higher revenues) and the matching platforms (due to higher revenues per vehicle/resource). Most importantly these services can also help reduce carbon emissions (due to fewer vehicles on roads). Online multi-capacity ridesharing is extremely challenging as the underlying matching graph is no longer bipartite (as in the unit-capacity case) but a tripartite graph with resources (e.g., taxis, cars), requests and request groups (combinations of requests that can travel together). The desired matching between resources and request groups is constrained by the edges between requests and request groups in this tripartite graph (i.e., a request can be part of at most one request group in the final assignment). While there have been myopic heuristic approaches employed for solving the online multi-capacity ridesharing problem, they do not provide any guarantees on the solution quality. To that end, this paper presents the first approach with bounds on the competitive ratio for online multi-capacity ridesharing (when resources rejoin the system at their initial location/depot after serving a group of requests).

Related papers

• Mutual Information as Intrinsic Reward of Reinforcement Learning Agents for On-demand Ride Pooling [19.247162142334076]
  On-demand vehicle pooling services allow each vehicle to serve multiple passengers at a time. Existing algorithms often only consider revenue, which makes it difficult for requests with unusual distribution to get a ride. We propose a framework for dispatching for ride pooling tasks, which splits the city into discrete dispatching and uses the reinforcement learning (RL) algorithm to dispatch vehicles in these regions.
  arXiv  Detail & Related papers  (2023-12-23T08:34:52Z)
• Fair collaborative vehicle routing: A deep multi-agent reinforcement learning approach [49.00137468773683]
  Collaborative vehicle routing occurs when carriers collaborate through sharing their transportation requests and performing transportation requests on behalf of each other. Traditional game theoretic solution concepts are expensive to calculate as the characteristic function scales exponentially with the number of agents. We propose to model this problem as a coalitional bargaining game solved using deep multi-agent reinforcement learning.
  arXiv  Detail & Related papers  (2023-10-26T15:42:29Z)
• Coalitional Bargaining via Reinforcement Learning: An Application to Collaborative Vehicle Routing [49.00137468773683]
  Collaborative Vehicle Routing is where delivery companies cooperate by sharing their delivery information and performing delivery requests on behalf of each other. This achieves economies of scale and thus reduces cost, greenhouse gas emissions, and road congestion. But which company should partner with whom, and how much should each company be compensated? Traditional game theoretic solution concepts, such as the Shapley value or nucleolus, are difficult to calculate for the real-world problem of Collaborative Vehicle Routing.
  arXiv  Detail & Related papers  (2023-10-26T15:04:23Z)
• Modeling routing problems in QUBO with application to ride-hailing [0.0]
  We focus on one such routing problem, the Ride Pooling Problem (RPP), where multiple customers can request on-demand pickups and drop-offs from shared vehicles within a fleet. The task is to optimally pool customer requests using the limited set of vehicles, akin to a small-scale flexible bus route.
  arXiv  Detail & Related papers  (2022-12-09T14:55:34Z)
• Efficiency, Fairness, and Stability in Non-Commercial Peer-to-Peer Ridesharing [84.47891614815325]
  This paper focuses on the core problem in P2P ridesharing: the matching of riders and drivers. We introduce novel notions of fairness and stability in P2P ridesharing. Results suggest that fair and stable solutions can be obtained in reasonable computational times.
  arXiv  Detail & Related papers  (2021-10-04T02:14:49Z)
• 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)
• Joint predictions of multi-modal ride-hailing demands: a deep multi-task multigraph learning-based approach [64.18639899347822]
  We propose a deep multi-task multi-graph learning approach, which combines multiple multi-graph convolutional (MGC) networks for predicting demands for different service modes. We show that our propose approach outperforms the benchmark algorithms in prediction accuracy for different ride-hailing modes.
  arXiv  Detail & Related papers  (2020-11-11T07:10:50Z)
• Zone pAth Construction (ZAC) based Approaches for Effective Real-Time Ridesharing [30.964687022746226]
  Key challenge in real-time ridesharing systems is to group the "right" requests to travel together in the "right" available vehicles in real-time. We contribute both myopic (ridesharing assignment focussed on current requests only) and non-myopic (ridesharing considers impact on expected future requests) approaches that employ zone paths.
  arXiv  Detail & Related papers  (2020-09-13T17:57:15Z)
• Balancing Taxi Distribution in A City-Scale Dynamic Ridesharing Service: A Hybrid Solution Based on Demand Learning [0.0]
  We study the challenging problem of how to balance taxi distribution across a city in a dynamic ridesharing service. We propose a hybrid solution involving a series of algorithms: the Correlated Pooling collects correlated rider requests, the Adjacency Ride-Matching based on Demand Learning assigns taxis to riders, and the Greedy Idle Movement aims to direct taxis without a current assignment to the areas with riders in need of service.
  arXiv  Detail & Related papers  (2020-07-27T07:08:02Z)
• Modeling and solving the multimodal car- and ride-sharing problem [0.0]
  We introduce the multimodal car- and ride-sharing problem (MMCRP) A pool of cars is used to cover a set of ride requests while uncovered requests are assigned to other modes of transport. We propose a two-layer decomposition algorithm based on column generation.
  arXiv  Detail & Related papers  (2020-01-15T09:43:55Z)

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.