Premium
Approximation algorithms for distance constrained vehicle routing problems
Author(s) -
Nagarajan Viswanath,
Ravi R.
Publication year - 2012
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20435
Subject(s) - combinatorics , cardinality (data modeling) , approximation algorithm , mathematics , metric (unit) , metric space , upper and lower bounds , vehicle routing problem , set (abstract data type) , space (punctuation) , routing (electronic design automation) , star (game theory) , tree (set theory) , discrete mathematics , computer science , mathematical analysis , computer network , operations management , economics , data mining , programming language , operating system
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 \over \varepsilon }),1 + \varepsilon )$ ‐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 \over \varepsilon })$ times the optimal number of vehicles. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012