The finite capacity dial-a-ride problem

We give the first non-trivial approximation algorithm for the Capacitated Dial-a-Ride problem: given a collection of objects located at points in a metric space, a specified destination point for each abject, and ct vehicle with a capacity of at mast k objects, the goal is to compute a shortest tour for the vehicle in which all objects can be delivered to their destinations while ensuring that the vehicle carries at most k objects at any point in time. The problem is known under several names, including the Stacker Crane problem and the Dial-a-Ride problem. No theoretical approximation approximations guarantees were known for this problem other than for the cases k = 1, infinity and the trivial O(k) approximation for general capacity k. We give an algorithm with approximation ratio O(root k) for special instances on a class of tree metrics called height-balanced trees. Using Bartal's recent results on the probabilistic approximation of metric spaces by tree metrics, we obtain an approximation ratio of O(root k log n log log n) for arbitrary n point metric spaces. When the points lie on a line (line metric), we provide a 2-approximation algorithm. We also consider the Dial-a-Ride problem in another framework: cc hen the vehicle is allowed to leave objects at intermediate locations and pick them Icp at a Inter time and deliver them. For this model, we design an approximation algorithm tr hose performance ratio is O(1)for tree metrics and O(log n log log n) for arbitrary metrics. We also study the ratio between the values of the optimal solutions for the two versions of the problem. We show that unlike in k-delivery TSP in which all the objects are identical, this ratio is not bounded by a constant for the Dial-a-Ride problem, and it could be as large as Omega(k(2/3)).