Approximating Capacitated Routing and Delivery Problems

Abstract

We provide approximation algorithms for some capacitated vehicle routing and delivery problems. These problems can all be viewed as instances of the following k-delivery TSP: given n source points and n sink points in a metric space, with exactly one item at each source, find a minimum length tour by a vehicle of finite capacity k to pick up and deliver exactly one item to each sink. The only known approximation algorithm for this family of problems is the 2.5-approximation algorithm of Anily and Hassin [ Networks, 22 (1992), pp. 419--433] for the special case k=1. For this case, we use matroid intersection to obtain a 2-approximation algorithm. Based on this algorithm and some additional lower bound arguments, we devise a factor-approximation for k-delivery TSP with arbitrary finite k. We also present a 2-approximation algorithm for the case $k = \infty$. We then initiate the study of dynamic variants of k-delivery TSP that model problems in industrial robotics and other applications. Specifically, we consider the situation where a robot arm (with finite or infinite capacity) must collect n point-objects moving in the Euclidean plane, and deliver them to the origin. The point-objects are moving in the plane with known, identical velocities---they might, for instance, be on a moving conveyor belt. We derive several useful structural properties that lead to constant-factor approximations for problems of this type that are relevant to the robotics application. Along the way, we show that maximum latency TSP is implicit in the dynamic problems, and that the natural "farthest neighbor" heuristic produces a good approximation for several notions of latency.