论文标题
在线多容量乘车共享的竞争比率
Competitive Ratios for Online Multi-capacity Ridesharing
论文作者
论文摘要
在多重容量的乘车共享中，具有不同来源和目的地对的多个请求（例如，客户，食品，包裹，包裹）在一个资源中旅行。近年来，Uber-Pool，Foodpanda和按需班车在线多容量乘车服务（即，在线完成任务）在运输，食品交付，物流和其他领域都非常受欢迎。这是因为多容量的乘车共享服务使所有涉及的各方受益{客户（由于成本较低），驾驶员（由于收入较高）和匹配平台（由于每辆车/资源的收入较高）。最重要的是，这些服务还可以帮助减少碳排放量（由于道路上的车辆较少）。 在线多容量乘车共享非常具有挑战性，因为基础匹配图不再是两分（如在单位容量案例中），而是带有资源（例如，出租车，汽车），请求和请求组（可以一起旅行的请求组的组合）的三方图（例如，出租车，汽车）。资源和请求组之间的所需匹配受此三方图中的请求和请求组之间的边缘的约束（即，最终分配中最多可以是一个请求组的一部分）。尽管采用了用于解决在线多重乘车问题的近视启发式方法，但它们并未提供有关解决方案质量的任何保证。为此，本文介绍了第一种方法，其在线多容量乘车共享的竞争比率（当资源在提供一组请求后，资源在其初始位置/仓库中重新加入系统时）。
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).
