Approximability of the optimal routing problem in finite-dimensional Euclidean spaces

The capacitated vehicle routing problem (CVRP) is a classical combinatorial optimization problem with a wide range of applications in operations research. Since the CVRP is NP-hard even in a finite-dimensional Euclidean space, special attention is traditionally paid to the issues of its approximability. A major part of the known results concerning approximation algorithms and polynomial-time approximation schemes (PTAS) for this problem are obtained for its particular instance on the Euclidean plane. In the present paper we show that the approach to the development of a PTAS in the planar problem with a single depot proposed by Haimovich and Rinnooy Kan in 1985 can be effectively applied in a more general case, for example, in spaces of arbitrary fixed dimension and for an arbitrary number of depots.