Breaching the 2-Approximation Barrier for Euclidean Capacitated Vehicle Routing

In the (Unit Demand) Euclidean Capacitated Vehicle Routing problem (CVRP), we are given a collection of \(n\) points in the Euclidean plane (the clients), one extra point (the depot), and one integer \(Q \ge 1\) (the vehicle capacity). A feasible solution is a collection of tours, where each tour contains the depot and at most \(Q\) clients, such that each client belongs to at least one such tour. Our goal is to minimize the total length of the tours. This models, e.g., the problem of delivering identical items stored at the depot to clients using a single vehicle that can carry at most \(Q\) items at a time.