Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/8530
Title: Approximation results for min-max path cover problems in vehicle routing
Authors: Xu, Z 
Xu, L
Li, CL 
Keywords: Approximation algorithms
Approximation hardness
Min-max path cover
Vehicle routing
Issue Date: 2010
Publisher: John Wiley & Sons
Source: Naval research logistics, 2010, v. 57, no. 8, p. 728-748 How to cite?
Journal: Naval research logistics 
Abstract: This article studies a min-max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 -2/k,2}, 5, max{5 -2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP, it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min-max vehicle routing problems.
URI: http://hdl.handle.net/10397/8530
ISSN: 0894-069X
EISSN: 1520-6750
DOI: 10.1002/nav.20434
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

7
Last Week
0
Last month
1
Citations as of Aug 19, 2017

WEB OF SCIENCETM
Citations

7
Last Week
1
Last month
0
Citations as of Aug 15, 2017

Page view(s)

44
Last Week
1
Last month
Checked on Aug 21, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.