  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).
