other · DSpace@MIT (Massachusetts Institute of Technology) · 2011
An asymptotically optimal algorithm for pickup and delivery problems
Pavone, Marco, Frazzoli, Emilio, Treleaven, Kyle Ballantyne
Cited by 0Open access
Abstract
Pickup and delivery problems (PDPs), in which objects or people have to be transported between specific locations, are among the most common combinatorial problems in real-world operations. One particular PDP is the Stacker Crane problem (SCP), where each commodity/customer is associated with a pickup location and a delivery location, and the objective is to find a minimum-length tour visiting all locations with the constraint that each pickup location and its associated delivery location are visited in consecutive order. The SCP is a route optimization problem behind several transportation systems, e.g., Transportation-On-Demand (TOD) systems. The SCP is NP-Hard and the best know approximation algorithm only provides a 9/5 approximation ratio. We present an algorithm for the stochastic SCP which: (i) is asymptotically optimal, i.e., it produces a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; and (ii) has computational complexity O(n[superscript 2+ϵ]), where n is the number of pickup/delivery pairs and ϵ is an arbitrarily small positive constant. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations.
Cite this paper
Pavone, M., Frazzoli, E., & Treleaven, K. B. (2011). An asymptotically optimal algorithm for pickup and delivery problems. DSpace@MIT (Massachusetts Institute of Technology).
Pavone, Marco, et al. “An asymptotically optimal algorithm for pickup and delivery problems.” DSpace@MIT (Massachusetts Institute of Technology), 2011.
Pavone, Marco, Emilio Frazzoli, and Kyle Ballantyne Treleaven. 2011. “An asymptotically optimal algorithm for pickup and delivery problems.” DSpace@MIT (Massachusetts Institute of Technology).
Pavone, M., Frazzoli, E. and Treleaven, K.B. (2011) ‘An asymptotically optimal algorithm for pickup and delivery problems’, DSpace@MIT (Massachusetts Institute of Technology).
@misc{pavone2011asymptotically,
title = {{An asymptotically optimal algorithm for pickup and delivery problems}},
author = {Pavone, Marco and Frazzoli, Emilio and Treleaven, Kyle Ballantyne},
journal = {DSpace@MIT (Massachusetts Institute of Technology)},
year = {2011}
}Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.