Approximation algorithms for distance constrained vehicle routing problems

Abstract

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/ε),1 + ε) -bicriteria approximation algorithm: i.e., for any ε > 0, it obtains a solution violating the length bound by a 1 + ε factor while using at most O(log 1/ε) times the optimal number of vehicles. © 2011 Wiley Periodicals, Inc.