A PTAS for Euclidean Capacitated Vehicle Routing
arXiv:2611.19018 · doi:10.1109/FOCS68528.2026.00016
Abstract
In the Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, we are given an -node graph with metric edges costs , a depot , and an integer vehicle capacity . The goal is to find a minimum-cost collection of tours, each containing the depot and visiting at most other nodes, such that the tours cover all the nodes. In this paper we focus on the Euclidean CVRP problem, where the nodes represent points on , and the edge costs are the respective Euclidean distances. Euclidean CVRP generalizes the classical NP-hard Euclidean TSP problem (the special case with ), that admits a PTAS [Arora FOCS'96/Mitchell SODA'96]. A long-standing open problem has been generalizing the latter PTAS to Euclidean CVRP. A polynomial-time -approximation for this problem follows from the PTAS for Euclidean TSP and the tour-partitioning technique for CVRP [Haimovich, Kan Math. OR'85]. This was the best known until a recent improvement of the approximation factor to slightly below 2 [Friggstad, Grandoni, Mousavi SODA'26]. There have been a series of papers presenting improved QPTASs by Das and Mathieu [SODA'10] (time ), Jayaprakash and Salavatipour [SODA'22] (time ), and recently Sitters [ArXiV'25] (time ). In this paper, we solve the mentioned long-standing open problem by presenting a PTAS for Euclidean CVRP.