Back to Search
Start Over
Approximations for minimum and min-max vehicle routing problems
- Source :
-
Journal of Algorithms . Apr2006, Vol. 59 Issue 1, p1-18. 18p. - Publication Year :
- 2006
-
Abstract
- Abstract: We consider a variety of vehicle routing problems. The input to a problem consists of a graph and edge lengths , . Customers located at the vertices have to be visited by a set of vehicles. Two important parameters are k the number of vehicles, and λ the longest distance traveled by a vehicle. We consider two types of problems. (1) Given a bound λ on the length of each path, find a minimum sized collection of paths that cover all the vertices of the graph, or all the edges from a given subset of edges of the input graph. We also consider a variation where it is desired to cover N by a minimum number of stars of length bounded by λ. (2) Given a number k find a collection of k paths that cover either the vertex set of the graph or a given subset of edges. The goal here is to minimize λ, the maximum travel distance. For all these problems we provide constant ratio approximation algorithms and prove their NP-hardness. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 01966774
- Volume :
- 59
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 21361262
- Full Text :
- https://doi.org/10.1016/j.jalgor.2005.01.007