4.2 Article

A PTAS for Capacitated Vehicle Routing on Trees

Journal

ACM TRANSACTIONS ON ALGORITHMS
Volume 19, Issue 2, Pages -

Publisher

ASSOC COMPUTING MACHINERY
DOI: 10.1145/3575799

Keywords

Approximation algorithms; capacitated vehicle routing; graph algorithms; combinatorial optimization

Ask authors/readers for more resources

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.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.2
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available