text: We consider the one-to-one Pickup and Delivery Problem (PDP) in Euclidean Space with arbitrary dimension @math where @math transportation requests are picked i.i.d. with a separate origin-destination pair for each object to be moved. First, we consider the problem from the customer perspective where the objective is to compute a plan for transporting the objects such that the Euclidean distance traveled by the vehicles when carrying objects is minimized. We develop a polynomial time asymptotically optimal algorithm for vehicles with capacity @math for this case. This result also holds imposing LIFO constraints for loading and unloading objects. Secondly, we extend our algorithm to the classical single-vehicle PDP where the objective is to minimize the total distance traveled by the vehicle and present results indicating that the extended algorithm is asymptotically optimal for a fixed vehicle capacity if the origins and destinations are picked i.i.d. using the same distribution.
  @cite_0: 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 logistical operations. A widely-encountered type of 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 immediate, consecutive order. The SCP is NP-Hard and the best known approximation algorithm only provides a 9 5 approximation ratio. In this paper, we examine an embedding of the SCP within a stochastic framework, and our objective is three-fold: First, we describe a large class of algorithms for the SCP, where every member is asymptotically optimal, i.e., it produces, almost surely, a solution approaching the optimal one as the number of pickups deliveries goes to infinity; moreover, one can achieve computational complexity O(n2+e) within the class, where n is the number of pickup delivery pairs and e is an arbitrarily small positive constant. Second, we characterize the length of the optimal SCP tour asymptotically. 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 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.
  @cite_4: Consider the problem of transporting a set of objects between the vertices of a path by a vehicle which has limited capacity. The problem of finding a shortest tour for the vehicle to transport all objects from their initial vertices to their destination vertices is a fundamental problem in motion planning. It is shown that the problem is NP-complete if every object must be transported directly from its initial vertex to its destination. However, if objects can be dropped at intermediate vertices along its tour and picked up later then the problem can be solved in linear time. It is also shown that if the underlying graph is a tree, instead of a path, then the problem is NP-complete even if objects can be dropped at intermediate vertices.
summary: As noted by many authors, the PDP problem generalizes the classical TSP problem and is thus NP complete for @math . Guan @cite_4 has shown that the PDP problem is NP complete for @math and @math and Guan also shows how to solve this version in linear time if we allow temporarily dropping objects. @cite_0 present asymptotically optimal algorithms for @math (SCP) and @math where the origins are picked i.i.d. and the destinations are picked i.i.d. from separate distributions.