Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps
One of the most common combinatorial problems in logistics and transportation-after the Traveling Salesman Problem-is the Stacker Crane Problem (SCP), where commodities or customers are associated each with a pickup location and a delivery location, and the objective is to find a minimum-length tour...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2013
|
| Online Access: | http://hdl.handle.net/1721.1/81779 |
| _version_ | 1826198060412174336 |
|---|---|
| author | Treleaven, Kyle Pavone, Marco Frazzoli, Emilio |
| author2 | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems |
| author_facet | Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Treleaven, Kyle Pavone, Marco Frazzoli, Emilio |
| author_sort | Treleaven, Kyle |
| collection | MIT |
| description | One of the most common combinatorial problems in logistics and transportation-after the Traveling Salesman Problem-is the Stacker Crane Problem (SCP), where commodities or customers are associated each with a pickup location and a delivery location, and the objective is to find a minimum-length tour `picking up' and `delivering' all items, while ensuring the number of items on-board never exceeds a given capacity. While vastly many SCPs encountered in practice are embedded in road or road-like networks, very few studies explicitly consider such environments. In this paper, first, we formulate an environment model capturing the essential features of a “small-neighborhood” road network, along with models for omni-directional vehicles and directed vehicles. Then, we formulate a stochastic version of the unit-capacity SCP, on our road network model, where pickup/delivery sites are random points along segments of the network. Our main contribution is a polynomial-time algorithm for the problem that is asymptotically constant-factor; i.e., it produces a solution no worse than κ+o(1) times the length of the optimal one, where o(1) goes to zero as the number of items grows large, almost surely. The constant κ is at most 3, and for omni-directional vehicles it is provably 1, i.e., optimal. Simulations show that with a number of pickup/delivery pairs as low as 50, the proposed algorithm delivers a solution whose cost is consistently within 10% of that of an optimal solution. |
| first_indexed | 2024-09-23T10:58:14Z |
| format | Article |
| id | mit-1721.1/81779 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:58:14Z |
| publishDate | 2013 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/817792024-06-13T15:06:46Z Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps Models and efficient algorithms for pickup and delivery problems on roadmaps Treleaven, Kyle Pavone, Marco Frazzoli, Emilio Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Department of Aeronautics and Astronautics One of the most common combinatorial problems in logistics and transportation-after the Traveling Salesman Problem-is the Stacker Crane Problem (SCP), where commodities or customers are associated each with a pickup location and a delivery location, and the objective is to find a minimum-length tour `picking up' and `delivering' all items, while ensuring the number of items on-board never exceeds a given capacity. While vastly many SCPs encountered in practice are embedded in road or road-like networks, very few studies explicitly consider such environments. In this paper, first, we formulate an environment model capturing the essential features of a “small-neighborhood” road network, along with models for omni-directional vehicles and directed vehicles. Then, we formulate a stochastic version of the unit-capacity SCP, on our road network model, where pickup/delivery sites are random points along segments of the network. Our main contribution is a polynomial-time algorithm for the problem that is asymptotically constant-factor; i.e., it produces a solution no worse than κ+o(1) times the length of the optimal one, where o(1) goes to zero as the number of items grows large, almost surely. The constant κ is at most 3, and for omni-directional vehicles it is provably 1, i.e., optimal. Simulations show that with a number of pickup/delivery pairs as low as 50, the proposed algorithm delivers a solution whose cost is consistently within 10% of that of an optimal solution. Singapore-MIT Alliance for Research and Technology Center 2013-10-25T16:27:41Z 2013-10-25T16:27:41Z 2012-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-2066-5 978-1-4673-2065-8 978-1-4673-2063-4 978-1-4673-2064-1 http://hdl.handle.net/1721.1/81779 Treleaven, Kyle, Marco Pavone, and Emilio Frazzoli. “Models and efficient algorithms for pickup and delivery problems on roadmaps.” In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), 5691-5698. Institute of Electrical and Electronics Engineers, 2012. en_US http://dx.doi.org/10.1109/CDC.2012.6426164 Proceedings of the 2012 IEEE 51st IEEE Conference on Decision and Control (CDC) Creative Commons Attribution-Noncommercial-Share Alike 3.0 http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Other univ. web domain |
| spellingShingle | Treleaven, Kyle Pavone, Marco Frazzoli, Emilio Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| title | Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| title_full | Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| title_fullStr | Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| title_full_unstemmed | Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| title_short | Models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| title_sort | models and asymptotically optimal algorithms for pickup and delivery problems on roadmaps |
| url | http://hdl.handle.net/1721.1/81779 |
| work_keys_str_mv | AT treleavenkyle modelsandasymptoticallyoptimalalgorithmsforpickupanddeliveryproblemsonroadmaps AT pavonemarco modelsandasymptoticallyoptimalalgorithmsforpickupanddeliveryproblemsonroadmaps AT frazzoliemilio modelsandasymptoticallyoptimalalgorithmsforpickupanddeliveryproblemsonroadmaps AT treleavenkyle modelsandefficientalgorithmsforpickupanddeliveryproblemsonroadmaps AT pavonemarco modelsandefficientalgorithmsforpickupanddeliveryproblemsonroadmaps AT frazzoliemilio modelsandefficientalgorithmsforpickupanddeliveryproblemsonroadmaps |