A PTAS for Capacitated Vehicle Routing on Trees
arXiv:2111.03735
Abstract
We give a polynomial time approximation scheme (PTAS) for the unit demand capacitated vehicle routing problem (CVRP) on trees, for the entire range of the tour capacity. The result extends to the splittable CVRP.
Accepted for publication at ICALP 2022