# Improving the Approximation Ratio for Capacitated Vehicle Routing

arXiv: https://arxiv.org/abs/2011.05235 · HTML: https://mlsanity.com/paper/2011.05235/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Nov 2020.

## Built on by (most cited first, 1 of 1)

- [NCO4CVRP: Neural Combinatorial Optimization for the Capacitated Vehicle Routing Problem](https://mlsanity.com/paper/2604.16581/) (2026)

## Abstract (arXiv)

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 and Altinkemer and Gavish.