Efficient Approximation of the Capacitated Vehicle Routing Problem in a Metric Space of an Arbitrary Fixed Doubling Dimension

M. Yu. Khachay^a^,^b^,^c^,* and Yu. Yu. Ogorodnikov^a^,^b^,**

^aKrasovskii Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, Yekaterinburg, 620219 Russia

^bUral Federal University, Yekaterinburg, 620002 Russia

^cOmsk State Technical University, Omsk, 644050 Russia

Correspondence to: *e-mail: mkhachay@imm.uran.ru
Correspondence to: **e-mail: yogorodnikov@gmail.com

Received 26 May, 2020

Abstract—In this paper, for the first time, we provide a quasi-polynomial time approximation scheme for the well-known capacitated vehicle routing problem formulated in metric spaces of an arbitrary fixed doubling dimension.

Keywords: capacitated vehicle routing problem, metric spaces of a fixed doubling dimension, quasi-polynomial time approximation scheme

DOI: 10.1134/S1064562420040080