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. © 2010 Wiley Periodicals, Inc.
| Original language | English |
|---|---|
| Pages (from-to) | 728-748 |
| Journal | Naval Research Logistics |
| Volume | 57 |
| Issue number | 8 |
| DOIs | |
| Publication status | Published - Dec 2010 |
| Externally published | Yes |
Bibliographical note
Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].Funding
This research was supported in part by the Research Grants Council of Hong Kong under grant numberPolyU5320/10E.
Research Keywords
- Approximation algorithms
- Approximation hardness
- Min-max path cover
- Vehicle routing
RGC Funding Information
- RGC-funded