ZAC: A zone path construction approach for effective real-time ridesharing
Real-time ridesharing systems such as UberPool, Lyft Line, GrabShare have become hugely popular as they reduce the costs for customers, improve per trip revenue for drivers and reduce traffic on the roads by grouping customers with similar itineraries. The key challenge in these systems is to group...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
AAAI Press
2021
|
| Online Access: | https://hdl.handle.net/1721.1/129337 |
| _version_ | 1826212291485368320 |
|---|---|
| author | Lowalekar, Meghna Varakantham, Pradeep 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, Meghna Varakantham, Pradeep Jaillet, Patrick |
| author_sort | Lowalekar, Meghna |
| collection | MIT |
| description | Real-time ridesharing systems such as UberPool, Lyft Line, GrabShare have become hugely popular as they reduce the costs for customers, improve per trip revenue for drivers and reduce traffic on the roads by grouping customers with similar itineraries. The key challenge in these systems is to group the right requests to travel in available vehicles in real-time, so that the objective (e.g., requests served, revenue or delay) is optimized. The most relevant existing work has focussed on generating as many relevant feasible (with respect to available delay for customers) combinations of requests (referred to as trips) as possible in real-time. Since the number of trips increases exponentially with the increase in vehicle capacity and number of requests, unfortunately, such an approach has to employ ad hoc heuristics to identify relevant trips. To that end, we propose an approach that generates many zone (abstraction of individual locations) paths - where each zone path can represent multiple trips (combinations of requests) - and assigns available vehicles to these zone paths to optimize the objective. The key advantage of our approach is that these zone paths are generated using a combination of offline and online methods, consequently allowing for the generation of many more relevant combinations in real-time than competing approaches. We demonstrate that our approach outperforms (with respect to both objective and runtime) the current best approach for ridesharing on both real world and synthetic datasets. |
| first_indexed | 2024-09-23T15:19:23Z |
| format | Article |
| id | mit-1721.1/129337 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:19:23Z |
| publishDate | 2021 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | mit-1721.1/1293372022-10-02T02:10:10Z ZAC: A zone path construction approach for effective real-time ridesharing Lowalekar, Meghna Varakantham, Pradeep Jaillet, Patrick Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Real-time ridesharing systems such as UberPool, Lyft Line, GrabShare have become hugely popular as they reduce the costs for customers, improve per trip revenue for drivers and reduce traffic on the roads by grouping customers with similar itineraries. The key challenge in these systems is to group the right requests to travel in available vehicles in real-time, so that the objective (e.g., requests served, revenue or delay) is optimized. The most relevant existing work has focussed on generating as many relevant feasible (with respect to available delay for customers) combinations of requests (referred to as trips) as possible in real-time. Since the number of trips increases exponentially with the increase in vehicle capacity and number of requests, unfortunately, such an approach has to employ ad hoc heuristics to identify relevant trips. To that end, we propose an approach that generates many zone (abstraction of individual locations) paths - where each zone path can represent multiple trips (combinations of requests) - and assigns available vehicles to these zone paths to optimize the objective. The key advantage of our approach is that these zone paths are generated using a combination of offline and online methods, consequently allowing for the generation of many more relevant combinations in real-time than competing approaches. We demonstrate that our approach outperforms (with respect to both objective and runtime) the current best approach for ridesharing on both real world and synthetic datasets. 2021-01-08T14:25:28Z 2021-01-08T14:25:28Z 2019-07 2020-12-21T18:30:11Z Article http://purl.org/eprint/type/ConferencePaper 2334-0843 https://hdl.handle.net/1721.1/129337 Lowalekar, Meghna, Pradeep Varakantham, Patrick Jaillet. “ZAC: A zone path construction approach for effective real-time ridesharing.” Proceedings International Conference on Automated Planning and Scheduling, ICAPS, 29 (July 2019): © 2019 The Author(s) en Proceedings International Conference on Automated Planning and Scheduling, ICAPS Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf AAAI Press MIT web domain |
| spellingShingle | Lowalekar, Meghna Varakantham, Pradeep Jaillet, Patrick ZAC: A zone path construction approach for effective real-time ridesharing |
| title | ZAC: A zone path construction approach for effective real-time ridesharing |
| title_full | ZAC: A zone path construction approach for effective real-time ridesharing |
| title_fullStr | ZAC: A zone path construction approach for effective real-time ridesharing |
| title_full_unstemmed | ZAC: A zone path construction approach for effective real-time ridesharing |
| title_short | ZAC: A zone path construction approach for effective real-time ridesharing |
| title_sort | zac a zone path construction approach for effective real time ridesharing |
| url | https://hdl.handle.net/1721.1/129337 |
| work_keys_str_mv | AT lowalekarmeghna zacazonepathconstructionapproachforeffectiverealtimeridesharing AT varakanthampradeep zacazonepathconstructionapproachforeffectiverealtimeridesharing AT jailletpatrick zacazonepathconstructionapproachforeffectiverealtimeridesharing |