A PTAS for Capacitated Vehicle Routing on Trees

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.

Automated summary

We propose a PTAS for solving the unit demand capacitated vehicle routing problem (CVRP) on trees, covering all possible tour capacities. The same approach can be extended to the splittable CVRP.