Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems
Demand-responsive transport (DRT) systems, where users generate requests for transportation from a pickup point to a delivery point, are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. However, despite the increasing ro...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
American Automatic Control Council
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81871 https://orcid.org/0000-0002-0505-1400 |
| _version_ | 1826214618997981184 |
|---|---|
| author | Treleaven, Kyle Ballantyne Pavone, Marco Frazzoli, Emilio |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Treleaven, Kyle Ballantyne Pavone, Marco Frazzoli, Emilio |
| author_sort | Treleaven, Kyle Ballantyne |
| collection | MIT |
| description | Demand-responsive transport (DRT) systems, where users generate requests for transportation from a pickup point to a delivery point, are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. However, despite the increasing role of DRT systems, there are very few rigorous results characterizing achievable performance (in terms, e.g., of stability conditions). In this paper, our aim is to bridge this gap for a rather general model of DRT systems, which takes the form of a generalized Dynamic Pickup and Delivery Problem. The key strategy is to develop analytical bounds for the optimal cost of the Euclidean Stacker Crane Problem (ESCP), which represents a general static model for DRT systems. By leveraging such bounds, we characterize a necessary and sufficient condition for the stability of DRT systems; the condition depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, customers' arrival rate, and the number of vehicles. Our results exhibit some surprising features that are absent in traditional spatially-distributed queueing systems. |
| first_indexed | 2024-09-23T16:08:21Z |
| format | Article |
| id | mit-1721.1/81871 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:08:21Z |
| publishDate | 2013 |
| publisher | American Automatic Control Council |
| record_format | dspace |
| spelling | mit-1721.1/818712022-10-02T06:35:47Z Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems Treleaven, Kyle Ballantyne Pavone, Marco Frazzoli, Emilio Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Treleaven, Kyle Ballantyne Frazzoli, Emilio Demand-responsive transport (DRT) systems, where users generate requests for transportation from a pickup point to a delivery point, are expected to increase in usage dramatically as the inconvenience of privately-owned cars in metropolitan areas becomes excessive. However, despite the increasing role of DRT systems, there are very few rigorous results characterizing achievable performance (in terms, e.g., of stability conditions). In this paper, our aim is to bridge this gap for a rather general model of DRT systems, which takes the form of a generalized Dynamic Pickup and Delivery Problem. The key strategy is to develop analytical bounds for the optimal cost of the Euclidean Stacker Crane Problem (ESCP), which represents a general static model for DRT systems. By leveraging such bounds, we characterize a necessary and sufficient condition for the stability of DRT systems; the condition depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, customers' arrival rate, and the number of vehicles. Our results exhibit some surprising features that are absent in traditional spatially-distributed queueing systems. Singapore-MIT Alliance for Research and Technology (Future Urban Mobility project) Singapore. National Research Foundation 2013-10-30T14:29:41Z 2013-10-30T14:29:41Z 2012-06 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-2102-0 978-1-4577-1095-7 0743-1619 INSPEC Accession Number: 13036296 http://hdl.handle.net/1721.1/81871 Treleaven, Kyle Ballantyne, Marco Pavone, and Emilio Frazzoli. "Cost bounds for Pickup and Delivery Problems with application to large-scale transportation systems." In 2012 American Control Conference, Fairmont Queen Elizabeth, Montréal, Canada, June 27-June 29, 2012. pp. 2120 - 2127. https://orcid.org/0000-0002-0505-1400 en_US http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6315329 Proceedings of the 2012 American Control Conference (ACC) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf American Automatic Control Council Other univ. web domain |
| spellingShingle | Treleaven, Kyle Ballantyne Pavone, Marco Frazzoli, Emilio Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems |
| title | Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems |
| title_full | Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems |
| title_fullStr | Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems |
| title_full_unstemmed | Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems |
| title_short | Cost Bounds for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems |
| title_sort | cost bounds for pickup and delivery problems with application to large scale transportation systems |
| url | http://hdl.handle.net/1721.1/81871 https://orcid.org/0000-0002-0505-1400 |
| work_keys_str_mv | AT treleavenkyleballantyne costboundsforpickupanddeliveryproblemswithapplicationtolargescaletransportationsystems AT pavonemarco costboundsforpickupanddeliveryproblemswithapplicationtolargescaletransportationsystems AT frazzoliemilio costboundsforpickupanddeliveryproblemswithapplicationtolargescaletransportationsystems |