Back to Search
Start Over
Improving the approximation ratio for capacitated vehicle routing.
- Source :
-
Mathematical Programming . Feb2023, Vol. 197 Issue 2, p451-497. 47p. - Publication Year :
- 2023
-
Abstract
- We devise a new approximation algorithm for capacitated vehicle routing. Our algorithm yields a better approximation ratio for general capacitated vehicle routing as well as for the unit-demand case and the splittable variant. Our results hold in arbitrary metric spaces. This is the first improvement upon the classical tour partitioning algorithm by Haimovich and Rinnooy Kan (Math Oper Res 10:527–542, 1985) and Altinkemer and Gavish (Oper Res Lett 6:149–158, 1987). [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00255610
- Volume :
- 197
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Mathematical Programming
- Publication Type :
- Academic Journal
- Accession number :
- 161716902
- Full Text :
- https://doi.org/10.1007/s10107-022-01841-4