A Quasipolynomial Time Approximation Scheme for Euclidean Capacitated Vehicle Routing

In the capacitated vehicle routing problem we are given the locations of customers and depots, along with a vehicle of capacity . The objective is to find a minimum length collection of tours covering all customers such that each tour starts and end at a depot and visits at most customers. The problem is a generalization of the traveling salesman problem. We present a quasipolynomial time approximation scheme for the Euclidean setting of the problem when all points lie in for constant dimension .