Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems
In this paper we study rebalancing strategies for a mobility-on-demand urban transportation system blending customer-driven vehicles with a taxi service. In our system, a customer arrives at one of many designated stations and is transported to any other designated station, either by driving themsel...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
American Automatic Control Council
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81786 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1826209461221457920 |
|---|---|
| author | Smith, Stephen L. Pavone, Marco Schwager, Mac Frazzoli, Emilio Rus, Daniela L. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Smith, Stephen L. Pavone, Marco Schwager, Mac Frazzoli, Emilio Rus, Daniela L. |
| author_sort | Smith, Stephen L. |
| collection | MIT |
| description | In this paper we study rebalancing strategies for a mobility-on-demand urban transportation system blending customer-driven vehicles with a taxi service. In our system, a customer arrives at one of many designated stations and is transported to any other designated station, either by driving themselves, or by being driven by an employed driver. When some origins and destinations are more popular than others, vehicles will become unbalanced, accumulating at some stations and becoming depleted at others. This problem is addressed by employing rebalancing drivers to drive vehicles from the popular destinations to the unpopular destinations. However, with this approach the rebalancing drivers themselves become unbalanced, and we need to “rebalance the rebalancers” by letting them travel back to the popular destinations with a customer. In this paper we study how to optimally route the rebalancing vehicles and drivers so that the number of waiting customers remains bounded while minimizing the number of rebalancing vehicles traveling in the network and the number of rebalancing drivers needed; surprisingly, these two objectives are aligned, and one can find the optimal rebalancing strategy by solving two decoupled linear programs. We determine the minimum number of drivers and minimum number of vehicles needed to ensure stability in the system. Our simulations suggest that, in Euclidean network topologies, one would need between 1/3 and 1/4 as many drivers as vehicles. |
| first_indexed | 2024-09-23T14:22:52Z |
| format | Article |
| id | mit-1721.1/81786 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:22:52Z |
| publishDate | 2013 |
| publisher | American Automatic Control Council |
| record_format | dspace |
| spelling | mit-1721.1/817862022-10-01T20:56:19Z Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems Smith, Stephen L. Pavone, Marco Schwager, Mac Frazzoli, Emilio Rus, Daniela L. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Pavone, Marco Frazzoli, Emilio Rus, Daniela L. In this paper we study rebalancing strategies for a mobility-on-demand urban transportation system blending customer-driven vehicles with a taxi service. In our system, a customer arrives at one of many designated stations and is transported to any other designated station, either by driving themselves, or by being driven by an employed driver. When some origins and destinations are more popular than others, vehicles will become unbalanced, accumulating at some stations and becoming depleted at others. This problem is addressed by employing rebalancing drivers to drive vehicles from the popular destinations to the unpopular destinations. However, with this approach the rebalancing drivers themselves become unbalanced, and we need to “rebalance the rebalancers” by letting them travel back to the popular destinations with a customer. In this paper we study how to optimally route the rebalancing vehicles and drivers so that the number of waiting customers remains bounded while minimizing the number of rebalancing vehicles traveling in the network and the number of rebalancing drivers needed; surprisingly, these two objectives are aligned, and one can find the optimal rebalancing strategy by solving two decoupled linear programs. We determine the minimum number of drivers and minimum number of vehicles needed to ensure stability in the system. Our simulations suggest that, in Euclidean network topologies, one would need between 1/3 and 1/4 as many drivers as vehicles. Singapore-MIT Alliance for Research and Technology ( Future Urban Mobility project) Singapore. National Research Foundation United States. Office of Naval Research (ONR grant N000140911051) 2013-10-25T18:10:55Z 2013-10-25T18:10:55Z 2013-06 Article http://purl.org/eprint/type/ConferencePaper 0743-1619 http://hdl.handle.net/1721.1/81786 Smith, Stephen L., Marco Pavone, Mac Schwager, Emilio Frazzoli, and Daniela Rus. "Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems." 2013 American Control Conference (ACC) Washington, DC, USA, June 17-19, 2013. American Automatic Control Council. https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0002-0505-1400 en_US http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6580187 Proceedings of the 2013 American Control Conference Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf American Automatic Control Council arXiv |
| spellingShingle | Smith, Stephen L. Pavone, Marco Schwager, Mac Frazzoli, Emilio Rus, Daniela L. Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems |
| title | Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems |
| title_full | Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems |
| title_fullStr | Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems |
| title_full_unstemmed | Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems |
| title_short | Rebalancing the rebalancers: Optimally routing vehicles and drivers in mobility-on-demand systems |
| title_sort | rebalancing the rebalancers optimally routing vehicles and drivers in mobility on demand systems |
| url | http://hdl.handle.net/1721.1/81786 https://orcid.org/0000-0001-5473-3566 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT smithstephenl rebalancingtherebalancersoptimallyroutingvehiclesanddriversinmobilityondemandsystems AT pavonemarco rebalancingtherebalancersoptimallyroutingvehiclesanddriversinmobilityondemandsystems AT schwagermac rebalancingtherebalancersoptimallyroutingvehiclesanddriversinmobilityondemandsystems AT frazzoliemilio rebalancingtherebalancersoptimallyroutingvehiclesanddriversinmobilityondemandsystems AT rusdanielal rebalancingtherebalancersoptimallyroutingvehiclesanddriversinmobilityondemandsystems |