Approximation of the capacitated vehicle routing problem with a limited number of routes in metric spaces of fixed doubling dimension

The capacitated vehicle routing problem (CVRP) is a classical combinatorial optimization problem having a wide range of practically important applications in operations research. As most combinatorial problems, CVRP is strongly NP-hard (even on the Euclidean plane). A metric instance of CVRP is APX-complete, so it cannot be approximated to arbitrary prescribed accuracy in the class of polynomial time algorithms (assuming that $P\ne NP$). Nevertheless, in the case of finite-dimensional Euclidean spaces, a quasi-polynomial or even polynomial time approximation scheme can be found for the problem by applying an approach based on works by S. Arora, A. Das, and C. Mathieu. Below, this approach has been extended for the first time to a significantly larger class of metric spaces of fixed doubling dimension. It is shown that CVRP formulated in such a space has a quasi-polynomial time approximation scheme whenever the number of routes in its optimal solution is bounded above by a polynomial in the logarithm of the input size.