  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.
