Approximation Algorithms for Distance Constrained Vehicle Routing Problems

We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47-61, Li et al., Oper Res 40 (1992), 790-799): given a set of vertices in a metric space, a specified depot, and a distance bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D. This problem is NP-complete, even when the underlying metric is induced by a weighted star. Our main result is a 2-approximation algorithm for DVRP on tree metrics; we also show that no approximation factor better than 1.5 is possible unless P = NP. For the problem on general metrics, we present a (O(log 1/epsilon), 1 + epsilon)-bicriteria approximation algorithm: i.e., for any epsilon > 0, it obtains a solution violating the length bound by a 1 + epsilon factor while using at most O(log 1/epsilon) times the optimal number of vehicles. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(2), 209-214 2012