Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem

We consider the classic setting of Capacitated Vehicle Routing Problem (CVRP): single product, single depot, demands of all customers are identical. This problem is known to be strongly NP-hard even for Euclidean spaces of fixed dimension. Being intractable, it can be well approximated. For instance, in the Euclidean plane, the problem (along with some of its modifications) admits polynomial time approximation schemes (PTAS). We propose polynomial time approximation scheme for the case of $R^3.$