Computer Science – Systems and Control
Scientific paper
2012-02-07
Computer Science
Systems and Control
27 pages, plus Appendix, 7 figures, extended version of paper being submitted to IEEE Transactions of Automatic Control
Scientific paper
The Stacker Crane Problem is NP-Hard and the best known approximation algorithm only provides a 9/5 approximation ratio. The objective of this paper is threefold. First, by embedding the problem within a stochastic framework, we present a novel algorithm for the SCP that: (i) is asymptotically optimal, i.e., it produces, almost surely, a solution approaching the optimal one as the number of pickups/deliveries goes to infinity; and (ii) has computational complexity $O(n^{2+\eps})$, where $n$ is the number of pickup/delivery pairs and $\eps$ is an arbitrarily small positive constant. Second, we asymptotically characterize the length of the optimal SCP tour. Finally, we study a dynamic version of the SCP, whereby pickup and delivery requests arrive according to a Poisson process, and which serves as a model for large-scale demand-responsive transport (DRT) systems. For such a dynamic counterpart of the SCP, we derive a necessary and sufficient condition for the existence of stable vehicle routing policies, which depends only on the workspace geometry, the stochastic distributions of pickup and delivery points, the arrival rate of requests, and the number of vehicles. Our results leverage a novel connection between the Euclidean Bipartite Matching Problem and the theory of random permutations, and, for the dynamic setting, exhibit novel features that are absent in traditional spatially-distributed queueing systems.
Frazzoli Emilio
Pavone Marco
Treleaven Kyle
No associations
LandOfFree
Asymptotically Optimal Algorithms for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Asymptotically Optimal Algorithms for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotically Optimal Algorithms for Pickup and Delivery Problems with Application to Large-Scale Transportation Systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-578570