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

Abstract

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 ≥ 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. © 2019 Krasovskii Institute of Mathematics and Mechanics. All right reserved.