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_13: In the capacitated vehicle routing problem, introduced by Dantzig and Ramser in 1959, we are given the locations of n customers and a depot, along with a vehicle of capacity k, and wish to find a minimum length collection of tours, each starting from the depot and visiting at most k customers, whose union covers all the customers. We give a quasi-polynomial time approximation scheme for the setting where the customers and the depot are on the plane, and distances are given by the Euclidean metric.
  @cite_6: Certain “Bus Problems” are defined as generalizations of the traveling salesman problem. The simplest result concerns the length of the tour required by a single bus to pick up and deliver n passengers from random locations to random destinations in a bounded region of the plane. It is shown that the length of the tour divided by the square root of n converges almost surely to the square root of slightly more than twice the area of the region as n goes to infinity. When several buses are available, the length of the tour is simply divided by the number of buses. The bus problems have been motivated by the practical problem of scheduling dial-a-ride transportation systems.
summary: Stein @cite_6 also conducts a probabilistic analysis but he looks at the variant where @math and @math and where @math origins and @math destinations are picked independently using a uniform distribution on some planar region. Stein shows that the value of the optimal solution divided by @math converges almost surely to a constant times the square root of the area of the region. Stein also shows how to solve the problem he considers by concatenating two TSP tours on the origins and destinations respectively. This way of solving the problem yields a solution which is roughly @math O(n^2) @math 4 @math d=2 @math c=+ @math d=2 @math c = O( n) @math d @math c$ @cite_13 .