Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

5-2020

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). The competitive ratio is : (i) 0.31767 for capacity 2; and (ii) γ for any general capacity κ, where γ is a solution to the equation γ = (1 −γ ) κ+1 .

Keywords

Competitive ratio, Food delivery, Carbon emissions

Discipline

Urban Studies and Planning

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS.

First Page

771

Last Page

779

ISBN

9781450375184

Publisher

IFAAMAS

City or Country

UK

Download

Share

COinS