Approximation results for min-max path cover problems in vehicle routing
✍ Scribed by Zhou Xu; Liang Xu; Chung-Lun Li
- Publisher
- John Wiley and Sons
- Year
- 2010
- Tongue
- English
- Weight
- 410 KB
- Volume
- 57
- Category
- Article
- ISSN
- 0894-069X
No coin nor oath required. For personal study only.
✦ Synopsis
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. Naval Research Logistics, 2010