Fundamental performance limits and efficient polices for Transportation-On-Demand systems
Transportation-On-Demand (TOD) systems, where users generate requests for transportation from a pick-up point to a delivery point, are already very popular and are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. Routing...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2011
|
| Online Access: | http://hdl.handle.net/1721.1/65388 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1826189814847766528 |
|---|---|
| author | Pavone, Marco Treleaven, Kyle Ballantyne Frazzoli, Emilio |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Pavone, Marco Treleaven, Kyle Ballantyne Frazzoli, Emilio |
| author_sort | Pavone, Marco |
| collection | MIT |
| description | Transportation-On-Demand (TOD) systems, where users generate requests for transportation from a pick-up point to a delivery point, are already very popular and are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. Routing service vehicles through customers is usually accomplished with heuristic algorithms. In this paper we study TOD systems in a formal setting that allows us to characterize fundamental performance limits and devise dynamic routing policies with provable performance guarantees. Specifically, we study TOD systems in the form of a unit-capacity, multiple-vehicle dynamic pick-up and delivery problem, whereby pick-up requests arrive according to a Poisson process and are randomly located according to a general probability density. Corresponding delivery locations are also randomly distributed according to a general probability density, and a number of unit-capacity vehicles must transport demands from their pick-up locations to their delivery locations. We derive insightful fundamental bounds on the steady-state waiting times for the demands, and we devise constant-factor optimal dynamic routing policies. Simulation results are presented and discussed. |
| first_indexed | 2024-09-23T08:22:59Z |
| format | Article |
| id | mit-1721.1/65388 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:22:59Z |
| publishDate | 2011 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/653882022-09-23T12:34:16Z Fundamental performance limits and efficient polices for Transportation-On-Demand systems Pavone, Marco Treleaven, Kyle Ballantyne Frazzoli, Emilio Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Frazzoli, Emilio Pavone, Marco Treleaven, Kyle Ballantyne Frazzoli, Emilio Transportation-On-Demand (TOD) systems, where users generate requests for transportation from a pick-up point to a delivery point, are already very popular and are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. Routing service vehicles through customers is usually accomplished with heuristic algorithms. In this paper we study TOD systems in a formal setting that allows us to characterize fundamental performance limits and devise dynamic routing policies with provable performance guarantees. Specifically, we study TOD systems in the form of a unit-capacity, multiple-vehicle dynamic pick-up and delivery problem, whereby pick-up requests arrive according to a Poisson process and are randomly located according to a general probability density. Corresponding delivery locations are also randomly distributed according to a general probability density, and a number of unit-capacity vehicles must transport demands from their pick-up locations to their delivery locations. We derive insightful fundamental bounds on the steady-state waiting times for the demands, and we devise constant-factor optimal dynamic routing policies. Simulation results are presented and discussed. Singapore-MIT Alliance for Research and Technology Center Singapore. National Research Foundation 2011-08-26T13:53:24Z 2011-08-26T13:53:24Z 2011-02 2010-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4244-7745-6 0743-1546 INSPEC Accession Number: 11848849 http://hdl.handle.net/1721.1/65388 Pavone, Marco, Kyle Treleaven, and Emilio Frazzoli. “Fundamental Performance Limits and Efficient Polices for Transportation-On-Demand Systems.” 49th IEEE Conference on Decision and Control (CDC). Atlanta, GA, USA, 2010. 5622-5629. © 2011 IEEE https://orcid.org/0000-0002-0505-1400 en_US http://dx.doi.org/10.1109/CDC.2010.5717552 49th IEEE Conference on Decision and Control (CDC), 2010 Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Pavone, Marco Treleaven, Kyle Ballantyne Frazzoli, Emilio Fundamental performance limits and efficient polices for Transportation-On-Demand systems |
| title | Fundamental performance limits and efficient polices for Transportation-On-Demand systems |
| title_full | Fundamental performance limits and efficient polices for Transportation-On-Demand systems |
| title_fullStr | Fundamental performance limits and efficient polices for Transportation-On-Demand systems |
| title_full_unstemmed | Fundamental performance limits and efficient polices for Transportation-On-Demand systems |
| title_short | Fundamental performance limits and efficient polices for Transportation-On-Demand systems |
| title_sort | fundamental performance limits and efficient polices for transportation on demand systems |
| url | http://hdl.handle.net/1721.1/65388 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT pavonemarco fundamentalperformancelimitsandefficientpolicesfortransportationondemandsystems AT treleavenkyleballantyne fundamentalperformancelimitsandefficientpolicesfortransportationondemandsystems AT frazzoliemilio fundamentalperformancelimitsandefficientpolicesfortransportationondemandsystems |