Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension

The Capacitated Vehicle Routing Problem (CVRP) is a classical extremal combinatorial routing problem with numerous applications in operations research. Although the CVRP is strongly NP-hard both in the general case and in the Euclidean plane, it admits quasipolynomial- and even polynomial-time approximation schemes (QPTAS and PTAS) in Euclidean spaces of fixed dimension. At the same time, the metric setting of the problem is APX-complete even for an arbitrary fixed capacity $q\geq 3$. In this paper, we show that the classical Haimovich–Rinnooy Kan algorithm implements a PTAS and an Efficient Polynomial-Time Approximation Scheme (EPTAS) in an arbitrary metric space of fixed doubling dimension for $q=o(\log\log n)$ and for an arbitrary constant capacity, respectively.