Given 7t Identical objects (pegs), placed at arbitrary initial locations, we conoider the problem of transporting them efficiently to n target locntlons (slots) with a vehicle that can carry at most k pegs at a time, This problem is referred to as k-delivery TSP. and it is a generalization of the Traveling Salesman Problem. We give a 5 approximation algorithm for the problem of minimizing the total dlstancc trnveled by the vehicle. Them arc two Wnds of transportations possible-one that could drop pegs at intermediate locations and pick them up later in the route for delivery (preemptive) and one that transports pegs to their tnrgeto directly (non-preemptive). In the former case, by exploiting the freedom to drop, one may be able to find a shorter delivery route, WC construct a non-preemptive tour that is within a factor 5 of the optimal preemptive tour. In addition we show that the ratio oP the distances traveled by an optimal non-preemptive tour versus n preemptive tour is bounded by 4. Vehicle routing and delivery problems have been widely studied In Computer Science and Operations Research. Many of these problems arc NP-hard, and a lot of research has been done on analyzing heuristics to find "good" solutions to these problems. These transportation problems occur in real life in areas such as robo(ics and transportation of packages. Methods for obtaining "good" solutions to the problems are of great practical significance. For example, Cnsco el al [9] report that combining deliveries and pickups for supermarkets led to an industry wide savings of $160 million a year, The problem that we consider in this paper is that of transporting a single commodity from a set of suppliers to a set of demand points using a vehicle of limited capacity. One way to analyze the performance of a heuristic is to compute the worst-case ratio between the cost of a solution produced by the algorithm to the cost of an optimal solution. If this ratio is bounded by p, we refer to this algorithm as an approximation algorithm with performance ratio p or simply as a papproximation algorithm. k-Delivery ?taveIing SaIesman Problem: Given n identical pegs placed at arbitrary locations, a vehicle with a maximum capacity of k pegs, and rz slots (demand points), each requiring a peg, tbe problem is to find a shortest tour for the vehicle in which all the pegs can be transported to their slots without exceeding the capacity of the vehicle. This problem is referred to as k-delivery TSP. It is a generalization of the traveling salesman problem (TSP), and is therefore NP-hard. The distances between the given points satisfies the triangle inequality since the vehicle can always take a shortest path between any two points. Replacing the distances behveen each pair of points by the shortest-path distance between them ensures that the triangle inequality is satisfied. Haimovich and Rinnooy Kan [17] studied a special cuse of this problem when all the pegs are located at one central depot, and are delivered with a vehicle of capacity k. They provided an approximation algorithm that obtains a performance ratio of 3. For geometric graphs -graphs induced by points in the plane with Euclidean distances as edge-weights, they provided a polynomial time approximation scheme for constant k. Christofides [ 1 I] surveys various issue-s, including problem formulation and algorithms, related to the vehicle routing problem, where the vehicles originate at a central depot. In STGC! '97, Asano et al [6] gave a polynomial-time approximation scheme for the same special case in the geometric setting, when k is O(logn/ loglogn). Anily and Hassin [2] demonstrated an algorithm that obtains a ratio of 2.5 for the l-delivery TSP. The first constant factor approximation algorithm for the general problem was given by Chalasani, Motwani and Rao [IO]. We will refer to their algorithm as the "CMR algorithm". They obtained an approximation ratio of 9.5. They also gave better algorithms for the cases k = 1 and k = 00, that obtain ratios of 2 in both cases. Independent of our work, Anily and Bramel [l] showed that a modification of the CMR algorithm improves the approximation ratio to 7 -i (in fact, we show that one can obtain a better bound of 6.5 by modifying the CMR approach). They also gave another algorithm with an approximation ratio of c(k) + $og, k, where 2 s c(k) < 3. Our Results: We summarize the results presented in this paper below: l For the k-delivery TSP. we provide a natural approximation algorithm that runs in polynomial time and show that its performance ratio is at most 5. Since the proof is complex, we first prove a simpler bound of 6.5; this proof contains some of the basic ideas. 349
REF studied the related k-delivery TSP problem, which involves transporting a number of identical objects from supply to demand vertices, using a single-capacity k vehicle.
Algorithms for capacitated vehicle routing
STOC '98
Computer Science