Competitive ratios for online multi-capacity ridesharing
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 s...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
International Foundation for Autonomous Agents and Multiagent Systems
2021
|
| Online Access: | https://hdl.handle.net/1721.1/128924 |
| _version_ | 1811084458198040576 |
|---|---|
| author | Lowalekar, M Varakantham, P Jaillet, Patrick |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Lowalekar, M Varakantham, P Jaillet, Patrick |
| author_sort | Lowalekar, M |
| collection | MIT |
| description | 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 |
| first_indexed | 2024-09-23T12:51:04Z |
| format | Article |
| id | mit-1721.1/128924 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:51:04Z |
| publishDate | 2021 |
| publisher | International Foundation for Autonomous Agents and Multiagent Systems |
| record_format | dspace |
| spelling | mit-1721.1/1289242022-09-28T10:29:12Z Competitive ratios for online multi-capacity ridesharing Lowalekar, M Varakantham, P Jaillet, Patrick Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science 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 2021-01-04T15:47:19Z 2021-01-04T15:47:19Z 2020-05 2020-12-21T18:38:57Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/128924 Lowalekar, M. et al. "Competitive ratios for online multi-capacity ridesharing." Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, May 2020, Auckland, New Zealand, International Foundation for Autonomous Agents and Multiagent Systems, May 2020. © 2020 International Foundation for Autonomous Agents and Multiagent Systems en http://www.ifaamas.org/Proceedings/aamas2020/forms/contents.htm Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf International Foundation for Autonomous Agents and Multiagent Systems arXiv |
| spellingShingle | Lowalekar, M Varakantham, P Jaillet, Patrick Competitive ratios for online multi-capacity ridesharing |
| title | Competitive ratios for online multi-capacity ridesharing |
| title_full | Competitive ratios for online multi-capacity ridesharing |
| title_fullStr | Competitive ratios for online multi-capacity ridesharing |
| title_full_unstemmed | Competitive ratios for online multi-capacity ridesharing |
| title_short | Competitive ratios for online multi-capacity ridesharing |
| title_sort | competitive ratios for online multi capacity ridesharing |
| url | https://hdl.handle.net/1721.1/128924 |
| work_keys_str_mv | AT lowalekarm competitiveratiosforonlinemulticapacityridesharing AT varakanthamp competitiveratiosforonlinemulticapacityridesharing AT jailletpatrick competitiveratiosforonlinemulticapacityridesharing |